Lecture 16：二叉树常考性质

16.1 二叉树的定义和基本术语

16.1.1 二叉树的基本概念

定义：#二叉树

描述：二叉树是 $n(n\ge 0)$ 个结点的有限集合。它要么是空二叉树，要么由一个根结点和两棵互不相交的二叉树组成，这两棵二叉树分别称为根的左子树和右子树。

两种二叉树

空二叉树： $$ n=0 $$
非空二叉树：
- 有且仅有一个根结点。
- 根结点可以有左子树。
- 根结点可以有右子树。
- 左子树和右子树本身仍然是二叉树。
- 左右子树互不相交。

特点

每个结点至多只有两棵子树。
左子树和右子树不能颠倒，因此二叉树是有序树。
二叉树可以为空；二叉树为空只表示没有结点，不表示这种二叉树不存在。
二叉树不是“度为 $2$ 的有序树”的简单别名。

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

对比项	二叉树	度为 $2$ 的有序树
是否允许为空	允许为空	通常不讨论空树
是否必须存在度为 $2$ 的结点	不要求	至少有一个结点度为 $2$
只有一个孩子时是否区分左右	区分左孩子和右孩子	按有序树子树次序理解
每个结点最多孩子数	$2$	$2$

解释

“二叉树有序”指的是左、右位置本身有含义。
一个结点只有一个孩子时，必须说明它是左孩子还是右孩子。
两棵树形状看起来相似，但左右位置不同，也可能是两棵不同的二叉树。

读图说明

以 A 为根的二叉树由 A、左子树和右子树递归构成，两棵子树互不相交。
以 B 为根的示例只有左子树，右子树是空二叉树；这与“没有右子树位置”不同，左右位置仍然有意义。

16.1.2 常见二叉树

满二叉树

定义：#满二叉树

描述：一棵高度为 $h$，且含有 $2^h-1$ 个结点的二叉树，称为满二叉树。

核心公式 $$ n=2^h-1 $$

特点

只有最后一层有叶子结点。
不存在度为 $1$ 的结点。
所有非叶结点的度都为 $2$。
若按层序从 $1$ 开始编号，则编号关系为： $$ \text{左孩子}=2i $$ $$ \text{右孩子}=2i+1 $$ $$ \text{父结点}=\left\lfloor \frac{i}{2}\right\rfloor $$

记忆

满二叉树的每一层都被填满。
高度为 $h$ 时，第 $h$ 层有 $2^{h-1}$ 个叶子结点。
前 $h$ 层结点总数是等比数列和： $$ 1+2+4+\cdots+2^{h-1}=2^h-1 $$

读图说明

图中每层都达到容量上限，按层序编号后，结点 $i$ 的左右孩子分别位于 $2i$ 和 $2i+1$；第四层编号为 $8\sim15$。

完全二叉树

定义：#完全二叉树

描述：当且仅当一棵二叉树的每个结点都与高度为 $h$ 的满二叉树中编号为 $1\sim n$ 的结点一一对应时，称为完全二叉树。

直观理解

从一棵满二叉树开始。
按层序编号。
只允许从编号最大的结点开始连续删除。
删除后剩下的树就是完全二叉树。

特点

只有最后两层可能有叶子结点。
最多只有一个度为 $1$ 的结点。
若按层序从 $1$ 开始编号，结点 $i$ 的关系为： $$ \text{左孩子}=2i $$ $$ \text{右孩子}=2i+1 $$ $$ \text{父结点}=\left\lfloor\frac{i}{2}\right\rfloor $$
结点编号满足： $$ i\le \left\lfloor\frac{n}{2}\right\rfloor $$ 则结点 $i$ 为分支结点。 $$ i> \left\lfloor\frac{n}{2}\right\rfloor $$ 则结点 $i$ 为叶子结点。
如果某个结点只有一个孩子，那么这个孩子一定是左孩子。

为什么只有一个孩子时一定是左孩子

完全二叉树按从上到下、从左到右的顺序填充。
不可能出现“右孩子存在而左孩子不存在”的情况。
若某个结点只有一个孩子，说明最后一层填充到该结点的左孩子就停止了。

