please help me: build a binary search tree by Lisp

[xzhang]

Write lisp for two functions that manipulate binary search trees. The tree will now be a nested list structure. Inserting 4, 2, 5, 1, 6, 3 should create the list: (4 (2 (1 () ()) (3 () ())) (5 () (6 () ())))

1.Write a lisp (scheme) function (isIn? item binTree) that returns #t if the item is in the binary search tree ‘binTree’, otherwise it returns #f.

2.Write a lisp (scheme) function (with helpers?) that builds a binary tree equivalent to the CLIPS binary tree for any input list. The main function will be called by (binTree () list)

[azimuth0]

I'm sorry, but what is it that you need help with?

[MidiMagic]

This looks like a homework assignment. Nobody but a college professor would use LISP.

We don't do your homework for you. But I can get you thinking.

LISP is a prefix language, so it is obvious that the binary tree structure you have is also prefix. A quick look confirms it.

So each node of the tree includes three list items, in this order:

- the node's element (a numeric atom)

- the left child branch of the tree (which is either a tree node or an empty list)

- the right child branch of the tree (which is either a tree node or an empty list)

Since it is a binary tree, all of the elements in the left child must be less than the element in the current node. Likewise, all of the elements in the right child must be greater than the element in the current node.

So your function should be able to tell which way to go by looking at the current node. 4 possibilites exist:

1. The current node is empty. You didn't find the search item.

2. The current node element equals the search value. You found it.

3. The current node element is larger than the search value. Recursively go left.

4. The current node element is smaller than the search value. Recursively go right.

[azimuth0]

You are incorrect. Both Common Lisp and Scheme are perfectly good industry languages with wide platform support and usage. For many, including myself, a lisp language is their preferred language.

I've seen lisp written by college professors, and it's awful. They only use lists, when an array, hash, or class would have been better.

[Rashakil Fol]

LISP is a prefix language, so it is obvious that the binary tree structure you have is also prefix.

What do you mean, in that it is "prefix"?

[raymondmak104]

How to do 3. The current node element is larger than the search value. Recursively go left.

4. The current node element is smaller than the search value. Recursively go right. ????

i have wirte a function like this but it's not work

(defun searching (a L)
(cond ((null L) nil)
((equal a (car L)) T)
(t (searching a (cdr L)))))