P64 - 二叉树布局：中序排列
Binary tree layout: in-order
官方模块：
Problems.P64核心函数：layoutInorder
题目描述
按中序遍历顺序给二叉树节点分配坐标 。 为中序遍历序号（即当前是第几个被访问的节点）， 为层数。
函数签名
1layoutInorder :: Tree a -> Tree (a, (Int, Int))
实现
方法一：递归分配坐标
1layoutInorder :: Tree a -> Tree (a, (Int, Int))
2layoutInorder tree = fst (layout tree 1 1)
3
4layout :: Tree a -> Int -> Int -> (Tree (a, (Int, Int)), Int)
5layout Empty next _ = (Empty, next)
6layout (Branch x left right) next y =
7 let (leftTree, next') = layout left next (y + 1)
8 (rightTree, next'') = layout right (next' + 1) (y + 1)
9 in (Branch (x, (next', y)) leftTree rightTree, next'')
中序遍历：先布局左子树得到 next'，当前节点 x = next'，再布局右子树，起始序号为 next' + 1。
方法二：利用左子树大小定位
1layoutInorder :: Tree a -> Tree (a, (Int, Int))
2layoutInorder tree = place tree 0 1
3 where
4 place Empty _ _ = Empty
5 place (Branch value left right) skipped depth =
6 Branch (value, (rootX, depth))
7 (place left skipped (depth + 1))
8 (place right rootX (depth + 1))
9 where
10 rootX = skipped + treeSize left + 1
先由 treeSize left 知道左子树会占用多少个中序位置。若此前已经跳过 skipped 个节点，根的位置就是 skipped + treeSize left + 1。它用子树大小直接定位，不需要在线程中返回下一个序号。
方法对比
| 方法 | 状态来源 | 复杂度 |
|---|---|---|
| 递归传递下一个序号 | 左子树布局后的返回值 | O(n) |
| 利用左子树大小 | 每个节点重新计算左子树大小 | 朴素实现最坏 O(n²) |
测试
1>>> layoutInorder (leaf 'a')
2Branch ('a',(1,1)) Empty Empty
3>>> layoutInorder (Branch 'a' (leaf 'b') (leaf 'c'))
4Branch ('a',(2,1)) (Branch ('b',(1,2)) Empty Empty) (Branch ('c',(3,2)) Empty Empty)