P63 - 构造并判断完全二叉树
Construct and recognize complete binary trees
官方模块：
Problems.P63核心函数：completeBinaryTree,isCompleteBinaryTree
题目描述
完全二叉树中，除最后一层外每层都被填满，且最后一层的节点靠左排列。
函数签名
1completeBinaryTree :: Int -> Tree ()
2isCompleteBinaryTree :: Tree a -> Bool
数组下标模型
把根编号为 1，则编号 的左右孩子分别是 和 。完全二叉树恰好占用连续编号 。
实现
方法一：递归下标构造 + 验证
1completeBinaryTree :: Int -> Tree ()
2completeBinaryTree size = build 1
3 where
4 build i
5 | i > size = Empty
6 | otherwise = Branch () (build (2*i)) (build (2*i + 1))
7
8isCompleteBinaryTree :: Tree a -> Bool
9isCompleteBinaryTree tree = valid tree 1
10 where
11 size = treeSize tree
12 valid Empty i = i > size
13 valid (Branch _ left right) i =
14 i <= size && valid left (2*i) && valid right (2*i + 1)
方法二：isComplete 用 BFS
1isCompleteBinaryTree :: Tree a -> Bool
2isCompleteBinaryTree tree = scan [tree] False
3 where
4 scan [] _ = True
5 scan (Empty : rest) _ = scan rest True
6 scan (Branch _ _ _ : _) True = False
7 scan (Branch _ left right : rest) False =
8 scan (rest ++ [left, right]) False
BFS 层序遍历时，一旦遇到 Empty，之后就不能再有非空节点。
方法三：按左右子树规模构造
1completeBinaryTree :: Int -> Tree ()
2completeBinaryTree n
3 | n <= 0 = Empty
4 | otherwise = Branch ()
5 (completeBinaryTree leftSize)
6 (completeBinaryTree (n - 1 - leftSize))
7 where
8 height = floorLog2 n
9 lastLevel = n - (2 ^ height - 1)
10 leftCapacity = 2 ^ max 0 (height - 1)
11 leftSize
12 | height == 0 = 0
13 | otherwise = leftCapacity - 1 + min lastLevel leftCapacity
14
15floorLog2 :: Int -> Int
16floorLog2 value = length (takeWhile (<= value) (iterate (* 2) 1)) - 1
高度确定后，最后一层优先填入左子树。这个版本直接算出左右子树各有多少节点，不使用堆下标。
方法对比
| 任务 | 方法一 | 替代方法 |
|---|---|---|
| 构造 | 堆下标是否超过 n | 计算左右子树规模 |
| 判断 | 最大下标与节点数比较 | BFS 检查空位后的节点 |
测试
1>>> treeSize (completeBinaryTree 6)
26
3>>> isCompleteBinaryTree (completeBinaryTree 6)
4True
5>>> isCompleteBinaryTree (Branch 1 Empty (leaf 2))
6False