树与二叉树的基本概念¶
树的基本概念¶
树的定义¶
- 树(
Tree)：这是一种非线性结构。是\(n(n≥0)\)个有限结点组成的一个具有层次关系的集合，与现实生活中的树十分相像，只不过它是倒挂的。\(n=0\)时称这样的树为空树
Note
树结构特点：在任何一个非空树中
- 有且只有一个特定的称为根(
Root)的结点 - 当\(n>1\)时，其余结点可以分为\(m(m>0)\)个互不相交的有限集合\(T_1,T_2\cdots{T_m}\),其中每一个集合本身又是一颗树，并且称为根的子树(
Sub Tree)。因此树是具有递归性质的. - 树： 也是连通无环图、极小连通图、极大无环图\ 树的边和结点数的关系： e = n-1
- 结点分类
树结点结构：包含一个数据元素和指向其子树的分支
结点分类：除根节点外，其余结点有且只有一个前驱
- 根节点：只有后继没有前驱，对于非空树，有且只有一个
- 叶子结点（终端结点）：没有后继结点的结点（度为0）
-
分支结点（非终端结点）：有后继结点的结点（度大于0），除根节点外的分支结点也称为内部结点
-
基本术语
| 术语名称 | 描述 | 举例 |
|---|---|---|
| 结点 | A，B，C等都是结点，结点不仅包含数据元素，而且包含指向子树的分支。 | A结点不仅包含元素A，而且包含三个指向子树的指针 |
| 结点的度 | 结点的孩子个数或拥有的子树个数或分支个数 | A结点有三个孩子，A的度为3 |
| 树的度 | 树中各结点度的最大值 | A,D结点的度最大为3，故树的度为3 |
| 叶子结点 | 度为0的结点 | F,G,I,J,K,L,M均为叶子结点 |
| 非叶结点 | 度不为0的结点 | A,B,C,D,E,H,均为非叶结点 |
| 孩子 | 某结点子树的根 | A结点的孩子为B,C,D |
| 双亲 | 与孩子的定义对应 | B,C,D的双亲都是A |
| 兄弟 | 同一个双亲的孩子互为兄弟 | B,C,D互为兄弟 |
| 祖先 | 从根到某结点的唯一路径上所有的结点，都是该结点的祖先 | K的祖先是A,B,E |
| 子孙 | 以某结点为根的子树中的所有结点 | D的子孙是H,I,J,M |
| 层次 | 根节点为第一层，根的孩子是第二层次，以此类推 | 结点F处在第三层 |
| 结点的深度 | 是指从根节点到该结点路径上的结点个数，也就是该结点的层次，自顶向下逐层累加 | A、E、L的深度分别为1、3、4 |
| 结点的高度 | 从某结点往下走可能到达多个叶子结点，对应了通往这些叶子结点的路径，其中最长的那条路径上的结点的个数称其为结点的高度（即以当前结点为根的子树的高度），自底向上逐层累加 | A、E、J的高度分别为4、2、1 |
| 树的高度(深度) | 树中结点的最大层次 | 根节点的高度就是树的高度 |
| 堂兄弟 | 双亲在同一层的结点互为堂兄弟 | E、F、G、H、I、J互为堂兄弟 |
| 有序树 | 树中任意节点的子节点之间有顺序关系，这种树称为有序树。即树的所有节点按照一定的顺序排列，这样进行插入、删除、查找时效率就会非常高 | \(BST/AVL/BRT\) |
| 无序树 | 树中结点的子树没有顺序，可以任意交换 | |
| 森林 | 若干互不相交的树的集合 | 上面的树，将根结点A去除，剩余的就一个森林 |
| 路径 | 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，由于树的分支是有向的，即从双亲指向孩子，所以树中的路径是从上向下的，同一双亲的孩子之间不存在路径 | |
| 路径长度 | 路径上所经过的边的个数 | |
| 树的路径长度 | 指树根到每个结点的路径长的总和，根到每个结点的路径长度的最大值应是树的高度减 1。注意与哈夫曼树的带权路径长度相区别。 |
深度和高度的理解可以类比楼的高度从下往上看，和水的深度从上往下看
- \(height( v ) + depth( v ) <= height( T )\)何时取等号 ?
答：即\(height( v ) + depth( v ) <= height( T )\) 取等号的时机应该是v节点处在这棵树的一条最长的由一个叶子到根的路径上所有节点构成的链上， 这条链上的所有节点都可以取等号，这条链的长度也等于树的高度
- 在一棵树中,顶点p是顶点v的父亲,则它们的高度的关系是
答：结点高度=\(max\)\(+1\)； 所以\(h(p)>= h(v)+1\)。
- 维基百科：树（数据结构）-wiki
树的基本性质¶
- 树中的结点数 = 总度数 + 1；
- 度为\(m\)的树和\(m\)叉树的区别
| 度为\(m\)的树 | \(m\)叉树 |
|---|---|
| 任意结点的度小于等于\(m\)，也即最多\(m\)个孩子 | 任意结点的度小于等于\(m\)，也即最多\(m\)个孩子 |
| 至少有一个结点度为\(m\) | 允许所有结点的度都小于\(m\) |
| 一定是非空树，至少有\(m+1\)个结点 | 可以是空树 |
 |
 |
