```#+(and) "
P65 (**) Layout a binary tree (2)
[p65]

An alternative layout method is depicted in the illustration
opposite. Find out the rules and write the corresponding Prolog
predicate. Hint: On a given level, the horizontal distance between
neighboring nodes is constant.

Use the same conventions as in problem P64 and test your predicate in an appropriate way.

"

;; The rule seems to be that the ordinate is the depth of the node,
;; and the abscissa of a node is offset from the parent by 2^height of the node.
;;
;; The abscissa of the leftmost node is fixed to 1,
;; and the ordinate of the root is fixed to 1.
;;
;; height of the tree = depth of node + height of node.

(defun binary-tree-count-leftmosts (tree)
(if (binary-tree-empty-p tree)
0
(+ 1 (binary-tree-count-leftmosts (binary-tree-left tree)))))

(defun layout-node-p65 (node abscissa depth height)
"
The abscissa of the NODE is given by ABSCISSA, and the ordinate by DEPTH.
The abscissa of the children is offset by (expt 2 height).
"
(setf (layout-binary-tree-x node) abscissa
(layout-binary-tree-y node) depth)
(let* ((height-1 (1- height))
(depth+1  (1+ depth))
(offset   (expt 2 height-1)))
(unless (binary-tree-empty-p (binary-tree-left node))
(layout-node-p65 (binary-tree-left node)
(- abscissa offset)
depth+1
height-1))
(unless (binary-tree-empty-p (binary-tree-right node))
(layout-node-p65 (binary-tree-right node)
(+ abscissa offset)
depth+1
height-1)))
node)

(defun layout-binary-tree-p65 (tree)
(let ((height (binary-tree-height tree)))
(layout-node-p65 (binary-tree-to-layout-binary-tree tree)
(1+ (- (expt 2 (1- height))
(expt 2 (- height (binary-tree-count-leftmosts tree)))))
1
(1- height))))

(assert (= 4 (binary-tree-count-leftmosts (construct '(n k c a e d g m u p q) (function string<)))))
(assert (= 5 (binary-tree-height          (construct '(n k c a e d g m u p q) (function string<)))))
(assert (equal (layout-binary-tree-p65    (construct '(n k c a e d g m u p q) (function string<)))
'(N (K (C (A NIL NIL 1 4)
(E (D NIL NIL 4 5)
(G NIL NIL 6 5) 5 4) 3 3)
(M NIL NIL 11 3) 7 2)
(U (P NIL
(Q NIL NIL 21 4) 19 3)
NIL 23 2) 15 1)))

;; (list
;;  (draw-laid-out-tree (layout-binary-tree-p65 (complete-binary-tree 7)))
;;  (draw-laid-out-tree (layout-binary-tree-p65 (construct '(n k c a e d g m u p q)   (function string<))))
;;  (draw-laid-out-tree (layout-binary-tree-p65 (construct '(n k c a h g e m u p s q) (function string<)))))
;;
;; (
;;         1
;;        / \
;;     2       3
;;    / \     / \
;;   4   5   6   7
;;
;;
;;                               N
;;                              / \
;;               K                               U
;;              / \                             /
;;       C               M               P
;;      / \                               \
;;   A       E                               Q
;;          / \
;;         D   G
;;
;;
;;                                                           N
;;                                                          / \
;;                           K                                                               U
;;                          / \                                                             /
;;           C                               M                               P
;;          / \                                                               \
;;   A               H                                                               S
;;                  /                                                               /
;;               G                                                               Q
;;              /
;;             E
;; )

;;;; THE END ;;;;```
ViewGit