读图说明

实线和彩色结点是当前完全二叉树，浅色虚线结点表示满二叉树中尚未占用的位置。
现有结点编号连续为 $1\sim12$；若出现编号 $13$ 而编号 $12$ 不存在，就不再是完全二叉树。

二叉排序树

定义：#二叉排序树

描述：二叉排序树是一种可用于元素排序和搜索的二叉树。

特征

左子树上所有结点的关键字均小于根结点的关键字。
右子树上所有结点的关键字均大于根结点的关键字。
左子树和右子树又各是一棵二叉排序树。

上述写法默认关键字互不相同。若允许重复关键字，必须预先约定重复项统一放在一侧或在结点中记录计数，不能时左时右。

递归理解

根结点把数据分成两部分。
小于根的都放左边。
大于根的都放右边。
左右子树内部继续满足同样规则。

中序遍历性质

对二叉排序树进行中序遍历，可以得到递增序列。
这一性质是后续查找、插入、删除和排序题的重要基础。

读图说明

左半部分以 19 为根，左子树所有关键字都小于 19，右子树所有关键字都大于 19，而且两棵子树递归满足同样条件。
右半部分展示一个局部平衡的二叉排序树；AVL 的平衡条件必须对树中每个结点都成立。

平衡二叉树

定义：#平衡二叉树

描述： 408 语境中的平衡二叉树通常指 AVL 树：它首先是一棵二叉排序树，并且树上任一结点的左、右子树高度之差的绝对值不超过 $1$。

公式化表达 对任意结点 $x$，都有： $$ \left|h_L(x)-h_R(x)\right|\le 1 $$

其中：

$h_L(x)$ 表示结点 $x$ 左子树高度。
$h_R(x)$ 表示结点 $x$ 右子树高度。

注意

只满足高度差条件而不满足二叉排序树关键字次序的普通二叉树，不是 AVL 树。
平衡二叉树强调任意结点，而不仅仅是根结点。
只看根的左右高度差不够，子树内部也必须平衡。

16.2 二叉树的性质

16.2.1 最常用性质

性质一：第 k 层最多结点数

二叉树第 $k$ 层最多有： $$ 2^{k-1} $$ 个结点。

说明

根结点位于第 $1$ 层。
第 $1$ 层最多 $1=2^0$ 个结点。
第 $2$ 层最多 $2=2^1$ 个结点。
第 $3$ 层最多 $4=2^2$ 个结点。
依次类推，第 $k$ 层最多 $2^{k-1}$ 个结点。

性质二：叶子结点数与二分支结点数

设非空二叉树中：

$n_0$ 表示度为 $0$ 的结点数，即叶子结点数。
$n_1$ 表示度为 $1$ 的结点数。
$n_2$ 表示度为 $2$ 的结点数。

则： $$ n_0=n_2+1 $$

含义

叶子结点永远比分支数为 $2$ 的结点多 $1$ 个。
这个结论与 $n_1$ 的数量无关。

性质三：高度为 h 的二叉树最多结点数

高度为 $h$ 的二叉树最多有： $$ 2^h-1 $$ 个结点。

达到最大值的情况

每一层都达到最大结点数。
树必须是满二叉树。

性质四：二叉树高度范围

含 $n\ge 1$ 个结点的二叉树，高度 $h$ 的范围为： $$ \left\lfloor\log_2 n\right\rfloor+1\le h\le n $$

等价地，最小高度也可以写成： $$ \left\lceil\log_2(n+1)\right\rceil $$

解释

最矮的情况：尽量填满每一层，形态接近完全二叉树。
最高的情况：每个结点都只有一个孩子，退化成单支链。

性质五：二叉链表空指针总数

若一棵二叉树有 $n$ 个结点，则二叉链表中共有： $$ 2n $$ 个指针域。

其中有 $n-1$ 个指针指向真实结点，因此空指针数为： $$ 2n-(n-1)=n+1 $$

PDF 中的另一种推导 按结点度数拆分： $$ \text{空指针数}=2n_0+n_1 $$

又因为： $$ n=n_0+n_1+n_2 $$ $$ n_0=n_2+1 $$

