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

"

(defun binary-tree-height (tree)
  (if (binary-tree-empty-p tree)
      0
      (+ 1 (max (binary-tree-height (binary-tree-left tree))
                (binary-tree-height (binary-tree-right tree))))))

(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 ((offset (expt 2 height)))
    (unless (binary-tree-empty-p (binary-tree-left node))
      (layout-node-p65 (binary-tree-left node)
                       (- abscissa offset)
                       (1+ depth)
                       (1- height)))
    (unless (binary-tree-empty-p (binary-tree-right node))
      (layout-node-p65 (binary-tree-right node)
                       (+ abscissa offset)
                       (1+ depth)
                       (1- height))))
  node)


(defun layout-binary-tree-p65 (tree)
  (let ((height (binary-tree-height tree)))
    (layout-node-p65 (binary-tree-to-layout-binary-tree tree)
                     (expt 2  height)
                     0
                     height)))

;;;; THE END ;;;;