LISP Problem with Binary Search Tree (Please help!!)

Discussion of Common Lisp
Post Reply
Posts: 1
Joined: Thu Oct 07, 2010 8:48 am

LISP Problem with Binary Search Tree (Please help!!)

Post by luen_ck » Thu Oct 07, 2010 9:10 am

I hv wrote a function to search a value if it's in a binary search tree (the output is T when it's in the binary tree, otherwise NIL):

Code: Select all

(defun search1 (a)
(if (listp temp) (and (setq node (car temp)) 
(setq left (cadr temp)) (setq right (caddr temp))))
(if (listp node)           
(setq node1 (car node)) (setq node1 node))
                 (cond ((= a node1) (and (setq temp input) (= 1 1)))
	         ((> a node1) (and (setq temp right) 
				 (if (atom temp)(if (= temp a) (and (setq temp input) (= 1 1)) (and (setq temp input) (= 1 2))) (search1 a))))
                 ((< a node1) (and (setq temp left)
                                 (if (atom temp)(if (= temp a) (and (setq temp input) (= 1 1)) (and (setq temp input) (= 1 2))) (search1 a))))))
(defun search (a)
(setq temp input)
(if (= 1 1) (search1 a)))
When I set the input as (5 4 (9 nil 10)) and run (search 9), the variable right becomes (9 NIL 10) instead of 10. The worst is that When i search 10, the program stopped n showed no response.
It's totally fine when the input is (5 4 (9 7 10)).

I hv struggled with this problem for 5 hours, pleae help!! :cry:
Last edited by nuntius on Thu Oct 07, 2010 10:25 am, edited 1 time in total.
Reason: add the [code] block

Paul Donnelly
Posts: 148
Joined: Wed Jul 30, 2008 11:26 pm

Re: LISP Problem with Binary Search Tree (Please help!!)

Post by Paul Donnelly » Mon Oct 11, 2010 3:16 pm

You should change the program to use better style; that will probably make the problem more obvious. Indentation never hurts. SETQ isn't for defining variables. If you want a global variable, use DEFVAR outside your function. As for global variables themselves, you don't want those. Pass more arguments instead. T and NIL are the symbols for true and false, so get rid of the (= 1 1) (= 1 2) stuff. Anywhere you've written (AND (condition) (= 1 1)) can simply be (condition). I'm assuming that you're trying to use AND all over the place for its short-circuiting properties; if there's another reason then whatever you're doing is totally wrong.

Anyway, the thing to do is throw this code away and start over. Don't use SETQ (or SETF) at all, and if you go over 10 lines of code you've made a big mistake and need to rethink your approach.

Post Reply