I have tried to make a program creating a binary tree with a list as an input, but I am running into a few errors. For one, if I have less than 5 elements, it does not output anything at all, and when I have more than 5 elements, while I do receive the output I want, It also prints the final side of the tree computed as well. If any of you could help me with debugging it, it would be greatly appreciated! Please find below, sample input, sample output, as well as my code.
(make-cbtree '(8 3 10 1))
(8 (3 (1 () ()) ()) (10 () ()))
(make-cbtree '(8 3 10 1 6))
(8 (3 (1 () ()) (6 () ())) (10 () ()))
;;This program will take a list and print a binary tree
(defun entry (tree) ;Node
(car tree)
)
(defun left (tree) ;This function gets the left branch
(cadr tree)
)
(defun right (tree) ;Function will get the right branch
(caddr tree)
)
(defun make-tree (entry left right) ;This function creates the node for a binary tree
(if (= z y)
(print(list entry left right))
) ;if z=y then prints the list
(list entry left right)
)
(defun add (x tree) ;This function will add the element from list into tree
(cond ((null tree) (make-tree x '() '())) ;Empty node, return nil
((= x (entry tree)) tree) ;if element from list equals node
;;if element from list is less than node then call make-tree function and add element to left side
((< x (entry tree)) (make-tree (entry tree) (add x(left tree)) (right tree)))
;;if element from list is greater than node then call make-tree function and add element to right side
((> x (entry tree)) (make-tree (entry tree) (left tree) (add x (right tree))))
)
)
(defun make-cbtree(elements) ;Call this function to create a binary tree
(dolist (x elements) ;Using dolist to go through all elements in list
(setf z (+ z 1))
(setf tree (add x tree))
)
)
;;Default values
(setf tree '())
(defvar z 0)
(defvar y 5)
(make-cbtree '(8 3 10 1))
For a start, if you are going to define an abstraction for a binary tree, define the abstraction, not part of it. In particular you at least want an object which represents an empty tree and a test for a tree being empty, so your code is not full of obscure stuff which has leaked up from below the abstraction:
;;; A binary tree has an entry, a left and a right node
;;; The implementation is a three-element list
(defconstant empty-tree nil)
(defun empty-tree-p (tree)
(eq tree empty-tree))
(defun entry (tree)
(first tree))
(defun left (tree)
(second tree))
(defun right (tree)
(third tree))
(defun make-tree (entry left right)
(list entry left right))
Secondly I have no idea what the obscure global variables are for – were they some leftover debugging thing? They don't need to exist and are certainly breaking your code. Removing them will make it work I think.
Below is a version which works, does not use assignment, and uses the abstractions defined above throughout.
(defun add (x tree)
;; Add an entry to a tree
(cond ((empty-tree-p tree)
(make-tree x empty-tree empty-tree))
((= (entry tree) x)
tree)
((< (entry tree) x)
(make-tree (entry tree) (add x (left tree)) (right tree)))
(t
(make-tree (entry tree) (left tree) (add x (right tree))))))
(defun add-elts-to-tree (elts tree)
;; Add a number of elements to a tree
(if (null elts)
tree
(add-elts-to-tree (rest elts) (add (first elts) tree))))
(defun list->tree (l)
(add-elts-to-tree l empty-tree))
Now, because I've defined an abstraction for trees, I can, if I want, completely replace the implementation:
;;; A binary tree has an entry, a left and a right node
;;; The implementation is a function of one argument
(defconstant empty-tree (lambda (k)
(declare (ignore k))
nil))
(defun empty-tree-p (tree)
(eq tree empty-tree))
(defun make-tree (entry left right)
(lambda (k)
(ecase k
((entry) entry)
((left) left)
((right) right))))
(defun entry (tree)
(funcall tree 'entry))
(defun left (tree)
(funcall tree 'left))
(defun right (tree)
(funcall tree 'right))