树与二叉树

本节导读

树是数据结构里篇幅最大的一章，本节讲树的基本概念和二叉树，下一节讲树、森林和树的应用。大纲列的二叉树条目有：定义及主要特征、顺序存储与链式存储、遍历、线索二叉树的基本概念和构造。

这一节的选择题多是结点个数计算、遍历序列推导；综合应用题可能要写遍历或判断的算法。学完你应该能熟练用「度数之和 + 1 = 结点数」列方程，能由两种遍历序列画出二叉树，能写出二叉树遍历的递归代码。

树的基本概念

结点的度是它的孩子个数，树的度是各结点度的最大值；度为 0 的是叶结点，其余是分支结点。层次从根开始，本课约定根在第 1 层，树的高度（深度）是最大层数；有的教材让根在第 0 层，做题时看清题目的约定。路径长度按路径上的边数算。

树的几个基本性质（设树有 n 个结点）：

性质	内容
结点数与度数	n = 所有结点的度数之和 + 1（除根外每个结点都对应一条指向它的边）
度为 m 的树	第 i 层至多 $m^{i-1}$mi−1 个结点
高度为 h 的 m 叉树	至多 $\dfrac{m^h - 1}{m - 1}$m−1mh−1​ 个结点
n 个结点的 m 叉树	最小高度为 $\left\lceil \log_m(n(m-1)+1) \right\rceil$⌈logm​(n(m−1)+1)⌉

第一条最常用：设度为 0、1、2、…、m 的结点各有 $n_0, n_1, \dots, n_m$n0​,n1​,…,nm​ 个，则 $n_0 + n_1 + \dots + n_m = n_1 + 2n_2 + \dots + m n_m + 1$n0​+n1​+⋯+nm​=n1​+2n2​+⋯+mnm​+1。

二叉树及其性质

二叉树每个结点至多两个孩子，而且分左右，是有序树；度为 2 的有序树与二叉树不同——前者至少有一个结点有两个孩子，后者可以为空。

• 满二叉树：高度为 h 且有 $2^h - 1$2h−1 个结点。
• 完全二叉树：按层从上到下、每层从左到右编号 1 至 n，编号与同高度满二叉树一一对应。叶结点只出现在最后两层；度为 1 的结点至多 1 个，而且只有左孩子。

二叉树的主要性质：

性质	内容
叶结点与度为 2 的结点	$n_0 = n_2 + 1$n0​=n2​+1
第 i 层	至多 $2^{i-1}$2i−1 个结点
高度为 h	至多 $2^h - 1$2h−1 个结点
n 个结点的完全二叉树	高度为 $\left\lceil \log_2(n+1) \right\rceil$⌈log2​(n+1)⌉，也等于 $\lfloor \log_2 n \rfloor + 1$⌊log2​n⌋+1
完全二叉树的编号	结点 i 的双亲是 $\lfloor i/2 \rfloor$⌊i/2⌋，左孩子 2i、右孩子 2i + 1（不超过 n 才存在）

完全二叉树的叶结点数可以这样求：最后一个结点编号为 n，它的双亲 $\lfloor n/2 \rfloor$⌊n/2⌋ 是最后一个分支结点，所以分支结点有 $\lfloor n/2 \rfloor$⌊n/2⌋ 个，叶结点有 $n - \lfloor n/2 \rfloor$n−⌊n/2⌋ 个。

二叉树的存储结构

顺序存储：按完全二叉树的编号把结点放进数组。完全二叉树用它最省；一般二叉树要按完全二叉树补上空结点，最坏情况（每个结点都只有右孩子）高度为 h 时要用到编号 $2^h - 1$2h−1 的位置，非常浪费。

