This is a read-only archive of lispforum.com. The forum was locked to new users and posts and is preserved here as static HTML from a database snapshot taken on 2019-09-07.

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

2 posts · 1054 views

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):
(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 , edited 1 time in total. Reason: add the [code] block

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

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.