所以： $$ 2n_0+n_1=n_0+n_0+n_1=n_0+n_2+1+n_1=n+1 $$

16.2.2 二叉树的常考性质

考点一：$n_0=n_2+1$

设非空二叉树中度为 $0,1,2$ 的结点个数分别为 $n_0,n_1,n_2$。

结论 $$ n_0=n_2+1 $$

推导第一种计数方式：按结点的度分类。 $$ n=n_0+n_1+n_2 $$

第二种计数方式：结点数等于总度数加 $1$。 $$ n=n_1+2n_2+1 $$

两式相减： $$ n_0+n_1+n_2=n_1+2n_2+1 $$

整理得到： $$ n_0=n_2+1 $$

为什么结点数等于总度数加 1

所有结点的度数之和等于边数。
非空树中，边数为结点数减 $1$。
因此： $$ \text{总度数}=n-1 $$ $$ n=\text{总度数}+1 $$

考点二：每层结点数

二叉树第 $i$ 层至多有： $$ 2^{i-1} $$ 个结点，其中： $$ i\ge 1 $$

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

对比

树类型	第 $i$ 层最多结点数
二叉树	$2^{i-1}$
$m$ 叉树	$m^{i-1}$

考点三：高度为 h 的树最多结点数

高度为 $h$ 的二叉树至多有： $$ 2^h-1 $$ 个结点。

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

当 $m=1$ 时，树退化为链，最多有 $h$ 个结点。

推导 $m$ 叉树每层最多结点数为： $$ 1,m,m^2,\cdots,m^{h-1} $$

求和： $$ 1+m+m^2+\cdots+m^{h-1}=\frac{m^h-1}{m-1} $$

16.2.3 完全二叉树的常考性质

考点一：n 个结点的完全二叉树高度

具有 $n(n>0)$ 个结点的完全二叉树高度 $h$ 为： $$ h=\left\lceil\log_2(n+1)\right\rceil $$

也可以写为： $$ h=\left\lfloor\log_2 n\right\rfloor+1 $$

两种写法为什么都可以

$\left\lceil\log_2(n+1)\right\rceil$ 是从“满到第 $h$ 层至少需要覆盖 $n$ 个结点”推出来的。
$\left\lfloor\log_2 n\right\rfloor+1$ 是由最大编号 $n$ 所在层数推出来的。
二者对正整数 $n$ 等价。

推导思路 高度为 $h$ 的完全二叉树满足： $$ 2^{h-1}\le n\le 2^h-1 $$

由左边： $$ h\le \log_2 n+1 $$

由右边： $$ n+1\le 2^h $$ $$ \log_2(n+1)\le h $$

因此： $$ h=\left\lceil\log_2(n+1)\right\rceil $$

考点二：由 n 推出 $n_0,n_1,n_2$

完全二叉树最多只有一个度为 $1$ 的结点，因此： $$ n_1=0\ \text{或}\ 1 $$

又因为： $$ n_0=n_2+1 $$

所以： $$ n_0+n_2 $$ 一定是奇数。

情况一：结点总数为偶数 若完全二叉树有 $2k$ 个结点，则必有： $$ n_1=1 $$ $$ n_0=k $$ $$ n_2=k-1 $$

推导 $$ n=n_0+n_1+n_2 $$

代入 $n=2k$ 和 $n_0=n_2+1$： $$ 2k=(n_2+1)+n_1+n_2 $$

若 $n_1=1$： $$ 2k=2n_2+2 $$ $$ n_2=k-1 $$ $$ n_0=k $$

情况二：结点总数为奇数 若完全二叉树有 $2k-1$ 个结点，则必有： $$ n_1=0 $$ $$ n_0=k $$ $$ n_2=k-1 $$

推导 $$ 2k-1=(n_2+1)+0+n_2 $$ $$ 2k-1=2n_2+1 $$ $$ n_2=k-1 $$ $$ n_0=k $$

速记表

完全二叉树结点总数	$n_1$	$n_0$	$n_2$
$2k$	$1$	$k$	$k-1$
$2k-1$	$0$	$k$	$k-1$

完全二叉树性质补充