链式存储：二叉链表的结点含 lchild、data、rchild 三个域；n 个结点共有 2n 个指针域，其中 n − 1 个指向孩子，其余 n + 1 个为空。需要常找双亲时加一个 parent 域，叫三叉链表。

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode;
void PreOrder(BiTNode *T) {        /* 先序：根、左、右 */
    if (T != NULL) {
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

中序、后序只是把 visit 挪到两次递归调用之间或之后。三种遍历都是每个结点访问一次，时间复杂度 $O(n)$O(n)，递归栈的深度等于树高，空间复杂度 $O(h)$O(h)。

二叉树的遍历与构造

遍历	访问顺序	实现要点
先序	根、左子树、右子树	递归，或用栈：出栈即访问，先压右孩子再压左孩子
中序	左子树、根、右子树	递归，或用栈：一路向左压栈，出栈时访问并转向右子树
后序	左子树、右子树、根	递归，或用栈并记录上次访问的结点
层次	按层从上到下、从左到右	用队列：出队访问，左右孩子依次入队

由遍历序列确定二叉树：先序加中序、后序加中序、层次加中序都能唯一确定一棵二叉树；先序加后序不能（只有一个孩子时分不清是左是右）。做法是先用先序（或后序、层次）找根，再用中序把其余结点分成左右两部分，逐层递归。

线索二叉树

二叉链表里的 n + 1 个空指针可以利用起来：左指针为空时指向遍历序列中的前驱，右指针为空时指向后继，这样的指针叫线索。每个结点加两个标志位：ltag = 0 表示 lchild 指向左孩子，ltag = 1 表示指向前驱；rtag 同理。按某种遍历次序把空指针改成线索的过程叫线索化，中序线索化在中序遍历的过程中用一个 pre 指针记住刚访问过的结点即可。

在中序线索二叉树里找结点 p 的后继：rtag = 1 时后继就是 rchild；rtag = 0 时后继是右子树中最左下的结点。找前驱对称。先序线索树找前驱、后序线索树找后继时，要用到双亲，单靠二叉链表做不到，这是三种线索树的主要区别。

易错提醒

• ❌ 度为 2 的有序树就是二叉树。✅ 二叉树可以为空，左右子树严格区分；度为 2 的有序树至少有一个结点有两个孩子。因为二者的定义不同，只有一个孩子时二叉树还要分左右。

• ❌ 先序序列加后序序列也能唯一确定二叉树。✅ 必须有中序序列（或在其他附加条件下），先序加后序不能。因为根只有一个孩子时，分不清它是左孩子还是右孩子。

• ❌ 树的高度一律从 0 算起。✅ 按题目约定；本课约定根在第 1 层、高度等于层数。因为两种约定下同一棵树的高度差 1，代进公式结果就不同。

• ❌ 完全二叉树中可以有多个度为 1 的结点。✅ 至多一个，而且它只有左孩子。因为编号是连续的，缺孩子只可能发生在最后一个分支结点上。

• ❌ 在中序线索树中，有右孩子的结点，其后继就是右孩子。✅ 后继是右子树中最左下的结点。因为右孩子还可能有左子树，那些结点在中序里排在右孩子前面。

例题精讲

例题 1（计算）

一棵度为 4 的树中，度为 4、3、2、1 的结点分别有 2、3、1、4 个。问叶结点有多少个？

答题要点示范：度数之和 $4 \times 2 + 3 \times 3 + 2 \times 1 + 1 \times 4 = 23$4×2+3×3+2×1+1×4=23，结点总数 n = 23 + 1 = 24；分支结点 2 + 3 + 1 + 4 = 10 个，叶结点 24 − 10 = 14 个。

例题 2（由遍历序列构造）

二叉树的先序序列为 A B D G E C F，中序序列为 D G B E A F C。画出这棵二叉树，并写出后序序列。

答题要点示范：先序第一个 A 是根；中序里 A 左边的 D G B E 是左子树，右边的 F C 是右子树。左子树的先序是 B D G E，根为 B，中序 D G | B | E 说明 D G 在 B 左边、E 是 B 的右孩子；D G 的先序是 D G、中序也是 D G，所以 D 是 B 的左孩子、G 是 D 的右孩子。右子树先序 C F、中序 F C，C 为根，F 是 C 的左孩子。后序序列为 G D E B F C A。

点评：每一步都是「先序（或后序）定根，中序分左右」，写的时候把每一层的子序列都列出来，不容易乱。

例题 3（算法设计）

设问：二叉树用二叉链表存储，设计算法判断它是否为完全二叉树。

答题要点示范：

（1）设计思想：按层次遍历，空指针也入队。完全二叉树按层排列时，所有非空结点都在空结点之前；一旦出队了一个空结点，之后再出现非空结点就不是完全二叉树。

（2）算法：

#define MAXN 1000                  /* 足够大：入队次数不超过 2n + 1 */
int is_complete(BiTNode *T) {
    BiTNode *Q[MAXN];
    int front = 0, rear = 0, seen_null = 0;
    if (T == NULL) return 1;       /* 空树按完全二叉树处理 */
    Q[rear++] = T;
    while (front != rear) {
        BiTNode *p = Q[front++];
        if (p == NULL) {
            seen_null = 1;         /* 遇到了第一个空位 */
        } else {
            if (seen_null) return 0;   /* 空位之后又有结点 */
            Q[rear++] = p->lchild;
            Q[rear++] = p->rchild;
        }
    }
    return 1;
}

（3）每个结点和空指针各入队出队一次，时间复杂度 $O(n)$O(n)；队列最多存 2n + 1 个指针，空间复杂度 $O(n)$O(n)。

点评：关键是让空指针也入队，这样「编号连续」这条性质就变成了「空结点之后不能再有非空结点」，一遍层次遍历就能判断。

本节小结

• 树：结点数 = 度数之和 + 1；高度按题目约定，本课根在第 1 层。
• 二叉树：$n_0 = n_2 + 1$n0​=n2​+1，第 i 层至多 $2^{i-1}$2i−1 个，高 h 至多 $2^h - 1$2h−1 个；完全二叉树编号 i 的孩子是 2i、2i + 1，分支结点 $\lfloor n/2 \rfloor$⌊n/2⌋ 个。
• 存储：完全二叉树宜顺序存储；二叉链表 n 个结点有 n + 1 个空指针。
• 遍历：先序、中序、后序、层次，都是 $O(n)$O(n)；有中序才能与另一种序列唯一确定二叉树。
• 线索二叉树利用空指针指向前驱、后继，靠 ltag、rtag 区分孩子与线索。