99 questions/Solutions/65
< 99 questions | Solutions
Jump to navigation
Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
An alternative layout method is depicted in the illustration below:
Find out the rules and write the corresponding 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.
layout :: Tree a -> Tree (a, Pos)
layout t = layoutAux x1 1 sep1 t
where d = depth t
ld = leftdepth t
x1 = 2^(d-1) - 2^(d-ld) + 1
sep1 = 2^(d-2)
layoutAux x y sep Empty = Empty
layoutAux x y sep (Branch a l r) =
Branch (a, (x,y))
(layoutAux (x-sep) (y+1) (sep `div` 2) l)
(layoutAux (x+sep) (y+1) (sep `div` 2) r)
depth :: Tree a -> Int
depth Empty = 0
depth (Branch a l r) = max (depth l) (depth r) + 1
leftdepth :: Tree a -> Int
leftdepth Empty = 0
leftdepth (Branch a l r) = leftdepth l + 1
The auxiliary function is passed the x- and y-coordinates for the root of the subtree, the horizontal separation between the root and its child nodes, and the subtree itself. It returns the subtree annotated with positions.