- 度为\(m\)的树第\(i\)层至多有\(m^{i-1}\)个结点，其中\(i\)大于等于1
- 高度为\(h\)的\(m\)叉树至多有\(\frac{m^h-1}{m-1}\)个结点（即等比数列求和公式）：\(m^0+m^1+\cdots+m^{h-1}=\frac{m^h-1}{m-1}\)
- 高度为\(h\)的\(m\)叉树至少有\(h\)个结点；高度为\(h\)度为\(m\)的树至少有\(h+m-1\)个结点
- 具有\(n\)个结点的\(m\)叉树的最小高度为\(\lceil log_{m}(n(m-1)+1)\rceil\)
设一棵 m叉树的高度为 h。在高度固定的情况下，要容纳尽可能多的结点，就应当使每一层的结点数都达到最大值。从第 1 层到第 h 层，各层最多分别有\(1,m,m^2,\ldots,m^{h-1}\)个结点。因此，高度为h 的 m 叉树最多具有\( 1+m+m^2+\cdots+m^{h-1} \=\frac{m^h-1}{m-1} \)个结点。
若该树要容纳 n 个结点，则必须满足\(n\le \frac{m^h-1}{m-1}.\)
由于 \(m\ge 2\)，所以 m-1>0。整理上式可得\(n(m-1)\le m^h-1,\)从而\(m^h\ge n(m-1)+1.\)
两边取以 m 为底的对数，得到\(h\ge \log_m\bigl(n(m-1)+1\bigr).\)
因为树高h 必须是整数，所以\( h\ge \left\lceil \log_m\bigl(n(m-1)+1\bigr) \right\rceil. \)
下面说明这个下界确实能够达到。令\( h_0= \left\lceil \log_m\bigl(n(m-1)+1\bigr) \right\rceil. \)由\( h_0 \)的定义可知\( n\le \frac{m^{h_0}-1}{m-1}. \)
因此，可以按照从上到下、从左到右的顺序，将 n 个结点依次放入一棵完全 m 叉树中。这样得到的树高度不超过\(h_0\)。另一方面，\(h_0\)是满足上述容量条件的最小整数，所以高度不可能小于\(h_0\)。
故具有 n 个结点的 m 叉树的最小高度为\( h_{\min}=\left\lceil\log_m\bigl(n(m-1)+1\bigr)\right\rceil \)
- 具有\(n\)个结点的度为m的最大高度为\(n-m+1\).
只有一个结点的度为\(m\),其他结点的度都为1.
二叉树的概念¶
基本概念¶
- 二叉树(
Binary Tree)定义：是\(n\)个(\(n≥0\))结点的有限集合，其中每个结点最多有两颗子树，也即二叉树度最大为2，同时二叉树子树有次序之分，不能颠倒。结点数为\(0\)的二叉树称之为空二叉树.
含有\(n\)个结点的二叉树最多有\(\frac{C^n_{2n}}{n+1}\)种形态
- 二叉树五种形态
几种特殊的二叉树¶
| 满二叉树 | 完全二叉树 | 二叉排序(查找)树(BST) |
平衡二叉树 |
|---|---|---|---|
 |
 |
 |
 |
