Lecture 15：树与二叉树

15.1 树的基本概念

15.1.1 什么是树

定义：#树

描述： 树是 $n(n\ge 0)$ 个结点的有限集合。当 $n=0$ 时，称为空树；任意一棵非空树有且仅有一个根结点，其余结点可划分为若干棵互不相交的子树。

直观理解

• 树从树根开始生长。
• 从上到下逐级分支。
• 树是一种层次结构。

空树

• 结点数为 $0$ 的树称为空树。

非空树必须满足

1. 有且仅有一个特定的结点，称为根。
2. 当 $n>1$ 时，其余结点可以分为 $m(m>0)$ 个互不相交的有限集合： $$ T_1,T_2,\cdots,T_m $$ 其中每个集合本身又是一棵树，并称为根结点的子树。

解释

• 子树之间互不相交。
• 每棵子树还可以继续看成新的树。
• 这种递归定义是树结构的重要特征。

15.1.2 叶子结点和分支结点

定义：#叶子结点

描述： 没有后继的结点称为叶子结点，也称终端结点。

定义：#分支结点

描述： 有后继的结点称为分支结点，也称非终端结点。

注意

• PDF 中“叶子结点也称非终端结点”应理解为 OCR 或口误。
• 标准说法是：
  • 叶子结点：终端结点；
  • 分支结点：非终端结点。

15.1.3 树的基本特性

• 除根结点外，任何一个结点都有且仅有一个前驱。
• 每个结点可以有 $0$ 个或多个后继。
• 根结点没有前驱。
• 叶子结点没有后继。

15.2 结点和树的属性

15.2.1 路径和路径长度

定义：#路径

描述： 在把父子关系看作有方向时，祖先到后代的有向路径只能沿边向下；若忽略边的方向，则树中任意两个结点之间都存在且仅存在一条简单路径。

路径长度

• 路径长度是路径上经过的边数。

15.2.2 层次、深度和高度

结点的层次

• 结点从上往下数所在的层。
• 默认根结点层次为： $$ 1 $$

结点的深度

• 若按层数计，结点深度就是结点所在层次，根结点深度为 $1$。
• 也有教材按边数计深度，此时根结点深度为 $0$。做题时必须先确认题目的计数口径。

结点的高度

• 按层数计，是从该结点向下到最深叶子结点的最长路径所含结点数，叶子结点高度为 $1$。
• 若题目按边数计，则上述数值整体减 $1$。

树的高度

• 树总共有多少层。
• 也称树的深度。

15.2.3 结点的度和树的度

定义：#结点的度

描述： 结点的度是该结点拥有的孩子个数，也就是分支数。

定义：#树的度

描述： 树的度是树中各结点的度的最大值。

例子

• 若结点 B 有 $2$ 个孩子，则： $$ d(B)=2 $$
• 若结点 D 有 $3$ 个孩子，则： $$ d(D)=3 $$
• 若整棵树中最大结点度为 $3$，则树的度为： $$ 3 $$

15.2.4 有序树和无序树

定义：#有序树

描述： 若树中结点的各棵子树从左到右有次序，不能互换，则称为有序树。

定义：#无序树

描述： 若树中结点的各棵子树从左到右无次序，可以互换，则称为无序树。

15.2.5 树的路径长度

定义

• 树的路径长度是根结点到每个结点路径长度的总和。

读图说明

• A 的度为 $3$，B 的度为 $2$，D 的度为 $3$，所以整棵树的度为 $3$。
• F、G、I、J、K、L、M 的度为 $0$，都是叶子结点。
• 从根 A 到 M 的有向路径为 A-D-H-M，包含 $3$ 条边，因此路径长度为 $3$。

15.3 森林

定义：#森林

描述： 森林是 $m(m\ge 0)$ 棵互不相交的树的集合。

解释

• 当 $m=0$ 时，森林为空。
• 一棵树也可以看作只有一棵树的森林。
• 树删去根结点后，其若干棵子树可以构成森林。

读图说明

• 删除原树的根 A 以及与 A 相连的边后，得到以 B、C、D 为根的三棵互不相交的树，这三棵树组成森林。

15.4 树的常考性质

15.4.1 结点度与总结点数

设：

• $n$ 表示总结点数。
• $n_i$ 表示度为 $i$ 的结点数。
• $m$ 表示树的度。

总结点数 所有结点按度分类： $$ n=n_0+n_1+n_2+\cdots+n_m $$

