数据结构：树和二叉树的概念和性质

前言

树（Tree）是数据结构中非常重要且基础的一类非线性结构。与线性结构（如数组、链表、栈、队列）不同，树结构中的数据元素之间存在明显的层次关系，例如现实生活中的家族谱系、公司组织架构、计算机中的文件系统，以及编译原理中的语法分析树，都可以用树这种结构来抽象和描述。

本文将从树的定义出发，系统梳理树的相关概念（如度、叶子结点、路径、高度等），再介绍树的重要性质，并进一步聚焦到最常用、最基础的二叉树，讲解二叉树的定义、几种特殊形态（满二叉树、完全二叉树、搜索二叉树）以及二叉树的核心性质。

1. 树的定义

树（Tree）是 n（n ≥ 0）个结点的有限集。当 n = 0 时，称为空树；当 n > 0 时，称为非空树。任意一棵非空树应该满足以下要求：

• a. 有且仅有一个特定的称为根的结点。
• b. 当 n > 1 时，其余结点可分为 m（m > 0）个互不相交的有限集 T1，T2，…，Tm，其中每个集合本身又是一棵树，并且称为根的子树。
  

树的根结点没有前驱结点，除根结点外的所有结点有且只有一个前驱结点，树中的所有结点可以有多个后继结点。

树（Tree）这个概念来源于现实世界中常见的树，都是从根开始生长，再长出很多子树。
树是一种递归定义的数据结构，树可以分成根和多棵子树，每棵子树又可以分为根和多棵子树。

2. 树的相关概念

2.1 结点间的关系描述

• 祖先：从根结点到该结点所经分支上的所有结点称为该结点的祖先。如：A 到 G 分支中，A 和 C 都是 G 的祖先。
• 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如：下面的所有结点都是 A 的子孙，C 的子孙只有 G。
• 孩子/双亲：结点所有子树的根结点称为该结点的孩子，相对应，该结点称为孩子的双亲。如：B 的孩子是 E 和 F，E 和 F 的双亲是 B。
• 兄弟：同一个双亲的孩子之间互称为兄弟。如：H 和 I 是兄弟结点，这里兄弟类似人类亲缘关系的亲兄弟。
• 堂兄弟：双亲在同一层的结点互为堂兄弟。如：G 和 H 是堂兄弟关系。

2.2 结点和树之间的属性描述

3. 树的性质

3.1 性质一：树中的结点数 = 所有结点的度数之和 + 1

这个点很好理解，一个结点的度就是这个结点有几个孩子结点，所有的度相加就是累计的孩子结点数，只有根结点没算进去，所以所有结点的度之和 + 1 就是结点数。有些地方也会说树中的结点数 = 所有边之和 + 1，因为一个结点连接出去的边等于这个结点的度。

3.2 性质二：m 叉树中第 i 层上至多有m i − 1 m^{i-1}mi−1个结点（i ≥ 1）

m 叉树是指每个结点最多 m 个孩子，最少可以是 0 个孩子，m 叉树中不一定存在 m 个孩子的结点。

极端场景下高度为 h 的 m 叉树叶子结点都在第 h 层，每个分支结点均有 m 个孩子，每层都是满的，假设层数是 i，则每层结点数为m i − 1 m^{i-1}mi−1，第 1 至 h 层的结点数是一个以 m 为公比的等比数列。

3.3 性质三：高度为 h 的 m 叉树至多有m h − 1 m − 1 \frac{m^h - 1}{m - 1}m−1mh−1​个结点

极端场景下高度为 h 的 m 叉树叶子结点均在第 h 层，每个分支结点均有 m 个孩子，每层都是结点数达到最大（满），假设层数是 i，则每层结点数为m i − 1 m^{i-1}mi−1，第 1 至 h 层的结点数是一个以 m 为公比的等比数列。
等比数列前 n 项和：S n = a 1 ⋅ 1 − q n 1 − q S_n = a_1 \cdot \frac{1 - q^n}{1 - q}Sn​=a1​⋅1−q1−qn​，其中a 1 a_1a1​为首项，q qq为公比，n nn是项数。
高度为 h 的 m 叉树最多结点数为：S_h = (m^h - 1) / (m - 1)。

