408 数据结构--二叉树的概念、性质和存储结构 自学知识结构

前置知识：树的基本概念与性质

---

二叉树的定义

二叉树是一种特殊的树形结构，其特点是每个结点至多只有两棵子树（即二叉树中不存在度大于$2$的结点），并且二叉树是有序树，左右子树不能互换。
与树类似，二叉树也以递归形式定义。二叉树是$n$（$n\ge 0$）个结点的有限集合。当$n=0$时，称为空二叉树。
当$n\ne 0$时，二叉树由根结点和两个互不相交的子树组成，左子树和右子树又分别是一棵二叉树。即使树中结点只有一棵子树，因为二叉树有序，也要区分是左子树还是右子树。
二叉树与度为$2$的有序树的区别：

• 度为$2$的有序树至少有$3$个结点，而二叉树可以为空。
• 度为$2$的有序树的孩子的左右次序是相对于另一个孩子而言的，若某一结点只有一个孩子结点，则无需区分其左右。而对二叉树上的结点来说，无论其孩子数是否为$2$，均需确定其左右次序。即二叉树的结点次序不是相对于另一个结点而言的，而是确定的。

几种特殊的二叉树

Man! 满二叉树

一棵高度为$h$，且有$2^h-1$个结点的二叉树被称为满二叉树。
因为对一个满二叉树来说，第$i$层有$2^{i-1}$个结点，一共有$h$层，则求和结果就是$2^h-1$。
满二叉树的特点：

1. 只有最后一层有叶子结点。
2. 不存在度为$1$的结点。
3. 若层序从$1$开始编号，则对第$i$个结点，其左孩子必为第$2i$个结点，右孩子必为第$2i+1$个结点。如果结点$i$存在双亲结点，则其双亲必为第$\lfloor i/2\rfloor$个结点（即对$i/2$向下取整）。

（下图来自王道考研408数据结构课程视频 - 二叉树的定义和基本术语）

完全二叉树

一棵高度为$h$、有$n$个结点的二叉树，当且仅当其每个结点都与高度为$h$的满二叉树中编号为$1-n$的结点一一对应时，称为完全二叉树。
完全二叉树的特点：

1. 只有最后两层（层数最大的两层）可能有叶子结点。
2. 最多只有一个度为$1$的结点，且该结点只有左孩子而无右孩子。
3. 层序从$1$开始编号，则对第$i$个结点，其左孩子必为第$2i$个结点，右孩子必为第$2i+1$个结点。如果结点$i$存在双亲结点，则其双亲必为第$\lfloor i/2\rfloor$个结点。（同满二叉树）
4. 对结点$i$，当$i\le \lfloor n/2\rfloor$时，该结点为分支结点；当$i＞\lfloor n/2\rfloor$时，该结点为叶结点。
5. 若$n$为奇数，则每个分支结点都有左孩子和右孩子；若$n$为偶数，则编号最大的分支结点（编号为$n/2$）只有左孩子，没有右孩子，其余分支结点均有左、右孩子。

二叉排序树⭐

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

平衡二叉树⭐

树中任意一个结点的左子树和右子树的高度之差的绝对值不超过$1$，这样的二叉树称为平衡二叉树。
如果一棵二叉排序树是平衡的，那么它的搜索效率会高很多。

关于二叉排序树和平衡二叉树，后续章节会有详细介绍，现在暂时了解其概念即可。

正则二叉树

树中每个分支结点都有$2$个孩子，即树中只有度为$0$或$2$的结点。

---

二叉树的性质相关

常见考点1：非空二叉树上的叶结点数等于度为$2$的结点数加$1$，即$n_0=n_2+1$。

假设树中结点总数为$n$，度为$0$的结点数为$n_0$，度为$1$的结点数为$n_1$，度为$2$的结点数为$n_2$。则有：
① $n=n_0+n_1+n_2$
② $n=n_1+2n_2+1$（树的结点数=总度数+1）
联立两式，得$n_0=n_2+1$。
这一个考点常在选择题中涉及，需要牢记并灵活应用。

常见考点2：非空二叉树的第$i$层至多有$2^{i-1}$个结点（$i\ge 1$）

由树的基本概念与性质可知，$m$叉树的第$i$层至多有$m^{i-1}$个结点（$i\ge 1$），令$m=2$即可。

常见考点3：高度为$h$的二叉树至多有$2^h-1$个结点（$h\ge 1$）

由树的基本概念与性质可知，高度为$h$的$m$叉树至多有$\frac{m^h-1}{m-1}$个结点（$i\ge 1$），令$m=2$，得有$2^h-1$个（满二叉树）。

完全二叉树的性质相关

常见考点1：具有$n$个结点（$n＞0$）的完全二叉树的高度$h$为$\lceil {\log }_2\left(n+1\right)\rceil$或$\lfloor {\log }_{2}n\rfloor +1$。

由完全二叉树的已知性质，假设完全二叉树的高度为$h$，则有

$2^{h-1}-1<n\le 2^h-1$ 或 $2^{h-1}\le n<$