总度数 树中所有结点的度数之和为： $$ 0\cdot n_0+1\cdot n_1+2\cdot n_2+\cdots+m\cdot n_m $$

树中每条边都对应一个孩子关系，因此： $$ \text{总度数}=n-1 $$

所以： $$ n=1+\sum_{i=1}^{m}i n_i $$

为什么要加 $1$

• 除根结点外，每个结点都有且仅有一个父结点。
• 每个非根结点都对应一条边。
• 根结点没有父结点，所以总结点数比总度数多 $1$。

15.4.2 叶子结点个数公式

由： $$ n=n_0+n_1+n_2+\cdots+n_m $$

以及： $$ n=1+n_1+2n_2+\cdots+mn_m $$

两式相减可得： $$ n_0=\sum_{i=2}^{m}(i-1)n_i+1 $$

含义

• 叶子结点数 $n_0$ 可以由各类分支结点数量推出。
• 度为 $1$ 的结点不影响叶子结点数量公式。

15.4.3 边数公式

树 一棵有 $n$ 个结点的树，有： $$ n-1 $$ 条边。

森林 若森林中共有 $k$ 棵树，则： $$ \text{结点数}-\text{边数}=k $$

也就是： $$ \text{森林数}=\text{结点数}-\text{边数} $$

15.5 度为 m 的树和 m 叉树

15.5.1 定义区别

定义：#度为m的树

描述： 度为 $m$ 的树是指树中各结点度的最大值为 $m$，并且至少存在一个结点的度为 $m$。

定义：#m叉树

描述： $m$ 叉树是指每个结点最多只有 $m$ 个孩子的树。

15.5.2 对比表

结论

• 当 $m\ge 1$ 时，度为 $m$ 的树一定是 $m$ 叉树，但 $m$ 叉树未必存在度为 $m$ 的结点，因此前者是后者的真子集。

读图说明

• 左图至少有一个结点的度恰为 $3$，所以是度为 $3$ 的树。
• 中图每个结点的度都不超过 $3$，即使没有结点的度恰为 $3$，仍然是 3 叉树。
• 右图说明 3 叉树允许为空树，而“度为 3 的树”必须非空且必须出现度为 $3$ 的结点。

15.6 m 叉树的常考性质

15.6.1 第 i 层最多结点数

度为 $m$ 的树第 $i$ 层至多有： $$ m^{i-1} $$ 个结点，其中： $$ i\ge 1 $$

$m$ 叉树同理。

上述结论按根为第 $1$ 层计，且 $m\ge 1$。

解释

• 第 $1$ 层最多： $$ m^0=1 $$
• 第 $2$ 层最多： $$ m^1=m $$
• 第 $3$ 层最多： $$ m^2 $$

读图说明

• 要让第 $i$ 层结点数达到上界，前 $i-1$ 层中的每个非叶结点都必须产生 $m$ 个孩子，于是各层上界依次为 $m^0,m^1,\ldots,m^{i-1}$。

15.6.2 高度为 h 的 m 叉树最多结点数

当 $m\ge 2$ 时，高度为 $h$ 的 $m$ 叉树至多有： $$ \frac{m^h-1}{m-1} $$ 个结点。

推导 最多结点数是每一层最多结点数累加： $$ m^0+m^1+m^2+\cdots+m^{h-1} $$

由等比数列求和： $$ m^0+m^1+\cdots+m^{h-1}=\frac{m^h-1}{m-1} $$

当 $m=1$ 时，树退化为链，高度为 $h$ 时最多有 $h$ 个结点，不能代入分母为 $m-1$ 的公式。

15.6.3 高度为 h 的 m 叉树最少结点数

高度为 $h$ 的 $m$ 叉树至少有： $$ h $$ 个结点。

解释

• 要有高度 $h$，至少需要一条长度为 $h-1$ 的链。
• 每层至少一个结点。

15.6.4 高度为 h、度为 m 的树最少结点数

当 $m\ge 1$ 且存在这样的树时，高度为 $h$、度为 $m$ 的树至少有： $$ h+m-1 $$ 个结点。

解释

• 要让树的度为 $m$，至少要有一个结点拥有 $m$ 个孩子。
• 要让高度为 $h$，还要形成一条高度为 $h$ 的路径。
• 两个条件合并后，最少结点数为： $$ h+m-1 $$

