502 二叉树的概念

二叉树的概念

二叉树

二叉树的定义

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

与树相似，二叉树也以递归的形式定义。二叉树是 $n(n\ge 0)$ 个结点的有限集合：

1. 或者为空二叉树，即 $n=0$。
2. 或者由一个根结点和两个互不相交的、被称为根的左子树和右子树组成。左子树和右子树也分别是一棵二叉树。

核心特性：二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树的 5 种基本形态：

• 空二叉树：不含任何结点的树。
• 只有根结点：树中只有一个结点。
• 只有左子树：根结点只有左子树，右子树为空。
• 左右子树都有：根结点既有左子树又有右子树。
• 只有右子树：根结点只有右子树，左子树为空。

二叉树与度为 2 的有序树的区别

二叉树和树是两种不同的数据结构，即使是与限制最严格的“度为 2 的有序树”相比，也存在本质区别。

区别点	二叉树	度为 2 的有序树
次序的性质	绝对次序：严格区分左右子树。若某结点只有一个孩子，必须指明其为左孩子或右孩子。	相对次序：孩子的次序是相对于其他兄弟而言的。若某结点只有一个孩子，则它就是“第一个孩子”，无左右之分。
空结构	可以为空。	不能为空，至少有一个根结点。（度为 2 的树至少有 3 个结点）
数据结构归属	一种独立的、定义严格的数据结构。	树的特殊情况，是树的子集。

满二叉树

高度为 $h$，有 $2^h-1$ 个结点，所有分支结点都有左右子树。

完全二叉树

除最后一层外，所有层都满，最后一层结点集中在左侧。

二叉排序树 (Binary Search Tree, BST)

• 定义：二叉排序树，也称为二叉查找树或有序二叉树，它或者是一棵空树，或者具有下列性质的二叉树：

1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。
2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
3. 它的左、右子树也分别为二叉排序树。
4. 树中不存在键值相等的结点（这是常见定义，但有些实现允许重复值，通常放在右子树）。

• 特点：这种结构使得查找、插入和删除操作的平均时间复杂度为 $O(\log n)$，但在最坏情况下（例如，树退化成链表）可能达到 $O(n)$。

平衡二叉树 (Balanced Binary Tree)

• 定义：平衡二叉树是一种特殊的二叉排序树，其主要目标是维持树的高度尽可能小，从而保证操作的效率。严格来说，“平衡”可以有多种定义，但通常指满足以下条件的二叉树：

1. 它首先是一棵二叉排序树。
2. 对于树中的任意结点，其左子树和右子树的高度差的绝对值不超过某个阈值（通常是 1）。

• 常见类型：
• AVL 树：最早提出的自平衡二叉搜索树，要求任何结点的左右子树高度差的绝对值不超过 1。
• 红黑树：另一种自平衡二叉搜索树，通过对结点着色（红或黑）并满足特定性质来维持平衡，其平衡条件不如 AVL 树严格，但插入删除操作的调整（旋转）次数相对较少。
• 特点：通过在插入和删除结点后进行必要的调整（如旋转操作），平衡二叉树能够确保其高度大约是 $O(\log n)$，从而保证查找、插入和删除等操作的最坏时间复杂度也是 $O(\log n)$。

正则二叉树 (Regular Binary Tree / Full Binary Tree / Proper Binary Tree)

• 定义：正则二叉树，也常被称为满二叉树（Full Binary Tree，但注意这里的“满”与之前提到的“所有分支结点都有左右子树且所有叶子在同一层”的“满二叉树”定义不同，后者有时称为“完美二叉树 Perfect Binary Tree”），或严格二叉树 (Strictly Binary Tree)，或2- 树。其定义为：树中的每个结点要么是叶子结点（没有孩子），要么恰好有两个孩子结点。换句话说，不存在只有一个孩子的结点。
• 特点：
• 如果一个正则二叉树有 $i$ 个内部结点（度为 2 的结点），那么它有 $i+1$ 个叶子结点。
• 总节点数 $n=2i+1$。
• 叶节点数 $n_0=n_2+1$，这与所有二叉树的性质一致，因为在正则二叉树中 $n_1=0$。

主要性质

基本性质

• 叶子结点的个数：非空二叉树上的叶子结点数 $n_0=n_2+1$，其中 $n_2$ 为度为 2 的结点数。 推导：属于 一般树主要性质叶子结点数的推论。设度为 $1$ 的结点数为 $n_1$，则：

  • 总结点数：$n=n_0+n_1+n_2$
  • 总边数：$n-1=0\cdot n_0+1\cdot n_1+2\cdot n_2=n_1+2n_2$ 消元得：$n_0=n_2+1$

• 层与结点数：非空二叉树的第 $i$ 层最多有 $2^{i-1}$ 个结点。 推导：取 $m=2$ 的特殊情况。