对完全二叉树按层序从 $1$ 开始编号，设结点总数为 $n$。

父结点编号

当 $i>1$ 时，结点 $i$ 的双亲编号为： $$ \left\lfloor\frac{i}{2}\right\rfloor $$

奇偶关系

当 $i$ 为偶数时： $$ \text{父结点编号}=\frac{i}{2} $$ 此时 $i$ 是双亲的左孩子。
当 $i$ 为奇数时： $$ \text{父结点编号}=\frac{i-1}{2} $$ 此时 $i$ 是双亲的右孩子。

左孩子编号

当： $$ 2i\le n $$ 时，结点 $i$ 的左孩子编号为： $$ 2i $$

否则结点 $i$ 没有左孩子。

右孩子编号

当： $$ 2i+1\le n $$ 时，结点 $i$ 的右孩子编号为： $$ 2i+1 $$

否则结点 $i$ 没有右孩子。

结点 i 所在层次

结点 $i$ 所在层次为： $$ \left\lfloor\log_2 i\right\rfloor+1 $$

注意区分

求“编号 $i$ 的结点所在层次”，用 $i$： $$ \left\lfloor\log_2 i\right\rfloor+1 $$
求“$n$ 个结点的完全二叉树高度”，用 $n$： $$ \left\lceil\log_2(n+1)\right\rceil $$ 或： $$ \left\lfloor\log_2 n\right\rfloor+1 $$

16.3 二叉树的存储结构

16.3.1 顺序存储

定义：#顺序存储

描述：二叉树的顺序存储用数组 t 按对应满二叉树的层序编号存放结点。若最大结点编号为 MaxSize，并约定 t[0] 留空，则数组至少需要 MaxSize+1 个槽位。

重要结论

二叉树的顺序存储结构特别适合完全二叉树，因为结点编号与数组位置连续对应。
其他二叉树也可以按其在对应完全二叉树中的位置补空位存储，但可能严重浪费空间。
对于非完全二叉树，必须把结点编号与对应位置补齐，否则无法直接用编号关系判断父子关系。

数组下标习惯

PDF 中为了让结点编号和数组下标一致，通常让 t[0] 空出来。
这样编号为 $i$ 的结点就放在 t[i] 中。

基本操作 对完全二叉树，结点 $i$：

左孩子编号： $$ 2i $$
右孩子编号： $$ 2i+1 $$
父结点编号： $$ \left\lfloor\frac{i}{2}\right\rfloor $$
若求结点 $i$ 所在层次： $$ \left\lfloor\log_2 i\right\rfloor+1 $$
若求 $n$ 个结点的完全二叉树高度： $$ \left\lceil\log_2(n+1)\right\rceil $$ 或： $$ \left\lfloor\log_2 n\right\rfloor+1 $$

基本判断操作

判断 $i$ 是否有左孩子： $$ 2i\le n $$
判断 $i$ 是否有右孩子： $$ 2i+1\le n $$
判断 $i$ 是否为叶子结点： $$ i>\left\lfloor\frac{n}{2}\right\rfloor $$
判断 $i$ 是否为分支结点： $$ i\le\left\lfloor\frac{n}{2}\right\rfloor $$

非完全二叉树的顺序存储问题

非完全二叉树的结点编号无法和真实结点连续对应。
顺序存储时，必须把该二叉树的结点编号与完全二叉树中的位置对应起来。
空缺位置需要显式标记为空。
不能只通过 $i$ 和 $n$ 的大小关系判断是否有左、右孩子。
需要使用 isEmpty 属性判断某个数组位置是否为空。

最坏情况

高度为 $h$ 且只有 $h$ 个结点的右单支树，最深结点编号为： $$ 2^h-1 $$
为保留编号 $1\sim 2^h-1$ 的位置，需要 $2^h-1$ 个有效编号位置；若还让 t[0] 留空，实际数组至少需要 $2^h$ 个槽位。空缺位置以 isEmpty 标记。

结论

顺序存储特别适合完全二叉树，但并非不能存储其他二叉树。
对非完全二叉树可能严重浪费空间。
对非完全二叉树，判断空结点必须依赖 isEmpty。