适用条件

• 当 $m\ge 1$ 时，树中必须至少有父子两层，因此还需 $h\ge 2$。
• $m=0$ 时只有单结点树，此时 $h=1,n=1$，应单独处理。

15.6.5 n 个结点的 m 叉树最小高度

当 $m\ge 2,n\ge 1$ 时，具有 $n$ 个结点的 $m$ 叉树，其最小高度为： $$ \left\lceil \log_m\big(n(m-1)+1\big)\right\rceil $$

原因

• 高度最小时，应让树尽量“满”。
• 也就是让靠上的层次优先达到容量上限；最后一层可以不满，并不要求每个非叶结点都恰有 $m$ 个孩子。
• 高度为 $h$ 的 $m$ 叉树最多有： $$ \frac{m^h-1}{m-1} $$ 个结点。
• 要容纳 $n$ 个结点，需要： $$ n\le \frac{m^h-1}{m-1} $$
• 解得： $$ h\ge \log_m\big(n(m-1)+1\big) $$
• 因为高度是整数，所以取上整。

当 $m=1$ 时，非空树只能是一条链，最小高度就是 $n$；空树的高度按本笔记约定为 $0$。

15.7 题型整理

题型：#树的结点度计算

第一部分：解题方法

• 先按结点度分类，写出 $n_0,n_1,n_2,\cdots,n_m$。
• 用总结点数公式： $$ n=n_0+n_1+\cdots+n_m $$
• 用总度数公式： $$ n-1=\sum_{i=1}^{m}i n_i $$
• 求叶子结点数时使用： $$ n_0=\sum_{i=2}^{m}(i-1)n_i+1 $$

第二部分：典型例题

例题：一棵树中度为 2 的结点有 5 个，度为 3 的结点有 2 个，求叶子结点数。

代入公式： $$ n_0=(2-1)n_2+(3-1)n_3+1 $$

$$ n_0=1\times5+2\times2+1=10 $$

所以叶子结点数为： $$ 10 $$

第三部分：知识点复盘

• 树的总度数等于边数。
• 树的边数等于结点数减 $1$。
• 叶子结点公式来自总结点数和总度数两个式子相减。

题型：#m叉树高度

第一部分：解题方法

• 求最多结点数，用： $$ \frac{m^h-1}{m-1} $$
• 求最小高度，用： $$ \left\lceil \log_m\big(n(m-1)+1\big)\right\rceil $$
• 求第 $i$ 层最多结点数，用： $$ m^{i-1} $$

第二部分：典型例题

例题：高度为 4 的 3 叉树最多有多少个结点？

代入： $$ \frac{3^4-1}{3-1}=\frac{81-1}{2}=40 $$

所以最多有： $$ 40 $$ 个结点。

第三部分：知识点复盘

• 高度最小，要尽量满。
• 结点最多，也是尽量满。
• 高度至少，要形成一条链。

相关知识

• 科目导航：数据结构导航
• 阅读顺序：上一篇：KMP 算法 · 下一篇：二叉树常考性质
• 关联专题：二叉树代码

15.8 本节复盘

必须掌握

• 树是递归定义的层次结构。
• 空树是结点数为 $0$ 的树。
• 非空树有且仅有一个根结点。
• 除根结点外，每个结点有且仅有一个前驱。
• 结点的度是孩子个数。
• 树的度是各结点度的最大值。
• 树有 $n$ 个结点，则有 $n-1$ 条边。
• 森林满足： $$ \text{结点数}-\text{边数}=\text{森林数} $$
• 叶子结点数： $$ n_0=\sum_{i=2}^{m}(i-1)n_i+1 $$
• 当 $m\ge 2$ 时，高度为 $h$ 的 $m$ 叉树最多结点数： $$ \frac{m^h-1}{m-1} $$
• 当 $m=1$ 时，树退化为链，最多有 $h$ 个结点。

易错点

• 叶子结点是终端结点，不是非终端结点。
• 树的层次默认从 $1$ 开始。
• 度为 $m$ 的树必须至少有一个结点度为 $m$。
• $m$ 叉树不一定有度为 $m$ 的结点。
• $m$ 叉树可以为空树，度为 $m$ 的树不可以。
• 求最小高度要取上整。

一句话总结

• 树的核心是“一个根、多棵互不相交子树”的递归结构，常考度数、边数、叶子数和 $m$ 叉树高度公式。