August 19, 2024
P55 - Construct completely balanced binary trees
In a completely balanced binary tree, the following property holds for every node: The number of nodes in its left subtree and the number of nodes in its right subtree are almost equal, which means their difference is not greater than one.
Write a function cbal-tree to construct completely balanced binary trees for a given number of nodes. The function should generate all solutions. Put the symbol 'x' as information into all nodes of the tree.
Example:* (cbal-tree-print 4)(X (X NIL NIL) (X NIL (X NIL NIL)))(X (X NIL NIL) (X (X NIL NIL) NIL))etc......
Note: you can either print the trees or return a list with them all.
* (cbal-tree 4)((X (X NIL NIL) (X NIL (X NIL NIL))) (X (X NIL NIL) (X (X NIL NIL) NIL)) ......)
lisp
;;; cbal-tree(n): list version
;;; returns a list with all completely balanced binary trees with a
;;; given number of nodes.
;;;
;;; Note: it seems possible to improve the performance using
;;; dynamic programming
(defun cbal-tree (n)
(cond
((= n 0) (list ()))
((oddp n)
(append (cart-process (cbal-tree (/ (1- n) 2))
(cbal-tree (/ (1- n) 2))
)
))
((evenp n)
(append (cart-process (cbal-tree (/ (- n 2) 2))
(cbal-tree (/ n 2))
)
(cart-process (cbal-tree (/ n 2))
(cbal-tree (/ (- n 2) 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))
)
)
)
;;; cbal-tree: print version
;;; call list version and then print each element
(defun cbal-tree-print (n)
(dolist (tree (cbal-tree n))
(print tree)
)
)