完全二叉树读图

t[0] 留空后，结点编号与数组下标一致，编号 $1\sim12$ 的结点连续占用 t[1] 至 t[12]。

非完全二叉树读图

右单支树只有 1、3、7、15 四个结点，却必须保留编号对应的空位；高度为 $4$ 时已经占到 t[15]，体现了最坏情况下的空间浪费。

顺序存储代码实现

#include <stdbool.h>

#define MaxSize 100
typedef int ElemType;  // 示例元素类型，可替换

typedef struct {
    ElemType value;  // 结点中的数据元素
    bool isEmpty;   // 结点是否为空
} TreeNode;

// 初始化数组
TreeNode t[MaxSize + 1];  // t[0] 留空，可用编号为 1～MaxSize

void InitTreeArray(TreeNode t[]) {
    for (int i = 0; i <= MaxSize; i++) {
        t[i].isEmpty = true;
    }
}

代码理解

value 保存结点数据。
isEmpty 用来标记该数组位置是否为空。
对非完全二叉树尤其需要 isEmpty，否则无法区分“该位置没有结点”和“数组没有用到”。
访问 t[i] 前仍须保证 $1\le i\le\texttt{MaxSize}$；isEmpty 不能代替数组越界检查。

16.3.2 链式存储

定义：#链式存储

描述：二叉树的链式存储用结点和指针表示树中结点之间的父子关系，每个结点通常包含数据域、左孩子指针和右孩子指针。

二叉链表结点结构

数据域：保存结点自身数据。
左孩子指针：指向左孩子。
右孩子指针：指向右孩子。

空链域数量 若非空二叉树有 $n$ 个结点：

每个结点有 $2$ 个指针域。
总指针域数为： $$ 2n $$
除根结点外，每个结点都有一个来自父结点的指针，因此非空指针数为： $$ n-1 $$
空指针域数为： $$ 2n-(n-1)=n+1 $$

作用

这些空链域后续可以用于构造线索二叉树。
链式存储对非完全二叉树更节省空间。

读图说明

左图突出真实存在的结点，浅色位置不分配链式结点；右图每个结点只用 lchild、rchild 指向实际孩子，空孩子对应 NULL。
链式结构不需要为完全二叉树编号中的空位预留结点，因此更适合形态稀疏的二叉树。

结点定义

// 二叉树的结点（链式存储）
typedef struct BiTNode {
    ElemType data;                  // 数据域
    struct BiTNode *lchild, *rchild; // 左、右孩子指针
} BiTNode, *BiTree;

解释

BiTNode 表示一个二叉树结点类型。
BiTree 表示指向二叉树根结点的指针。
若 BiTree root = NULL;，表示这是一棵空二叉树。

链式树构建示例

// 二叉树的链式构建
#include <stdlib.h>

typedef struct {
    int value;
} ElemType;

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void LinkTreeExample(void) {
    // 定义一棵空树，root 指向根结点
    BiTree root = NULL;

    // 插入根结点
    root = malloc(sizeof *root);
    if (root == NULL) return;
    root->data = (ElemType){1};
    root->lchild = NULL;
    root->rchild = NULL;

    // 插入新结点
    BiTNode *p = malloc(sizeof *p);
    if (p == NULL) {
        free(root);
        return;
    }
    p->data = (ElemType){2};
    p->lchild = NULL;
    p->rchild = NULL;
    root->lchild = p;  // 作为根结点的左孩子

    // 示例结束后释放；实际使用时应在树不再需要时释放
    free(p);
    free(root);
}

构建过程

root = NULL 表示原来是空树；构建语句须写在函数体内。
malloc(sizeof(BiTNode)) 为根结点申请空间。
给根结点的数据域赋值。
根结点的左、右孩子指针先置为 NULL。
再申请一个新结点 p。
让 root->lchild = p，表示 p 成为根结点的左孩子。
动态申请的结点用完后需释放；此示例先释放子结点，再释放根结点。

16.3.3 三叉链表

定义：#三叉链表

描述：三叉链表在二叉链表的基础上，除了左孩子指针和右孩子指针外，还增加一个指向父结点的指针。

结构