4. 二叉树的定义

二叉树（Binary Tree）是另一种树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于 2 的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒（二叉树是有序树），左边的叫左子树，右边的叫右子树。

二叉树的度并不一定为 2，它要求每个结点度最大为 2，特殊情况下，树的度也可能为 0 或者 1。

二叉树也是一个递归定义的数据结构，任何一棵二叉树可以分为根和左右子树，非空的左右子树又可以分为根和左右子树。

5. 几个特殊的二叉树

5.1 满二叉树

一棵高度为 h 的二叉树，每层结点数都达到最大（满），合计有 2^h - 1 个结点的二叉树就叫满二叉树。

• 满二叉树的叶子结点都在最后一层，且分支结点的度均为 2。满二叉树是当前高度下二叉树结点数最大的形态。
• 等比数列前 n 项和：S_n = a1 * (1 - q^n) / (1 - q)，其中 a1 为首项，q 为公比，n 是项数。
• 高度为 h 的满二叉树的合计结点：S_n = 2^0 + 2^1 + 2^2 + … + 2^(h-1) = 2^h - 1。

5.2 完全二叉树

一棵高度为 h 的完全二叉树，前 h-1 层都是结点数达到最大（满），第 h 层不一定满，但是要求从左到右结点是连续的。

• 满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。
• 高度为 h 的完全二叉树的结点数量在 [2^(h-1), 2^h - 1] 之间。
• 完全二叉树的叶子一定只出现在最后两层，且度为 1 的结点最多有 1 个，剩下的结点都是度为 0 和度为 2。

5.3 搜索二叉树

二叉搜索树又称二叉排序树（它走中序遍历是有序的），它或者是一棵空树，或者是具有以下性质的二叉树：

• 若它的左子树不为空，则左子树上所有结点的值都小于根结点的值（实践中可变形为左子树上所有结点的值都小于等于根结点的值）。
• 若它的右子树不为空，则右子树上所有结点的值都大于根结点的值（实践中可变形为右子树上所有结点的值都大于等于根结点的值）。
• 它的左右子树也分别为二叉搜索树。

6. 二叉树的性质

6.1 性质一：在二叉树的第 i 层上至多有 2^(i-1) 个结点（i ≥ 1）

这个性质是前面「m 叉树中第 i 层上至多有 m^(i-1) 个结点」在 m = 2 时的特例。二叉树每个结点最多有 2 个孩子，极端情况下每层都达到最大结点数，则第 i 层上至多有 2^(i-1) 个结点。

6.2 性质二：高度为 h 的二叉树至多有 2^h - 1 个结点（h ≥ 1）

同理，这是「高度为 h 的 m 叉树至多有 (m^h - 1) / (m - 1) 个结点」在 m = 2 时的特例。当每层结点数都达到最大（即满二叉树）时，高度为 h 的二叉树结点总数最多，为 2^h - 1 个。

6.3 性质三：对任何一棵二叉树 T，如果其度为 0（叶子）结点数为 n0，度为 2 的结点数为 n2，则 n0 = n2 + 1

前面树的性质讲到，树中的结点数 = 所有结点的度数之和 + 1。假设树中结点总数为 m，度为 1 的结点数为 n1，则：

m = n1 + 2 n2 + 1

假设树中结点总数为 m，则 m = n0 + n1 + n2，化解一下可以推导出 n0 = n2 + 1，就是这个性质的结论。

6.4 性质四：具有 n 个结点的完全二叉树的高度为 ⌊log2 n⌋ + 1

• ⌊X⌋ 表示对 X 向下取整。
• 完全二叉树小节我们讲到，高度为 h 的完全二叉树的结点数量在 [2^(h-1), 2^h - 1] 之间，我们尝试把这个不等式调整一下变成 2^(h-1) ≤ n < 2^h，则 h - 1 ≤ log2 n < h，因为 h 是整数，所以 h = ⌊log2 n⌋ + 1。