#+(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.


(load "p54a")



(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