| 从根节点开始，按层序从左到右，从上到下依次编号，第一个结点编号为1，那么对于编号为\(i\)的结点，其双亲(若存在)的编号为\(⌊i/2⌋\),其左右孩子的编号分别为\(2i\)和\(2i+1\). | 特点： 只有最后两层可能有叶子结点; 最多只有一个度为1的结点 ; 如果某个结点只有一个孩子，那么它一定是左孩子 ; 若按层序从1开始编号，结点\(i\)的左孩子的编号就为\(2i\)，右孩子的编号就为\(2i+1\)，同时其父节点为\(⌊i/2⌋\) ; 若按层序从1开始编号,当\(i ≤ ⌊ n/ 2 ⌋\)时该结点为分支结点，当\(i > ⌊ n /2 ⌋\)时该结点为叶子结点 |
左子树上所有结点的关键字值均小于根结点的关键字 ； 右子树上所有结点的关键字值均大于根结点的关键字 ； 左子树和右子树又各是一颗二叉排序树 |
树上任一结点的左子树和右子树的高度之差不超过1（能有更高的搜索效率） |
【扩展】：
- 完全二叉树的层次遍历中，【队列的最大规模】= \(\frac{n+1}{2}\) = 叶子节点个数，且最大规模可能出现两次\ 即完全二叉树层次遍历【队列容量】 <= 叶子节点个数
- 当n为奇数，在 A[ n/2 ] 结点处于队首时出现一次
- 当n为偶数时，在 A[ n/2 -1 ] 和 A[ n/2 ] 结点处于队首时各出现一次，共计2次。
在整个遍历过程中，辅助队列的规模变化是单峰对称的，即
- { 0, 1, 2, ..., (n + 1)/2, ..., 2, 1, 0 } （n 为奇数时）
- { 0, 1, 2, ..., n/2, n/2, ..., 2, 1, 0 } （n 为偶数时）
2. 真二叉树：不含度为1的结点的二叉树称作真二叉树，即只含有度0或者度2结点的二叉树。(真二叉树无\(n_1\)节点，其内部节点数等于\(n_2 = n_0-1\)，即真二叉树内部节点数比叶子节点数少1。) 3. 二叉树的退化
当二叉树的每层节点都被填满时，达到「满二叉树」；而当所有节点都偏向一侧时，二叉树退化为「链表」。
- 满二叉树是理想情况，可以充分发挥二叉树“分治”的优势。
- 链表则是另一个极端，各项操作都变为线性操作，时间复杂度退化至\(O(n)\).
二叉树的常考性质¶
性质1：非空二叉树中，叶子结点(度为0的结点总比度为2的结点多1个,即\(n_0 = n_2+1\)
- 首先需要明白，度为0的结点，引出0个分支；度为1的结点引出1个分支，度为2的结点引出2个分支，依次类推
- 假设一个二叉树中叶子结点有\(n_0\)个，那么它引出0条分支，单分支结点数为\(n_1\)个，它就会引出\(1×n_1\)条分支，双分支结点数为\(n_2\)，它引出\(2×n_2\)条分支。于是总的结点数为\(n_0+n_1+n_2\)，总分支数为\(n_1+2×n_2\)条
- 任何一个树，总分支（度）数=总结点数 - 1，于是可知\(n_1+2×n_2=n_0+n_1+n_2-1\)，化简得到\(n_0=n_2+1\).
性质2：二叉树第\(i\)层至多有\(2^{i-1}\)个结点
性质3: 边数\(e = n-1 = n_1 + 2×n_2\)
性质4：高度为\(h\)的二叉树至多有\(2^h-1\)个结点（也就是满二叉树）
性质5：具有\(n\)个结点的完全二叉树的高度为\(h = ⌊ l o g 2 n ⌋ + 1 或 ⌈ l o g 2 ( n + 1 ) ⌉\)，其中 \(n\ge 1\)。
证明：完全二叉树具有以下特点：
- 除最后一层外，其余各层都是满的；
- 最后一层的结点从左到右连续排列。
设该完全二叉树的高度为 h。前 (h-1) 层是一棵满二叉树，共有 \(2^{h-1}-1\) 个结点。由于第 h 层至少有一个结点，所以高度为 h 的完全二叉树至少有\( n_{\min} \=(2^{h-1}-1)+1 \=2^{h-1} \)个结点。这个结论对 h=1 也成立。
当第 h 层也被填满时，得到一棵高度为 h 的满二叉树，此时结点数最多：
\( n_{\max} \=1+2+2^2+\cdots+2^{h-1} \=2^h-1. \)
所以，高度为 h 的完全二叉树的结点数必定满足\( 2^{h-1}\le n\le 2^h-1. \tag{1} \)
由式 (1) 可得\(2^{h-1}\le n<2^h.\)两边取以 (2) 为底的对数，得到\(h-1\le \log_2 n\<h.\)因为 h-1 是整数，所以\(\left\lfloor\log_2 n\right\rfloor=h-1.\)因此\( h=\left\lfloor\log_2 n\right\rfloor+1 \)
由式 (1) 可得\(2^{h-1}+1\le n+1\le 2^h.\)进而有\(2^{h-1}\<n+1\le 2^h.\)两边取以 2 为底的对数，得到
\(h-1<\log_2(n+1)\le h.\)因为 h 是整数，所以\( h=\left\lceil\log_2(n+1)\right\rceil \)
综上，具有 n 个结点的完全二叉树的高度为\( h=\left\lfloor\log_2 n\right\rfloor+1 \=\left\lceil\log_2(n+1)\right\rceil \)
性质6：对于完全二叉树，可以由结点数\(n\)推出度为0、1和2的结点个数为\(n_0、n_1、n_2\)，因为完全二叉树最多只有一个度为1的结点，即\(n_1 = 0或n_1 = 1\)，又因为\(n_0=n_2+1\),故\(n_0+n_2=2n_2+1\)一定为奇数，所以
- 若完全二叉树有\(2k\)(偶数)个结点，则必有\(n_1=1,n_0=k,n_2=k-1\)
- 若完全二叉树有\(2k-1\)(奇数)个结点，则必有\(n_1=0,n_0=k,n_2=k-1\)
二叉树的存储结构¶
二叉树的顺序存储结构¶
利用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等等
- 用数组表示满二叉树
先分析一个简单案例。给定一个满二叉树，我们将所有节点按照层序遍历的顺序存储在一个数组中，则每个节点都对应唯一的数组索引。
根据层序遍历的特性，我们可以推导出父节点索引与子节点索引之间的“映射公式”：若节点的索引为\(i\)，则该节点的左子节点索引为\(2i+1\)，右子节点索引为\(2i+2\)
下图为满二叉树的数组表示
映射公式的角色相当于链表中的指针。给定数组中的任意一个节点，我们都可以通过映射公式来访问它的左（右）子节点。(若数组是从1开始存储，下标为\(i\)的结点的左右孩子结点(若存在)的下标分别是\(2i\)、\(2i+1\)，其双亲结点(若存在)的下标为\(⌊ i/ 2⌋\)).
若完全二叉树中共有\(n\)个结点，则
- 判断\(i\)是否有左孩子？ ———\(2i+1 <= n-1?\) （该式成立则存在左孩子，否则不存在）
- 判断\(i\)是否有右孩子？ ———\(2i+2 <= n-1?\) （该式成立则存在右孩子，否则不存在）
- 判断\(i\)是叶子结点还是分支结点？ ———\(i>⌊\frac{n-1}{2}⌋\) （该式成立则是叶子结点，否则为分支结点）
由上面可以看出，从数组下标为0的位置开始存放结点的话，有点麻烦，因此建议从下标为1的位置开始存放，那样的话这些判断就与之前在性质中提到的判断逻辑一样了。
- 用数组表示任意二叉树
然而满二叉树是一个特例，在二叉树的中间层，通常存在许多 空结点 。由于层序遍历序列并不包含这些 空结点 ，因此我们无法仅凭该序列来推测 空结点 的数量和分布位置。这意味着存在多种二叉树结构都符合该层序遍历序列。显然在这种情况下，上述的数组表示方法已经失效。
为了解决此问题，我们可以考虑在层序遍历序列中显式地写出所有空结点 。如下图所示，这样处理后，层序遍历序列就可以唯一表示二叉树了。
然而，在最坏情况下，一个高度为\(h\)且只有\(h\)个结点的单支树却需要占据近\(2^h-1\)个存储单元，如下图所示，可见其空间利用率很低
值得说明的是，完全二叉树（包括满二叉树）非常适合使用数组来表示。回顾完全二叉树的定义，空结点只出现在最底层且靠右的位置，因此所有 空结点 一定出现在层序遍历序列的末尾。这意味着使用数组表示完全二叉树时，可以省略存储所有 空结点 ，非常方便。
Tip
【结论】：用顺序存储结构如数组来存储二叉树结点元素的话，只适用于完全二叉树、满二叉树这种，对于普通的二叉树，会有很多结点空间的浪费。
【注意】：如果题目给定二叉树节点数量和高度，并规定用顺序结构存储，问你需要的存储单元数量至少是多少时，由于二叉树形态未知，因此要考虑最坏情况，即二叉树的最后一层的最右边有结点的情况，因此要按满二叉树开辟空间。
用数组存储二叉树的结构体定义与基本操作
Note
二叉树顺序存储的数据结构定义，需要注意以下两点：
1. 二叉树的结点用数组存储，每个结点需要标记“是否为空”
2. 各结点的数组下标隐含结点关系，要能根据一个结点的数组下标 i，计算出其父节点、左孩子、右孩子的数组下标
typedef struct TreeNode {
int data; //结点中的数据元素
bool isEmpty; //结点是否为空
} TreeNode;
//初始化顺序存储的二叉树，所有结点标记为"空"
void InitSqBiTree (TreeNode t[], int length) {
for (int i=0; i<length; i++){
t[i].isEmpty=true;
}
}
int main(){
TreeNode t[100]; //定义一棵顺序存储的二叉树
InitSqBiTree(t, 100); //初始化为空树
//...
}
若顺序二叉树从数组下标1开始存储结点，则：
● 结点 \(i\) 的父结点编号为\(i/2\)
● 结点\(i\) 的左孩子编号为\(i\*2\)
● 结点\(i\) 的右孩子编号为 \(i\*2+1\)
若顺序二叉树从数组下标0开始存储结点，则：
● 结点\(i\) 的父结点编号为\([(i+1)/2] - 1\)
● 结点 \(i\) 的左孩子编号为\([(i+1)2] - 1 = 2i + 1\)
● 结点\(i\)的右孩子编号为 \([(i+1)2+1] - 1 = 2i + 2\)
下面给出的是结点从下标为\(1\)处开始存储的基本操作代码，如果是从0处开始存储，结合上面的逻辑对代码稍作修改即可。
实现函数，找到结点 i 的父结点、左孩子、右孩子(结点从下标为\(1\)处开始存储)
//判断下标为 index 的结点是否为空
bool isEmpty(TreeNode t[], int length, int index){
if (index >= length || index < 1) return true; //下标超出合法范围
return t[index].isEmpty;
}
//找到下标为 index 的结点的左孩子，并返回左孩子的下标，如果没有左孩子，则返回 -1
int getLchild(TreeNode t[], int length, int index){
int lChild = index * 2; //如果左孩子存在，则左孩子的下标一定是 index * 2
if (isEmpty(t, length, lChild)) return -1; //左孩子为空
return lChild;
}
//找到下标为 index 的结点的右孩子，并返回右孩子的下标，如果没有右孩子，则返回 -1
int getRchild(TreeNode t[], int length, int index){
int rChild = index * 2 + 1; //如果右孩子存在，则右孩子的下标一定是 index * 2 + 1
if (isEmpty(t, length, rChild)) return -1; //右孩子为空
return rChild;
}
//找到下标为 index 的结点的父节点，并返回父节点的下标，如果没有父节点，则返回 -1
int getFather(TreeNode t[], int length, int index){
if (index == 1) return -1; //根节点没有父节点
int father = index / 2; //如果父节点存在，则父节点的下标一定是 index/2，整数除法会自动向下取整
if (isEmpty(t, length, father)) return -1;
return father;
}
利用上述三个函数，实现先/中/后序遍历(结点从下标为\(1\)处开始存储)
对于链式存储的二叉树，先序、中序、后序遍历的递归遍历代码实现很简单，大家都会
对于顺序存储的二叉树，利用上面封装的函数，也可以实现递归遍历
//从下标为 index 的结点开始先序遍历
void PreOrderSqTree (TreeNode *t, int length, int index){
if (isEmpty(t, length, index)) //当前为空节点
return;
visitNode(t[index]); //访问结点
PreOrderSqTree(t, length, getLchild(t, length, index)); //先序遍历左子树
PreOrderSqTree(t, length, getRchild(t, length, index)); //先序遍历右子树
}
//从下标为 index 的结点开始中序遍历
void InOrderSqTree (TreeNode *t, int length, int index){
if (isEmpty(t, length, index)) //当前为空节点
return;
InOrderSqTree(t, length, getLchild(t, length, index)); //中序遍历左子树
visitNode(t[index]); //访问结点
InOrderSqTree(t, length, getRchild(t, length, index)); //中序遍历右子树
}
//从下标为 index 的结点开始后序遍历
void PostOrderSqTree (TreeNode *t, int length, int index){
if (isEmpty(t, length, index)) //当前为空节点
return;
PostOrderSqTree(t, length, getLchild(t, length, index)); //后序遍历左子树
PostOrderSqTree(t, length, getRchild(t, length, index)); //后序遍历右子树
visitNode(t[index]); //访问结点
}
int main(){
TreeNode t[100]; //定义一棵顺序存储的二叉树
InitSqBiTree(t, 100); //初始化为空树
//...在空二叉树中插入数据
//...略
InOrderSqTree (t, 100, 1); //从根节点1出发，进行中序遍历
}
数组存储的 优劣之处
Warning
二叉树的数组表示的优点包括：
- 数组存储在连续的内存空间中，对缓存友好，访问与遍历速度较快。
- 不需要存储指针，比较节省空间。
- 允许随机访问节点。
然而，数组表示也具有一些局限性：
- 数组存储需要连续内存空间，因此不适合存储数据量过大的树。
- 增删节点需要通过数组插入与删除操作实现，效率较低。
- 当二叉树中存在大量空结点时，数组中包含的节点数据比重较低，空间利用率较低。
二叉树的链式存储结构¶
由于顺序存储空间利用率很低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树中的每个结点。在二叉树中，结点结构通常包括若干数据域和若干指针域。
因此，二叉链表至少包含3个域：数据域data、左指针域lchild和右指针域rchild；
二叉树的链式存储结构描述为
typedef struct TreeNode{
int data; //数据域；
struct TreeNode* lchild,*rchild; //左、右孩子指针；
}TreeNode,*BiTree;
//也可根据实际需要在结构体中加上一个父结点指针，这样的话查找
//父节点就不用像二叉链表从根节点开始遍历了。
typedef struct TreeNode{
int data; //数据域；
struct TreeNode* lchild,*rchild; //左、右孩子指针；
struct TreeNode* parent; //父节点指针；
}TreeNode,*BiTree;
\(n\)个结点→\(2n\)个指针域→除了根结点以外，其余结点头上都会连一个指针→所以有\(n-1\)个结点连有指针→还剩下\(n+1\)个空链域。
//定义一棵空树
BiTree root = NULL;
//插入根结点
root = (BiTree)malloc(sizeof(TreeNode));
root -> data = 1;
root -> lchild = NULL;
root -> rchild = NULL;
//插入新结点
TreeNode *p = (TreeNode*)malloc(sizeof(TreeNode));
p -> data = 2;
//TreeNode *p = new TreeNode(2); //c++描述；
p -> lchild = NULL;
p -> rchild = NULL;
root ->lchild = p; //作为根节点的孩子