• 最大结点数：高度为 $h$ 的二叉树最多有 $2^h-1$ 个结点。 推导：${\sum }_{i=1}^h{2}^{i-1}=2^h-1$（等比数列求和）。

• 完全二叉树高度：包含 $n$ 个结点的完全二叉树高度为 $\lfloor {\log }_2(n)\rfloor +1$。 推导：设高度为 $h$，则 $2^{h-1}-1<n\le 2^h-1$，故 $h-1<{\log }_2(n+1)\le h$，即 $h=\lfloor {\log }_2(n)\rfloor +1$ 或 $h=\lceil {\log }_2(n+1)\rceil$。

• 链式存储的二叉树空指针个数：$n$ 个结点的二叉树有 $n+1$ 个空指针。 推导：总指针数为 $2n$，非空指针数为 $n-1$（树的边数），故空指针数为 $2n-(n-1)=n+1$。

完全二叉树

层序编号

完全二叉树按层序从 $1$ 开始编号，具有以下重要性质：

1. 双亲与孩子结点的编号关系：

   • 双亲结点：编号为 $i$（$i>1$）的结点，其双亲结点编号为 $\lfloor i/2\rfloor$。
   • 左孩子：编号为 $i$ 的结点，若有左孩子，则左孩子编号为 $2i$。
   • 右孩子：编号为 $i$ 的结点，若有右孩子，则右孩子编号为 $2i+1$。 推导：层序编号按层从左到右递增，每层结点数为 $2^{k-1}$（第 $k$ 层）。若父结点编号为 $i$，其在该层的位置决定了子结点在下一层的位置，遵循 $2i$ 和 $2i+1$ 的规律。

2. 结点 $i$ 所在的层次： 编号为 $i$ 的结点位于第 $\lfloor {\log }_{2}i\rfloor +1$ 层。 推导：第 $k$ 层的结点编号范围为 $[2^{k-1},2^k-1]$。若 $2^{k-1}\le i\le 2^k-1$，则 $k-1\le {\log }_{2}i<k$，故 $k=\lfloor {\log }_{2}i\rfloor +1$。

3. 子结点存在性判断：

   • 左孩子存在性：$2i\le n$
   • 右孩子存在性：$2i+1\le n$
   • 叶子结点判断：$i>\lfloor n/2\rfloor$（等价于 $2i>n$）
   • 分支结点判断：$i\le \lfloor n/2\rfloor$（等价于 $2i\le n$）

4. 关键结点标识：

   • 最后一个非叶子结点：编号为 $\lfloor n/2\rfloor$
   • 第一个叶子结点：编号为 $\lfloor n/2\rfloor +1$ 推导：设最后一个非叶子结点编号为 $k$，则 $k$ 有孩子但 $k+1$ 无孩子，即 $2k\le n<2(k+1)$，解得 $k=\lfloor n/2\rfloor$。

5. 最后一个结点的位置特性：

   • 若 $n$ 为偶数：结点 $n$ 是结点 $n/2$ 的左孩子
   • 若 $n$ 为奇数且 $n>1$：结点 $n$ 是结点 $(n-1)/2$ 的右孩子 推导：由孩子编号公式，若 $n=2k$，则 $n$ 是 $k$ 的左孩子；若 $n=2k+1$，则 $n$ 是 $k$ 的右孩子。

性质	公式/条件	说明
双亲结点编号	$\lfloor i/2\rfloor$ $(i>1)$	根结点无双亲
左孩子编号	$2i$ $(2i\le n)$	超出范围则无左孩子
右孩子编号	$2i+1$ $(2i+1\le n)$	超出范围则无右孩子
所在层数	$\lfloor {\log }_{2}i\rfloor +1$	根结点在第 1 层
叶子结点判断	$i>\lfloor n/2\rfloor$	无任何孩子
分支结点判断	$i\le \lfloor n/2\rfloor$	至少有左孩子
最后非叶子结点	$\lfloor n/2\rfloor$	堆化操作起始点

应用示例：

• 结点 5：双亲为 $\lfloor 5/2\rfloor =2$，左孩子为 $10$（若 $n\ge 10$），右孩子为 $11$（若 $n\ge 11$）
• 在 $n=10$ 的完全二叉树中：最后非叶子结点为 $\lfloor 10/2\rfloor =5$，叶子结点为 $6,7,8,9,10$

高度、结点数相关讨论

叶节点的位置

• 可能在同一层：当最后一层被完全填满时
• 可能在最后一层和倒数第二层：当最后一层未被完全填满时

叶节点个数的奇偶性

• 可能为奇数——最后一个分支节点只有一个左孩子
• 可能为偶数——最后一个分支节点有两个孩子或没有孩子

分支节点与叶节点关系

