前言
在接触树结构之前，我们学习的数据结构大多基于线性存储，如顺序表、链表、队列和栈。树结构则是我们认识的首个非线性数据结构，由 n(n≥0) 个有限节点组成，具有明显的层次关系。之所以称为'树'，是因为它的形态像一棵倒置的树，根在上而叶在下。
树的结构特征
现实生活中的树木通常呈现底部生根、顶部生叶的形态，而在数据结构中，树的结构呈现出根在上方、叶在下方的特点。
树的基本概念
树的定义
树是由 n（n>=0）个有限结点组成的一个具有层次关系的集合，需满足以下特征：
- 有一个特殊的结点，称为根结点，根结点没有前驱结点。
- 除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm，其中每一个集合又是一棵结构与树类似的子树。
- 每棵子树的根结点有且只有一个前驱，可以有 0 个或多个后继。
树的术语
通过下图可以直观理解树的相关概念：
- 树的节点：如 A、B、C 等字母代表树的各个节点，A 是树的根节点。
- 节点的度：一个结点含有的子树的个数称为该结点的度。例如节点 A 有 B、C、D 为根的子树，故 A 的度为 3。
- 叶子结点或终端结点：不含有子树的节点被称为叶节点（即度为 0 的结点），如 J、F、K、L、H、I。
- 双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点，如 A 是 B、C、D 的父节点。
- 孩子结点或子结点：与父节点相对应，如 B、C、D 是 A 的子节点。
- 树的度：树内所有结点中度数值最大的那个结点的度，即 max(所有结点的度)。
- 结点的层次：从根开始定义起，根为第 1 层，根的子结点为第 2 层，以此类推。
- 树的高度或深度：树中结点的最大层次。
- 森林：由 m（m>0）棵互不相交的树的集合称为森林。
树的存储
树结构相对线性表较为复杂，既要保存值，又要表示结点之间的关系。实际中常用的表示方法包括双亲表示法、孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。这里介绍一种最为常用的表示方法：孩子兄弟表示法。
typedef int DataType;
struct Node {
struct Node* firstChild; // 第一个孩子结点
struct Node* pNextBrother; // 指向其下一个兄弟结点
DataType data; // 结点中的数据域
};
二叉树
二叉树的概念
二叉树是一棵特殊的树，是一个 n(n>=0) 个节点的有限集合，具有以下特征：
- 每个结点至多只有两棵子树（即二叉树中不存在度大于 2 的结点）。
- 由一个根结点加上两棵别称为左子树和右子树的二叉树组成。
- 二叉树的子树有左右之分，其次序不能任意颠倒。
从上图可以看出，二叉树不存在度大于 2 的结点，且子树有左右之分，次序不能颠倒，因此二叉树是有序树。对于任意的二叉树都是由以下几种情况复合而成的。
特殊的二叉树
满二叉树
满二叉树指每一层的节点数量均达到最大值的二叉树。具体而言，若某二叉树的深度为 h，且其节点总数为 2^h - 1，则该树即为满二叉树。
对于一棵满二叉树而言，假设其高度为 h，节点总数为 N：
- 第一层有：2^0 个节点
- 第二层有：2^1 个节点
- ...
- 第 h 层有：2^(h-1) 个节点
总节点数 N = 2^0 + 2^1 + ... + 2^(h-1) = 2^h - 1。所以也可得出 h = log₂N + 1，对于一棵二叉树而言其深度可以被近似为 h ≈ log₂N。
完全二叉树
完全二叉树指除最后一层外，每一层的节点数均达到最大值，最后一层的节点从左到右连续排列，缺失的节点只能在右侧。
对于完全二叉树，满足如下特征：
- 叶子节点仅可能出现在最下两层，且最下层叶子一定靠左集中。
- 适合用数组存储，无需额外空间记录指针，通过索引即可计算父子节点位置。
- 不存在只有右子节点而无左子节点的节点，右子节点存在的前提是左子节点已存在。
注：满二叉树也被视为特殊的完全二叉树。
二叉树的性质
二叉树的性质围绕节点数、深度、子树关系及特殊类型展开，核心是'每个节点最多 2 个子节点'的结构约束。
所有二叉树的性质
-
节点数与度数关系：若总节点数为 N，度为 0（叶子）、1、2 的节点数分别为 n₀、n₁、n₂，则 N = n₀ + n₁ + n₂，且 n₀ = n₂ + 1（叶子节点数比度为 2 的节点数多 1）。
推导过程：假设二叉树有 N 个结点。从总结点数角度考虑：N = n0 + n1 + n2。从边的角度考虑：N 个结点的任意二叉树，总共有 N-1 条边。因为度为 0 的结点不产生边；度为 1 的结点产生一条边；度为 2 的结点产生两条边，所以总边数为 n1 + 2n2。故 N-1 = n1 + 2n2。结合两式得：n0 + n1 + n2 - 1 = n1 + 2*n2，即 n0 = n2 + 1。
-
深度与节点数上限：若深度为 k（根节点深度为 1），则该二叉树最多有 2ᵏ - 1 个节点（满二叉树的情况），最少有 k 个节点。
最多节点：第 1 层最多 2^0，第 2 层最多 2^1...第 k 层最多 2^(k-1)。总数 N = 2^0 + ... + 2^(k-1) = 2^k - 1。 最少节点：每层只有一个节点，则 k 层有 k 个节点。
-
层数与节点分布：第 k 层（根为第 1 层）最多有 2^(k-1) 个节点，最少有 1 个节点。
满二叉树的性质
- 所有层的节点数均达到最大值，即第 k 层有 2^(k-1) 个节点，总节点数 n = 2ᵏ - 1。
- 叶子节点全部在最底层，且不存在度为 1 的节点（n₁ = 0），叶子节点数 n₀ = 2ᵏ⁻¹。
- 假设树的深度 k，则总节点数 n = 2ᵏ - 1，深度 k ≈ log₂n。
完全二叉树的性质
- 节点总数 n 满足 (2ᵏ⁻¹ - 1) + 1 <= n <= 2ᵏ - 1，深度 k ≈ log₂n。
- 数组存储索引规则：
- 父节点 i 的左子节点为 2i、右子节点为 2i+1。
- 子节点 j 的父节点为 j / 2（索引从 1 开始）。
- 叶子节点索引范围为 n/2 + 1 到 n，非叶子节点为 1 到 n/2，无'只有右子节点'的情况。
- 对于完全二叉树，度为 1 的节点：只有 1 个或者 0 个。
树与二叉树的转换
普通树转换为二叉树
核心方法
- 加线（连兄弟）：在所有兄弟节点之间加一条连线。
- 抹线（断父子）：保留最左边的孩子（长子），抹掉其他孩子。
- 旋转（理层次）：以树的根节点为轴心，将整棵树顺时针旋转 45 度，使其看起来像一棵标准的二叉树。
简记：兄弟相连留长子。
图解演示
如图所示一棵普通树：
操作一：兄弟间加线
操作二：保留长子
操作三：以根为轴心顺时针旋转 45°
二叉树转换为普通树
核心方法
- 加线（认父亲）：对于某个节点（比如 P），如果它有左孩子（L），那么把 L 的所有右链上的节点（即 L 的兄弟们），都与 P 用线连起来。
- 抹线（断兄弟）：抹掉二叉树中所有节点与它右孩子之间的连线。
- 旋转（理层次）：整理结构，使其恢复为普通树的层次。
简记：左孩右右连双亲，去掉原来右孩线。
图解演示
如图所示有一棵二叉树：
操作一：加线（认父亲）
操作二：抹线（断兄弟）
操作三：旋转（理层次）
森林转换为二叉树
核心方法
- 各树自转：先把森林中的每一棵树，各自转换为二叉树。
- 根根相连：将每棵树的根节点用线连起来。
- 唯一树根：第一棵树的根节点，就是转换后整棵二叉树的根节点。
简记：树变二叉，根相连。
图解演示
如图所示有如下森林：
操作一：各树自转
操作二：根根相连
操作三：唯一树根
二叉树转换为森林
核心方法
- 抹线（断开树与树的联系）：沿着二叉树根节点的右链一直走下去，把这根链上的所有连线全部剪断。
- 提取（确定每棵树的根）：断开后，右链上的每一个节点，现在都成为了独立的二叉树的根节点。
- 还原（各自变回普通树）：对这散落出来的每一棵小二叉树，分别执行'二叉树转普通树'的操作。
简记：去掉根部右孩线，孤立二叉再还原。
图解演示
如图所示一棵二叉树：
操作一：抹线（断开树与树的联系）
操作二：提取（确定每棵树的根）
操作三：还原（各自变回普通树）
实战练习
试题一
题目：某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ） A. 不存在这样的二叉树 B. 200 C. 198 D. 199
解析：对于任何一棵二叉树，都满足这样一个性质：n0（度为 0 的节点）= n2（度为 2 的节点）+ 1。故而叶子节点（即度为 0 的节点）个数为：199 + 1 = 200。选项 B 符合题意。
试题二
题目：下列数据结构中，不适合采用顺序存储结构的是（ ） A. 非完全二叉树 B. 堆 C. 队列 D. 栈
解析：
- B. 堆：基于完全二叉树连续排列的特性，故而可以采用顺序结构存储。
- C. 队列：对于循环队列采用顺序存储结构。
- D. 栈：一般基于数组实现，采用顺序结构。 答案为：A。
试题三
题目：在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ） A. n B. n+1 C. n-1 D. n/2
解析：对于任何一棵二叉树而言其节点总数 N，由度为 0 的节点、度为 1 的节点、度为 2 的节点所组成，N = n0 + n1 + n2。任意一棵二叉树满足如下性质：n0 = n2 + 1。故而 2n = n0 + n1 + n0 - 1。当且仅当 n1 = 1 时左边为偶数，且右边为偶数，所以 n0 = n。答案为：A。
试题四
题目：一棵完全二叉树的结点数为 531 个，那么这棵树的高度为（ ） A. 11 B. 10 C. 8 D. 12
解析：对于一棵完全二叉树而言，假设这棵树的高度为 k，则其节点的范围：2^(k-1) ~ 2^k - 1。2^9 = 512, 2^10 = 1024。531 介于 512 和 1023 之间，故高度为 10。答案为：B。
试题五
题目：一个具有 767 个结点的完全二叉树，其叶子结点个数为（） A. 383 B. 384 C. 385 D. 386
解析：对于任何一棵二叉树而言其节点总数 N，由度为 0 的节点、度为 1 的节点、度为 2 的节点所组成，N = n0 + n1 + n2。任意一棵二叉树满足如下性质：n0 = n2 + 1。对于 N = 767，则有 767 = n0 + n1 + n0 - 1。当且仅当 n1 等于 0 时，才满足左右两边为奇数，所以 n1 = 0。n0 = (767 + 1) / 2 = 384。答案为：B: n0 = 384。
