# Difference between revisions of "99 questions/Solutions/64"

(Another solution) |
|||

Line 20: | Line 20: | ||

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. |
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 <tt>Branch</tt> nodes in the subtree. |
It returns the subtree annotated with positions, plus the count of <tt>Branch</tt> nodes in the subtree. |
||

+ | |||

+ | |||

+ | The following is another solution. The root is located at (0, 0). |
||

+ | <haskell> |
||

+ | 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 |
||

+ | </haskell> |

## Revision as of 12:07, 4 July 2011

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
```