August 19, 2024
P59 - Construct height-balanced binary trees
In a height-balanced binary tree, the following property holds for every node: The height of its left subtree and the height of its right subtree are almost equal, which means their difference is not greater than one.Write a function hbal-tree to construct height-balanced binary trees for a given height.
The function should generate all solutions. Put the letter 'x' as information into all nodes of the tree.
Example:* (hbal-tree 3)(X (X (X NIL NIL) (X NIL NIL)) (X (X NIL NIL) (X NIL NIL)))= (X (X (X NIL NIL) (X NIL NIL)) (X (X NIL NIL) NIL))etc......
lisp
;;; hbal-tree(n): list version
;;; returns a list with all completely balanced binary trees with a
;;; given height.
;;;
(defun hbal-tree (h)
(cond
((<= h -2) ())
((= h -1) '(()) )
(t (append (cart-process (hbal-tree (- h 2))
(hbal-tree (- h 1))
)
(cart-process (hbal-tree (- h 1))
(hbal-tree (- h 1))
)
(cart-process (hbal-tree (- h 1))
(hbal-tree (- h 2))
)
))
)
)
(defun cart-process (l1 l2)
(process (cart-product l1 l2))
)
(defun process (lista)
(mapcar #'(lambda (x) (cons 'x x)) lista)
)
(defun cart-product (l1 l2)
(let ((a nil))
(dolist (t1 l1 a)
(setf a (append (mapcar #'(lambda (x) (list t1 x)) l2) a))
)
)
)
;;; hbal-tree: print version
;;; call list version and then print each element
(defun hbal-tree-print (h)
(dolist (tree (hbal-tree h))
(print tree)
)
)
Be first to comment