#-(and) "
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 predicate should generate
all solutions via backtracking. Put the letter 'x' as information
into all nodes of the tree.
Example:
* cbal-tree(4,T).
T = t(x, t(x, nil, nil), t(x, nil, t(x, nil, nil))) ;
T = t(x, t(x, nil, nil), t(x, t(x, nil, nil), nil)) ;
etc......No
"
;; Solution:
(defun binary-tree-count-nodes (node)
(if (binary-tree-empty-p node)
0
(+ 1
(binary-tree-count-nodes (binary-tree-left node))
(binary-tree-count-nodes (binary-tree-right node)))))
(defun binary-tree-balanced-p (node)
(or (binary-tree-empty-p node)
(<= (abs (- (binary-tree-count-nodes (binary-tree-left node))
(binary-tree-count-nodes (binary-tree-right node))))
1)))
;; (binary-tree-balanced-p (binary-tree-from-sexp '(x (x nil nil) (x nil (x nil nil)))))
;; --> T
;;
;; (binary-tree-balanced-p (binary-tree-from-sexp '(x (x nil nil) (x (x nil nil) nil))))
;; --> T
;;
;; (binary-tree-balanced-p (binary-tree-from-sexp '(x nil (x (x nil nil) nil))))
;; --> NIL
;;;; THE END ;;;;