数据域。
左孩子指针。
右孩子指针。
父结点指针。

目的

方便从某个结点直接找到父结点。
不需要从根结点重新遍历查找双亲。

考试注意

PDF 强调：考研中更喜欢考不带 parent 的方式。
因此二叉链表是基础，三叉链表作为补充理解即可。

三叉链表代码

// 二叉树的结点（链式存储）
typedef struct BiTNode {
    ElemType data;                    // 数据域
    struct BiTNode *lchild, *rchild;   // 左、右孩子指针
    struct BiTNode *parent;            // 父结点指针
} BiTNode, *BiTree;

16.4 题型：二叉树性质计算

题型一：由 $n_0,n_1,n_2$ 求未知量

第一部分：解题方法

先写总数公式： $$ n=n_0+n_1+n_2 $$
再写二叉树核心公式： $$ n_0=n_2+1 $$
若题目给总边数或总结点数，再用： $$ \text{边数}=n-1 $$
若题目出现空指针数，再用： $$ \text{空指针数}=n+1 $$

第二部分：典型例题

例 1 一棵非空二叉树中，度为 $2$ 的结点有 $8$ 个，求叶子结点个数。

解析 $$ n_0=n_2+1=8+1=9 $$

答案 $$ 9 $$

例 2 一棵二叉树有 $20$ 个结点，求它的二叉链表空指针数。

解析 $$ \text{空指针数}=n+1=20+1=21 $$

答案 $$ 21 $$

第三部分：知识点复盘

二叉树最常考公式是 $n_0=n_2+1$。
空指针数不要写成 $2n$，$2n$ 是总指针域数。
真实指向结点的指针数是 $n-1$。

题型二：完全二叉树编号计算

第一部分：解题方法

对完全二叉树按层序从 $1$ 开始编号：

求左孩子，看 $2i$。
求右孩子，看 $2i+1$。
求父结点，看 $\left\lfloor i/2\right\rfloor$。
求是否为叶子，看 $i>\left\lfloor n/2\right\rfloor$。
求结点层次，看 $\left\lfloor\log_2 i\right\rfloor+1$。
求整棵树高度，看 $\left\lceil\log_2(n+1)\right\rceil$ 或 $\left\lfloor\log_2 n\right\rfloor+1$。

第二部分：典型例题

例 1 一棵完全二叉树有 $100$ 个结点，编号为 $23$ 的结点，其父结点、左孩子、右孩子编号分别是多少？

解析父结点： $$ \left\lfloor\frac{23}{2}\right\rfloor=11 $$

左孩子： $$ 2\times 23=46\le 100 $$

右孩子： $$ 2\times 23+1=47\le 100 $$

答案

父结点编号为 $11$。
左孩子编号为 $46$。
右孩子编号为 $47$。

例 2 一棵完全二叉树有 $100$ 个结点，编号大于多少的结点一定是叶子结点？

解析分支结点满足： $$ i\le \left\lfloor\frac{100}{2}\right\rfloor=50 $$

叶子结点满足： $$ i>50 $$

答案

编号 $51\sim 100$ 的结点都是叶子结点。

第三部分：知识点复盘

完全二叉树编号题默认从 $1$ 开始编号。
若数组从 t[0] 开始连续存储，公式会发生变化；408 通常按编号从 $1$ 开始考。
判断是否有孩子必须先和 $n$ 比较，不能只算出 $2i$ 或 $2i+1$。

题型三：完全二叉树中 $n_0,n_1,n_2$ 的数量

第一部分：解题方法

看总结点数 $n$ 的奇偶。
若 $n=2k$，则： $$ n_1=1,\quad n_0=k,\quad n_2=k-1 $$
若 $n=2k-1$，则： $$ n_1=0,\quad n_0=k,\quad n_2=k-1 $$

第二部分：典型例题

例 1 一棵完全二叉树有 $64$ 个结点，求 $n_0,n_1,n_2$。

解析 $$ 64=2k $$ $$ k=32 $$

所以： $$ n_1=1 $$ $$ n_0=32 $$ $$ n_2=31 $$

答案 $$ n_0=32,\quad n_1=1,\quad n_2=31 $$