• 设叶节点个数为 $n_0$，度为 1 的节点个数为 $n_1$，度为 2 的节点个数为 $n_2$
• 总节点数：$n=n_0+n_1+n_2$
• 完全二叉树中：$n_1=0$ 或 $n_1=1$
• 关系式：$n_0=n_2+1$（当 $n_1=0$ 时）或 $n_0=n_2$（当 $n_1=1$ 时）

常见类型

1. 已知高度求最多节点

   • 高度为 $h$ 的完全二叉树最多节点数：$2^h-1$
   • 此时为满二叉树

2. 已知高度求最少节点

   • 高度为 $h$ 的完全二叉树最少节点数：$2^{h-1}$
   • 此时最后一层只有一个节点（根的情况）

3. 已知节点求最大高度

   • $n$ 个节点的完全二叉树最大高度：$\lfloor {\log }_{2}n\rfloor +1$
   • 当树退化为最 ” 瘦 ” 的完全二叉树时

4. 已知节点求最小高度

   • $n$ 个节点的完全二叉树最小高度：$\lceil {\log }_2(n+1)\rceil$
   • 当树尽可能 ” 胖 ” 时（接近满二叉树）

5. 已知叶节点求最多节点

   • 设叶节点数为 $n_0$
   • 当 $n_0$ 为奇数时：总节点数 $=2n_0-1$（此时 $n_1=1$）
   • 当 $n_0$ 为偶数时：总节点数 $=2n_0$（此时 $n_1=0$）

6. 已知叶节点求最少节点

   • 叶节点数为 $n_0$ 时，最少总节点数 $=2n_0-1$
   • 此时完全二叉树尽可能 ” 高瘦 ”

重要性质总结

• 完全二叉树的节点按层序编号时，对于编号为 $i$ 的节点：
  • 左孩子编号：$2i$（如果存在）
  • 右孩子编号：$2i+1$（如果存在）
  • 父节点编号：$\lfloor i/2\rfloor$（$i>1$ 时）
• 具有 $n$ 个节点的完全二叉树高度为 $\lfloor {\log }_{2}n\rfloor +1$

k 叉树

一般 k 叉树

基本定义

• k 叉树：每个节点最多有 k 个子节点的树
• 度数限制：节点的度 ≤ k
• 特殊情况：k=2 时为二叉树，k=3 时为三叉树

节点关系

• 设总节点数为 n，度为 i 的节点数为 $n_i$（i = 0,1,2,…,k）
• 总节点数：$n=n_0+n_1+n_2+...+n_k$
• 边数关系：$n-1=1\cdot n_1+2\cdot n_2+...+k\cdot n_k$
• 叶节点与分支节点关系：$n_0=1+(k-1)(n_2+n_3+...+n_k)+(k-2)n_1$

高度与节点关系

• 高度为 h 的 k 叉树：
  • 最少节点数：h 个（退化为链状）
  • 最多节点数：$\frac{k^h-1}{k-1}$（满 k 叉树）
• n 个节点的 k 叉树：
  • 最小高度：$\lceil {\log }_k((k-1)n+1)\rceil$
  • 最大高度：n

k 叉正则树

定义特征

• 每个分支节点的度数相同且等于 k
• 只存在度为 0 和度为 k 的节点
• 即：$n_1=n_2=...=n_{k-1}=0$

节点关系

• 设度为 k 的节点数为 $n_k$，叶节点数为 $n_0$
• 总节点数：$n=n_0+n_k$
• 边数关系：$n-1=k\cdot n_k$
• 关键公式：$n_0=(k-1)\cdot n_k+1$

重要性质

• 叶节点数 $n_0$ 与分支节点数 $n_k$ 的关系固定
• 总节点数：$n=n_0+\frac{n_0-1}{k-1}=\frac{k\cdot n_0-1}{k-1}$
• 当 k=2 时，退化为正则二叉树：$n_0=n_2+1$

k 叉满树

定义特征

• 所有分支节点的度数都等于 k
• 所有叶节点都在同一层（最后一层）
• 是 k 叉正则树的特殊情况

结构性质

• 高度为 h 的 k 叉满树节点数：$\frac{k^h-1}{k-1}$
• 最后一层叶节点数：$k^{h-1}$
• 前 h-1 层节点数：$\frac{k^{h-1}-1}{k-1}$

层次分布

• 第 i 层节点数：$k^{i-1}$（i = 1,2,…,h）
• 前 i 层节点总数：$\frac{k^i-1}{k-1}$

与其他树的关系

• k 叉满树 ⊆ k 叉正则树 ⊆ k 叉树
• 满足最严格的结构约束
• 具有最大的节点密度和最小的高度

常用计算公式

