99 questions/Solutions/64
Given a binary tree as the usual Prolog term t(X,L,R) (or nil). As a preparation for drawing the tree, a layout algorithm is required to determine the position of each node in a rectangular grid. Several layout methods are conceivable, one of them is shown in the illustration below:
In this layout strategy, the position of a node v is obtained by the following two rules:
- x(v) is equal to the position of the node v in the inorder sequence
- y(v) is equal to the depth of the node v in the tree
Write a function to annotate each node of the tree with a position, where (1,1) in the top left corner or the rectangle bounding the drawn tree.
type Pos = (Int, Int)
layout :: Tree a -> Tree (a, Pos)
layout t = fst (layoutAux 1 1 t)
where layoutAux x y Empty = (Empty, x)
layoutAux x y (Branch a l r) = (Branch (a, (x',y)) l' r', x'')
where (l', x') = layoutAux x (y+1) l
(r', x'') = layoutAux (x'+1) (y+1) r
The auxiliary function is passed the x-coordinate for the left-most node of the subtree, the y-coordinate for the root of the subtree, and the subtree itself. It returns the subtree annotated with positions, plus the count of Branch nodes in the subtree.
The following is another solution. The root is located at (0, 0).
tree64 t =
helper 0 0 t
where
helper x y Empty =
Empty
helper x y (Branch _ t0 t1) =
let
l = rights t0
r = lefts t1
in
Branch (x,y) (helper (x - l) (succ y) t0) (helper (x + r) (succ y) t1)
-- counting right steps caused by helper
rights (Branch _ t0 t1) =
rightsHelper t1 + 1
rights Empty =
0
-- counting left steps caused by helper
lefts (Branch _ t0 t1) =
leftsHelper t0 + 1
lefts Empty =
0
leftsHelper (Branch _ t0 t1) = rightsHelper t1 + leftsHelper t0 + 1
leftsHelper Empty = 0
rightsHelper (Branch _ t0 t1) = leftsHelper t0 + rightsHelper t1 + 1
rightsHelper Empty = 0