例 2 一棵完全二叉树有 $63$ 个结点，求 $n_0,n_1,n_2$。

解析 $$ 63=2k-1 $$ $$ k=32 $$

所以： $$ n_1=0 $$ $$ n_0=32 $$ $$ n_2=31 $$

答案 $$ n_0=32,\quad n_1=0,\quad n_2=31 $$

第三部分：知识点复盘

完全二叉树最多只有一个度为 $1$ 的结点。
总结点数为偶数时，存在一个度为 $1$ 的结点。
总结点数为奇数时，不存在度为 $1$ 的结点。

16.5 本节复盘

必须背熟的公式

公式	含义
$n=n_0+n_1+n_2$	二叉树按结点度分类
$n=n_1+2n_2+1$	结点数等于总度数加 $1$
$n_0=n_2+1$	叶子结点比分支度为 $2$ 的结点多 $1$
第 $k$ 层最多 $2^{k-1}$ 个结点	层数从 $1$ 开始
高度为 $h$ 最多 $2^h-1$ 个结点	满二叉树达到最大
空指针数 $n+1$	二叉链表空链域数量
完全二叉树高度 $\left\lceil\log_2(n+1)\right\rceil$	由总结点数求高度
完全二叉树高度 $\left\lfloor\log_2 n\right\rfloor+1$	与上一公式等价
结点 $i$ 的层次 $\left\lfloor\log_2 i\right\rfloor+1$	由编号求层次

完全二叉树编号规则

目标	条件或公式
父结点	$\left\lfloor i/2\right\rfloor$，其中 $i>1$
左孩子	$2i$，且 $2i\le n$
右孩子	$2i+1$，且 $2i+1\le n$
分支结点	$i\le \left\lfloor n/2\right\rfloor$
叶子结点	$i> \left\lfloor n/2\right\rfloor$

易错点

二叉树可以为空，空二叉树不是“不存在”。
二叉树的左右子树不能颠倒。
满二叉树一定是完全二叉树；完全二叉树不一定是满二叉树。
度为 $2$ 的有序树不等于二叉树。
顺序存储天然适合完全二叉树；其他二叉树也能补空位存储，但可能严重浪费空间。
非完全二叉树顺序存储时需要补空位置，并用 isEmpty 判断。
三叉链表有 parent 指针，但 408 更常考二叉链表。

16.1 二叉树的定义和基本术语

16.1.1 二叉树的基本概念

定义：#二叉树

16.1.2 常见二叉树

满二叉树

定义：#满二叉树

完全二叉树

定义：#完全二叉树

二叉排序树

定义：#二叉排序树

平衡二叉树

定义：#平衡二叉树

16.2 二叉树的性质

16.2.1 最常用性质

性质一：第 k 层最多结点数

性质二：叶子结点数与二分支结点数

性质三：高度为 h 的二叉树最多结点数

性质四：二叉树高度范围

性质五：二叉链表空指针总数

16.2.2 二叉树的常考性质

考点一：$n_0=n_2+1$

考点二：每层结点数

考点三：高度为 h 的树最多结点数

16.2.3 完全二叉树的常考性质

考点一：n 个结点的完全二叉树高度

考点二：由 n 推出 $n_0,n_1,n_2$

完全二叉树性质补充

父结点编号

左孩子编号

右孩子编号

结点 i 所在层次

16.3 二叉树的存储结构

16.3.1 顺序存储

定义：#顺序存储

顺序存储代码实现

16.3.2 链式存储

定义：#链式存储

结点定义

链式树构建示例

16.3.3 三叉链表

定义：#三叉链表

三叉链表代码

16.4 题型：二叉树性质计算

题型一：由 $n_0,n_1,n_2$ 求未知量

第一部分：解题方法

第二部分：典型例题

第三部分：知识点复盘

题型二：完全二叉树编号计算

第一部分：解题方法

第二部分：典型例题

第三部分：知识点复盘

题型三：完全二叉树中 $n_0,n_1,n_2$ 的数量

第一部分：解题方法

第二部分：典型例题

第三部分：知识点复盘

相关知识

16.5 本节复盘