• 已知叶节点数 $n_0$：总节点数 $n=\frac{k\cdot n_0-1}{k-1}$
• 已知高度 h：叶节点数 $n_0=k^{h-1}$，总节点数 $n=\frac{k^h-1}{k-1}$
• 已知总节点数 n：高度 $h={\log }_k((k-1)n+1)$

叶子结点数公式推导

在二叉树中，节点度数最多为 $2$，设 $n_0$、$n_1$、$n_2$ 分别为度数为 $0$、$1$、$2$ 的节点数量：

$$n_0=n_2+1$$

推导：

• 总节点数：$n=n_0+n_1+n_2$
• 握手定理：$n_1+2n_2=2(n-1)$
• 代入得：$n_1+2n_2=2(n_0+n_1+n_2-1)$
• 化简：$n_1+2n_2=2n_0+2n_1+2n_2-2$
• 整理：$n_0=n_2+1$

特殊情况

• 满二叉树：所有内部节点度数为 $2$，即 $n_1=0$，此时 $n_0=n_2+1$ 仍然成立。
• k 叉树：当所有内部节点度数为 $k$ 时，$n_0=(k-1)n_k+1$。

二叉树的存储结构

顺序存储

顺序存储结构是使用一组地址连续的存储单元（即一维数组）来存放二叉树中的结点。

• 存储方式：按照二叉树结点的层序遍历顺序，将结点存入数组中。对于一个结点，其在数组中的下标通常从 0 或 1 开始。
  • 约定根结点下标为 0:
    • 对于数组中下标为 $i$ 的结点，其左孩子下标为 $2i+1$，右孩子下标为 $2i+2$。
    • 对于数组中下标为 $i$ 的结点（$i>0$），其父结点下标为 $\lfloor (i-1)/2\rfloor$。
  • 约定根结点下标为 1:
    • 对于数组中下标为 $i$ 的结点，其左孩子下标为 $2i$，右孩子下标为 $2i+1$。
    • 对于数组中下标为 $i$ 的结点（$i>1$），其父结点下标为 $\lfloor i/2\rfloor$。
  • 注意：为了反映树的逻辑结构，数组中不存在的结点位置需用一个特殊值（如 0 或 NULL）来表示。
• 特点：
  • 优点：
    • 结点之间关系（父子关系）的确定非常简单，查找父结点和子结点的时间复杂度为 $O(1)$。
    • 对于满二叉树和完全二叉树，不会浪费存储空间，存储密度高。
  • 缺点：
    • 对于非完全二叉树，特别是形态稀疏或严重右斜（左斜）的树，会造成大量的空间浪费。
    • 进行插入、删除等操作时，可能需要移动大量数组元素，效率较低。
• 适用场景：主要适用于完全二叉树的存储，例如堆的实现。

链式存储

链式存储结构是通过指针将离散的结点链接起来，以反映二叉树的逻辑结构。每个结点至少包含数据域、左孩子指针域和右孩子指针域。

• 二叉链表 (Binary Linked List)
  • 结点结构：这是最常用的链式存储结构。

    typedef struct BiTNode {
        ElemType data; // 数据域
        struct BiTNode *lchild, *rchild; // 左、右孩子指针
    } BiTNode, *BiTree;

  • 特点：
    • 优点：
      • 空间利用率高，存储空间只与结点数量有关（$n$ 个结点占用 $n$ 个存储单元），不会因树的形态而浪费空间。
      • 插入、删除结点等操作非常灵活，只需修改相关结点的指针域，无需移动元素。
    • 缺点：
      • 每个结点都需要额外的指针空间，存储密度相对较低。
      • 查找结点的父结点较为困难，需要从根结点开始遍历，或者在遍历过程中使用栈来记录路径。
• 三叉链表 (Three-pronged Linked List)
  • 结点结构：在二叉链表的基础上，增加了一个指向父结点的指针。

    typedef struct TriTNode {
        ElemType data; // 数据域
        struct TriTNode *lchild, *rchild; // 左、右孩子指针
        struct TriTNode *parent; // 父结点指针
    } TriTNode, *TriTree;

  • 特点：
    • 优点：查找父结点非常方便，时间复杂度为 $O(1)$。
    • 缺点：每个结点的空间开销更大。
• 适用场景：适用于任意形态的二叉树，特别是当树的结构需要频繁修改（插入、删除）时。

两种存储结构的比较

特性	顺序存储	链式存储
存储密度	仅对完全二叉树高，否则低	相对较低，但与树形态无关
空间分配	静态分配，一次性分配连续空间	动态分配，按需分配离散空间
查找父/子节点	$O(1)$，非常方便	查找子节点方便，查找父节点不便（需三叉链表或遍历）
插入/删除	效率低，可能需移动大量元素	效率高，只需修改指针
适用情况	完全二叉树（如堆）	任意二叉树，特别是形态不规则或动态变化的树