August 19, 2024
P65 - Layout a binary tree (2)
An alternative layout method is depicted in the illustration opposite. Find out the rules and write the corresponding Lisp function.
Hint: On a given level, the horizontal distance between neighboring nodes is constant.
Use the same conventions as in problem P64 and test your function in an appropriate way.
lisp
(defun layout-aux (a x y tree)
(if (null tree)
()
(list (first tree)
x
y
(layout-aux (/ a 2) (- x (/ a 2)) (1+ y) (second tree))
(layout-aux (/ a 2) (+ x (/ a 2)) (1+ y) (third tree))
)
)
)
(defun layout-binary-tree (tree)
(multiple-value-bind (a x)
(initial-params tree)
(layout-aux a x 1 tree)
)
)
(defun initial-params (tree)
(if (null tree)
(values 1/2 0)
(multiple-value-bind (al xl)
(initial-params (second tree))
(multiple-value-bind (ar xr)
(initial-params (third tree))
(let ((a (* 2 (max al ar))))
(values
a
(if (= xl 0)
1
(+ xl (/ a 2))
)
)
)
)
)
)
)
Be first to comment