第 8 讲 · 树、二叉树与遍历

树表达层级关系。除根外，每个结点只有一个双亲，却可以有多个孩子；从根到任一结点只有一条路径。

基本术语

• 结点的度：孩子数；
• 树的度：所有结点度数的最大值；
• 叶结点：度为零；
• 层次：根为第一层，孩子比双亲多一层；
• 深度：最大层次；
• 子树：某结点及其全部后代；
• 森林：若干棵互不相交的树。

含 $n$ 个结点的非空树有 $n-1$ 条边，因为除根外每个结点恰由一条父子边接入。

树的存储

多叉树可以让每个结点保存定长孩子数组，但会浪费空指针；也可以保存双亲下标；最常用的通用方式是“第一个孩子—下一个兄弟”，每个结点只需两个指针。

第一个孩子—下一个兄弟表示法把一般树自然转换成二叉树：左指针指向第一个孩子，右指针指向下一个兄弟。森林中的各棵树则通过根的右指针相连。

二叉树不是“度为二的普通树”

二叉树的左右子树有次序，即使只有一个孩子，也要区分左孩子还是右孩子。它可能为空，且每个结点最多有两个孩子。

满二叉树与完全二叉树

深度为 $h$ 的满二叉树每层都达到最大结点数，共有 $2^h-1$ 个结点。完全二叉树除最下层外都满，最下层结点从左到右连续排列。

完全二叉树特别适合按层放进数组。编号从 1 开始时，结点 $i$ 的双亲为 $\lfloor i/2\rfloor$，左右孩子为 $2i$ 和 $2i+1$，前提是这些编号不超过结点数。

二叉树的重要性质

• 第 $i$ 层最多有 $2^{i-1}$ 个结点；
• 深度为 $h$ 时最多有 $2^h-1$ 个结点；
• 若叶结点数为 $n_0$、度为二的结点数为 $n_2$，则 $n_0=n_2+1$；
• 含 $n$ 个结点的完全二叉树深度为 $\lfloor\log_2 n\rfloor+1$。

$n_0=n_2+1$ 可以通过统计边得到：一方面边数是 $n-1$，另一方面也是所有结点度数之和 $n_1+2n_2$。

二叉树存储

顺序存储适合完全二叉树。一般二叉树若硬放数组会产生大量空位，因此常用二叉链表：

typedef struct BTNode {
    char data;
    struct BTNode *left;
    struct BTNode *right;
} BTNode;

遍历只有“根在什么时候访问”的区别

• 前序：根、左、右；
• 中序：左、根、右；
• 后序：左、右、根；
• 层序：从上到下、同层从左到右。

前三种都可看成同一递归框架：空树直接返回，递归处理左右子树，只改变访问根的位置。每个结点访问一次，时间 $O(n)$；递归栈空间是 $O(h)$。

层序遍历使用队列：根入队；循环取出队头并访问，再把其非空孩子入队。

由遍历序列恢复二叉树

前序序列第一个元素是根。到中序序列中找到它，左侧元素全属左子树，右侧全属右子树；再按相同规则递归处理。

中序加前序，或中序加后序，通常能唯一确定一棵元素互异的二叉树。只有前序和后序通常不能唯一确定，因为无法判断单孩子在左还是在右。

非递归遍历

前序和中序可以用显式栈保存“回头后还要处理的结点”。中序遍历时不断沿左链压栈；到空指针后弹栈访问，再转向右子树。

后序遍历还要知道右子树是否已经处理，因此需额外标志、保存上次访问结点，或使用两个栈。

典型递归操作

求结点数、叶结点数、深度、复制和销毁，都可以按“空树的答案 + 左右子树答案怎样组合”来写。例如

$$depth(T)=\begin{cases} 0,&T=\varnothing,\\ 1+\max(depth(T_L),depth(T_R)),&T\ne\varnothing. \end{cases}$$

先把递归定义写出来，再翻译成代码，比从指针语句开始拼更可靠。