P65 - 二叉树布局：层级等距

2026-09-07 00:00    #Haskell   #99题   #二叉树  

P65 - 二叉树布局：层级等距

Binary tree layout: constant distance between nodes at each level

官方模块：Problems.P65　核心函数：layoutLevelConstant

← P64 中序布局 | P66 紧凑布局 →

题目描述

父子节点的水平距离只由深度决定，越靠近根距离越大，向下一层距离减半。布局完成后最左节点的横坐标为 1。

函数签名

1layoutLevelConstant :: Tree a -> Tree (a, (Int, Int))

实现

方法一：按深度位移

 1layoutLevelConstant :: Tree a -> Tree (a, (Int, Int))
 2layoutLevelConstant tree = shift (1 - minimumX raw) raw
 3  where
 4    gap = 2 ^ max 0 (treeHeight tree - 2)
 5    raw = place tree 0 1 gap
 6
 7place :: Tree a -> Int -> Int -> Int -> Tree (a, (Int, Int))
 8place Empty _ _ _ = Empty
 9place (Branch value left right) x depth gap =
10  Branch (value, (x, depth))
11    (place left  (x - gap) (depth + 1) (gap `div` 2))
12    (place right (x + gap) (depth + 1) (gap `div` 2))
13
14minimumX :: Tree (a, (Int, Int)) -> Int
15minimumX Empty = 0
16minimumX (Branch (_, (x, _)) left right) =
17  minimum [x, minimumX left, minimumX right]
18
19shift :: Int -> Tree (a, (Int, Int)) -> Tree (a, (Int, Int))
20shift _ Empty = Empty
21shift amount (Branch (value, (x, y)) left right) =
22  Branch (value, (x + amount, y))
23    (shift amount left)
24    (shift amount right)

先以根横坐标 0 递归布局，再根据最小横坐标整体平移。树高决定根到孩子的初始距离。

方法二：满二叉树槽位公式

 1layoutLevelConstantByIndex :: Tree a -> Tree (a, (Int, Int))
 2layoutLevelConstantByIndex Empty = Empty
 3layoutLevelConstantByIndex tree = shiftBy (1 - minimumPosition raw) raw
 4  where
 5    height = treeHeight tree
 6    raw = placeAt tree 1 0
 7
 8    placeAt Empty _ _ = Empty
 9    placeAt (Branch value left right) depth slot =
10      Branch (value, (x, depth))
11        (placeAt left (depth + 1) (2 * slot))
12        (placeAt right (depth + 1) (2 * slot + 1))
13      where
14        x = (2 * slot + 1) * 2 ^ (height - depth)
15
16    minimumPosition = minimum . positions
17
18    positions Empty = []
19    positions (Branch (_, (x, _)) left right) =
20      x : positions left ++ positions right
21
22    shiftBy _ Empty = Empty
23    shiftBy amount (Branch (value, (x, y)) left right) =
24      Branch (value, (x + amount, y))
25        (shiftBy amount left)
26        (shiftBy amount right)

把当前树嵌入同高度的满二叉树。深度为 depth 的第 slot 个槽位横坐标可直接由公式算出，最后再按实际存在节点的最小横坐标归一化。

方法对比

方法核心思路
按深度位移从根坐标出发递归加减间距
槽位公式由深度和层内编号直接计算坐标

测试

1>>> layoutLevelConstant (Branch 'a' (leaf 'b') (leaf 'c'))
2Branch ('a',(2,1)) (Branch ('b',(1,2)) Empty Empty) (Branch ('c',(3,2)) Empty Empty)
3>>> layoutLevelConstantByIndex (Branch 'a' (leaf 'b') (leaf 'c'))
4Branch ('a',(2,1)) (Branch ('b',(1,2)) Empty Empty) (Branch ('c',(3,2)) Empty Empty)

参考