(makeTree '(4 3 9 10))
(4 (3 (9 () ()) ()) (10 () ()))
To do it, I am using a function that splits the list in 2. So, what I did is tried to separate the head of the list from it's tail and then use the split function to be able to do the binary tree. But I am having trouble implementing it. Can someone help me please?
Here is my code so far:
(defun aux-head (l n)
(if (= n 0) '()
(cons (car l) (aux-head (cdr l)(- n 1)))))
(defun aux-tail (l n)
(if (= n 0) l
(aux-tail (cdr l) (- n 1))))
(defun split (lst)
(cond
((null lst) '(()()))
((evenp (length lst))
(list (aux-head lst (/ (length lst) 2))(aux-tail lst (/ (length lst) 2))))
((oddp (length lst))
(list (aux-head lst (+ (floor (length lst) 2) 1))
(aux-tail lst (+ (floor (length lst) 2) 1))))))
(defun make-cbtree (lst)
(cond
((null lst) '(()()))
((car lst)
((split ((cdr lst)))))))
the common approach to creating a binary search tree is to add items one by one. It could look like this:
(defun add-node (tree val)
(if (null tree)
(list val () ())
(destructuring-bind (v l r) tree
(if (< val v)
(list v (add-node l val) r)
(list v l (add-node r val))))))
this one inserts the value into the proper position (rebuilding the tree, immutable style):
CL-USER> (add-node (list 1 nil nil) 2)
;; (1 NIL (2 NIL NIL))
CL-USER> (add-node (list 1 nil nil) 0)
;; (1 (0 NIL NIL) NIL)
what you need next, is to process input list one by one, adding it to the tree, starting from the empty one:
(defun make-tree (data)
(reduce #'add-node data :initial-value nil))
CL-USER> (make-tree (list 4 3 9 10))
;; (4 (3 NIL NIL) (9 NIL (10 NIL NIL)))
you can also make up the traverse
procedure:
(defun traverse (tree)
(when tree
(append (traverse (cadr tree))
(list (car tree))
(traverse (caddr tree)))))
CL-USER> (traverse (make-tree (list 4 3 9 10)))
;; (3 4 9 10)