第五章 树与二叉树
计算机学科基础：数据结构第五章树与二叉树学习笔记
1.树的基本概念（✠）
①树的定义：
- 树是n(n≥0)个结点的有限集，是一种递归定义的数据结构。当n=0时，称为空树。
- 在任意一棵非空树中应满足
- 有且仅有一个特定的称为根的结点。
- 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2……Tm
其中每个集合本身又是一棵树，并且称为根的子树。
②树的基本术语
- 结点的关系图谱：祖先、子孙、双亲（父节点）（根结点是唯一没有双亲的结点）
孩子、兄弟（有相同双亲的结点）、堂兄弟（同一层非同父节点） - 路径和路径长度。
- 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数；
- 树的路径长度是从树根到每个结点的路径长度的总和（路径只能是由上往下的，同一层之间不存在路径）
- 结点的深度、层次（从上往下数）；结点的高度（从下往上数）；树的高度（或深度）是树中结点的最大层数
- 度：一个结点的孩子个数；
树的度：树中结点的最大度数- 如度为4的树：存在某结点至少有4个孩子结点（而不是至少在某一层正好有4个结点）
- 度大于0：分支节点（每个结点的分支数就是该结点的度）
- 度等于0：叶子节点
- 有序树与无序树（从左到右有无次序）
- 森林：森林是m(m≥0)棵互不相交的树的集合
- 结点的关系图谱：祖先、子孙、双亲（父节点）（根结点是唯一没有双亲的结点）
- ③树的性质（选择题考点✪）
- 树的结点数=总度数+1（总度数也等于分支数）
- 例，此题选B，由总度数+1=结点数，叶子结点个数=总度数-其它非叶子结点的结点个数
- 例，此题选B，由总度数+1=结点数，叶子结点个数=总度数-其它非叶子结点的结点个数
- 区分度为m的树和m叉树
- 度为m的树第i层最多有$m^{i-1}$个结点(i≥1)；m叉树第i层最多有$m^{i-1}$个结点 (i≥1)
- 高度为h的m叉树最多有$\frac{m^{h}-1}{m-1}$个结点（由等比数列求和公式得）
- 高度为h的m叉树最少有h个结点；高度为h，度为m的树最少有h+m-1个结点
- 此时也可以反过来说，度为m，结点数为n的树，高度最多为n-m+1
- 图片
- 具有n个结点的m叉树（或度为m）的最小高度为 $\left\lceil\log _{m}(n(m-1)+1)\right\rceil$
- 树的结点数=总度数+1（总度数也等于分支数）
2.二叉树（✪）
①二叉树的定义
- 二叉树是n(n≥0)个结点的有限集合，其特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点）
- 或者为空二叉树，即n=0
- 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。
左子树和右子树又分别是一棵二叉树（二叉树是有序树，左右次序不能颠倒）
②特殊的二叉树
- 满二叉树
- 一棵高度为h，且含有$2^{h}-1$个结点的二叉树称为满二叉树，即树中的每层都含有最多的结点
- 满二叉树的叶结点都集中在二叉树的最下一层，并且除叶结点之外的每个结点度数均为2，不存在度为1的结点
- 按层序从1开始编号，结点ⅰ的左孩子为2i，右孩子为2i+1，结点i的父节点 ⌊i/2⌋（如果有的话）
- 完全二叉树
- 高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树
- 若i ≤ ⌊n/2⌋，则结点i为分支结点，否则为叶结点。
- 若一棵完全二叉树中的结点无左孩子，则其必是叶节点
- 叶结点只可能在层次最大的两层上出现。对于最大层次中的叶结点，都依次排列在该层最左边的位置上。
- 若有度为1的结点，则只可能有一个，且该结点只有左孩子而无右孩子（重要特征）。
- 按层序编号后，一旦出现某结点（编号为i）为叶结点或只有左孩子，则编号大于i的结点均为叶结点。
- 若结点数n为奇数，则每个分支结点都有左孩子和右孩子；
- 若n为偶数，则编号最大的分支结点(编号为n/2)只有左孩子，没有右孩子，其余分支结点左、右孩子都有。
- 图片
- 二叉排序树
- 左子树上所有结点的关键字均小于根结点的关键字
- 右子树上的所有结点的关键字均大于根结点的关键字
- 左子树和右子树又各是一棵二叉排序树。
- 将二叉排序树的先序序列中的关键字依次插入初始为空的树中，所得到的二叉排序树与原二叉排序树是相同的
- 平衡二叉树：树上任意一个结点的左子树和右子树的深度之差不超过1。
- 对于高度为n的平衡二叉树，最少需h(n)个结点，最多需要2n-1个结点。
- h(n)=h(n-1)+h(n-2)+1
- h(0)=0，h(1)=1，h(2)=2
- 满二叉树
③二叉树的性质（选择题考点♚）
- 非空二叉树上的叶结点数等于度为2的结点数加1，即$n_{0}=n_{2}+1$
- 可由$n=n_{0}+n_{1}+n_{2}$与$n=n_{1}+2n_{2}+1$得来
- 二叉树第i层上至多有$2^{i-1}$个结点(i≥1)
- 高度为h的二叉树至多有$2^{h}-1$个结点（满二叉树），最少有$2^{h-1}$个结点
- 具有n个${(n>0)}$ 结点的完全二叉树的高度h为${\left\lceil\log _{2}(n+1)\right\rceil}$ 或 $\left\lfloor\log _{2} n\right\rfloor+1$
- 第i个结点所在层次为${\left\lceil\log _{2}(n+1)\right\rceil}$ 或 $\left\lfloor\log _{2} n\right\rfloor+1$
- 对于完全二叉树，可以由节点数推出各类结点的数量情况，分为结点总数n为奇数或偶数
- 完全二叉树的度为1的结点数量最多为1，$n_{1}=1或0$
- 当n=2k时，此时$n_{1}=1,n_{0}=k,n_{2}=k+1$ （完全二叉树有偶数个结点时，叶子结点的个数为总结点数除以2）
- 当n=2k-1时，此时$n_{1}=0,n_{0}=k,n_{2}=k+1$（有奇数个结点时，叶子结点的个数为总结点数+1再除以2）
- 完全二叉树如果所有的非空结点都有两个子节点，说明其有奇数个结点，此时结点总数=2*叶子节点总数-1
- 有关性质例题的考察
- 例题1：这种题通过画出二叉树的情况来找规律即可，选B
- 例题2：给出完全二叉树具体一层的叶结点数量，求最多和最少得结点总数
（重要信息：完全二叉树的叶结点只有可能存在于最后一层和倒数第二层）- 结点数量最少时，该层即为最后一层，如此题为前五层满二叉树+8=39，
- 结点数量最多时，该层为倒数第二层，如此题为总七层-8*2=111
- 例题3：最小高度往往是满二叉树时，存放该二叉树至少需要的结点数量（最坏的情况，也为满二叉树时）分别选C、A
- 例题1：这种题通过画出二叉树的情况来找规律即可，选B
- 非空二叉树上的叶结点数等于度为2的结点数加1，即$n_{0}=n_{2}+1$
④二叉树的存储结构
二叉树的顺序存储
对于完全二叉树，顺序存储的结构较为合适，此时可以较好的反映出结点之间的逻辑关系，也能节省存储空间
对于一般的二叉树，需要用0来表示并不存在的空结点，以便于反映二叉树的逻辑结构，但是此时会浪费较多的存储空间
二叉树的链式存储
又称为二叉链表，由数据域，左指针域，右指针域组成
n个结点的二叉链表共有n+1个空链域，有n-1个非空链域
链域是指左指针或右指针关于三叉链表：再定义一个父指针指向父节点，方便查找（在后序线索树中可找到后序后继结点）
链式存储的代码实现
定义
1
2
3
4typedef struct BiTNode{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree初始化以及插入节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14BiTree root=NULL; //定义一颗空树
//插入根节点
root=(BiTree)malloc(sizeof(BiTNode));
root->data=1;
root->lchild=NULL;
root->rchlid=NULL;
//插入新结点
BiTNode *p=(BiTNode *)malloc(sizeof(BiTNode));
p->data=2;
p->lchild=NULL;
p->rchild=NULL;
root->lchild=p;
3.二叉树的遍历（✪）
三种基本遍历
如中序遍历，先递归遍历左子树，再访问根节点，再递归遍历右子树，二叉树为空则什么都不做。
这三种遍历方法的时间复杂度都是O(n)，每个结点都会被访问一次
二叉树的前中后序遍历中，所有叶节点的顺序完全相同
若一个二叉树的先序和后序序列正好相反，则该二叉树的高度等于结点数，只有一个叶节点
先序序列与中序序列的关系相当于，以先序序列为入栈次序，以中序队列为出栈次序
先序序列为a,b,c,d，求不同二叉树的个数（使用卡特兰数的公式$\frac{1}{n+1}C^{n}_{2n}$）
可用递归子树思想的方法来求出遍历次序
先序遍历（NLR，根左右）
在前序遍历的二叉树中，任何结点的子树的所有结点都是直接跟在该结点的之后1
2
3
4
5
6
7void PreOrder(BiTree T){
if(T!=NULL){
visit(T);
preOrder(T->lchild);
preOrder(T->rchild);
}
}中序遍历（LNR，左根右）
1
2
3
4
5
6
7void InOrder(BiTree T){
if(T!=NULL){
InOrder(T->lchild);
visit(T);
InOrder(T->rchild);
}
}后序遍历（LRN，左右根，可找到从子孙到祖先的路径）
1
2
3
4
5
6
7void PostOrder(BiTree T){
if(T!=NULL){
PostOrder(T->lchild);
PostOrder(T->rchild);
visit(T);
}
}求树的深度
层次遍历二叉树
由遍历构造二叉树
- 若只给出一棵二叉树的前/中/后/层序遍历序列中的一种，不能唯一确定一棵二叉树，需要和中序遍历组合才行
- 前序加中序确定二叉树结构
- 以前序序列的第一个单位为准，在中序遍历中确定其左右子树，之后的子树的根节点都以前序遍历靠前的元素为准
- 后序加中序确定二叉树结构
- 以后序遍历的最后一个元素为准，在中序遍历中确定其左右子树，之后的子树的根节点都以后序遍历靠后的元素为准
- 层序加中序确定二叉树结构
4.线索二叉树（选择题考点，代码无需掌握✪）
作用：方便从一个结点出发，找到其前驱、后继，
此时先序线索二叉树和中序线索二叉树进行遍历时不需要栈的支持（进行）递归，但是后序线索二叉树仍需要栈的支持线索：指向前驱和后继的指针，n个结点的二叉树含有n+1个空指针
n个结点的线索二叉树含有n+1个线索二叉树的线索化就是将二叉链表中的空指针改为指向前驱或后驱的线索
按照遍历的顺序进行，如果指针已经指向相应结点则不变动，如果没有空指针就跳过）存储结构
- 在普通二叉树结点的基础上，增加标志位：Itag和rtag （等于0此结点有孩子，等于1此结点被线索化）
- ltag\==1时，表示Ichild指向前驱；Itag\==0时，表示Ichild指向左孩子
- rtag\==1时，表示rchild指向后继；rtag\==0时，表示rchild指向右孩子
线索化二叉树（代码了解即可）
线索二叉树的存储结构
1
2
3
4
5typedef struct ThreadNode{
int data;
struct ThreadNode *lchild,*rchild; //左右孩子指针
int ltag,rtag; //左右线索标志
}ThreadNode,*ThreadTree;中序线索化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24void CreateInThread(ThreadTree T){
ThreadTree pre=NULL; //设定当前访问结点的前驱，并初始化
if(T!=NULL){ //线索化非空二叉树
InThread(T,pre);
pre->rchild=NULL; //处理遍历的最后一个结点
pre->rtag=1; //改变其标志符
}
}
void InThread(ThreadTree &p,ThreadTree &pre){
if(p!=NULL){
InThread(p->lchild,pre); //递归，线索化左子树（按照中序遍历，先遍历左子树）
if(p->lchild==NULL){ //若当前结点左子树为空时，建立前驱线索,左指针指向前驱
P->lchild=pre;
p->ltag=1;
}
if(pre!=NULL&&pre->rchild==NULL){
pre->rchild=p; //建立前驱节点的后继线索
pre->rtag=1;
}
pre=p; //完成以上操作之后，将前驱结点指向当前所遍历到的结点
InThread(p->rchild,pre); //递归线索化右子树
}
}对于先序线索化而言只需要将其线索化左子树的操作写在前面，中间是根结点的操作，最后是线索化右子树的操作
- 注：此时在ltag==0时，才能对左子树先序线索化
对于后序线索化而言只需要将其线索化左子树的操作写在前面，中间是线索化右子树的操作，最后是根结点的操作
线索二叉树的遍历（会推出各种遍历序列即可✪）
中序线索二叉树的遍历
进行遍历时，只要先找到序列中的第一个结点，然后依次找结点的后继，直至其后继为空。
首先找到中序线索二叉树的第一个结点 （最左下的结点，不一定为叶节点）
代码实现（求中序线索二叉树中中序序列下的第一个结点）
1
2
3
4
5ThreadNode *Firstnode(ThreadNode *p){
while(p->ltag==0)
p=p->lchild; (遍历找到最左下的结点，不一定是叶结点)
return p;
}
之后找中序后继结点
若此时p->rtag==1,则next=p->rchild （此时右链为线索，指向其后继）
p->ratg==0时，此时右子树不为空，则遍历右子树的第一个访问结点（右子树最左下的结点为其后继）
代码实现（求中序线索二叉树中结点p在中序序列下的后继）
1
2
3
4
5
6ThreadNode *Nexttnode(ThreadNode *p){
if(p->rtag==0)
return Firstnode(p->rchild); //不为空，找到其右子树的最左下角的结点
else
return p->rchild; //右标志为1直接返回线索
}
遍历中序二叉树的代码实现
1
2
3
4void Inorder(ThreadNode *T){
for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))
visit(p);
}中序线索二叉树找到中序前驱
- 若此时p->ltag==1，此时直接返回左线索
- 若此时p->ltag==0，则p结点的左子树中，最右下角的结点就是其前驱结点
先序线索二叉树的遍历
先序线索二叉树的先序后继
- 若右标志位为0时，首先看先序线索二叉树有无左孩子，如果有的话，就是其先序后继，如果只有右孩子没有左孩子，那么右孩子为其先序后继
- 图片
先序线索二叉树不能在左标志位为0的情况下找到先序前驱
后序线索二叉树的遍历
后序线索二叉树找后序前驱
- 若左标志位为0时，此时如果其有右孩子，那么此右孩子为其后序前驱，如果只有左孩子没有右孩子，那么左孩子为其后序前驱
后序线索二叉树找后序后继
- 如果此时右标志位为0，则不能有效的找到后序后继
- 此时可以用三叉链表来找到其后序后继
三种线索二叉树遍历的总结
- 对于中序线索二叉树来说可从任意结点进行遍历和逆向遍历；对于前序线索二叉树来说，只可进行顺向遍历；对于后序线索二叉树来说，只可进行逆向遍历
5.树、森林（✪）
树的存储结构（✪）
双亲表示法（顺序存储✪）
这种存储结构采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。
根结点下标为0，其伪指针域为-1。特点：该存储结构利用了每个结点（根结点除外）只有唯一双亲的性质，可以很快地得到每个结点的双亲结点，
但求结点的孩子时则需要遍历整个结构。适用于找父节点较多找孩子结点较少的树，如并查集
代码表示
1
2
3
4
5
6
7
8
9
10
typedef struct{ //树的结点定义
ElemType data;
int parent; //双亲位置域
}PTNode;
typedef struct{ //树的类型定义
PTNode nodes[MAX_TREE_SIZE]; //双亲表示法
int n; //结点数
}PTree;图片
孩子表示法（顺序存储+链式存储）
孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n个结点就有n个孩子链表
叶结点的孩子链表为空表用数组顺序存储各个结点。每个结点中保存数据元素、孩子链表头指针
特点：这种存储结构寻找子女的操作非常直接，而寻找双亲的操作需要遍历个结点中孩子链表指针域所指向的n个孩子链表，适用于服务流程树。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13struct CTNode{
int child; //孩子结点在数组中的位置
struct CTNode *next; //下一个孩子
};
typedef struct{
ElemType data;
struct CTNode *firstChild; //第一个孩子
}CTBox;
typedef struct{
CTBox nodes[MAX_TREE_SIZE];
int n,r; //结点数与根的位置
}CTree;图片
孩子兄弟表示法（链式存储✪）
又称为二叉树表示法，即以二叉链表作为树的存储结构，
包括结点值，指向结点第一个孩子的结点指针，以及指向结点下一个兄弟结点的指针特点：易于查找孩子，但是不易于查找双亲，可以方便实现树转换成二叉树的操作。
代码实现
1
2
3
4typedef struct CSNode{
ElemType data;
struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;图片
树、森林与二叉树的转换（会画✪）
- 树转换为二叉树：转换后的二叉树一定没有右子树
- 森林转换为二叉树
- 二叉树转换为树
- 二叉树转换成森林
- 树转换为二叉树：转换后的二叉树一定没有右子树
树和森林的遍历（✪）
- 树的遍历
- 先根遍历（等同于对相应二叉树的先序遍历）
- 后根遍历（等同于对相应二叉树的中序遍历）
- 层序遍历
- 先根遍历（等同于对相应二叉树的先序遍历）
- 森林的遍历
- 先序遍历（等同于对所对应的二叉树依次进行先序遍历）
- 中序遍历（等同于对所对应的二叉树依次进行中序遍历）
- 先序遍历（等同于对所对应的二叉树依次进行先序遍历）
- 树的遍历
6.树与二叉树的应用（✪）
哈夫曼树和哈夫曼编码
- 带权路径长度：从树的根到任意结点的路径长度（经过的边数）与该结点上权值的乘积，称为该结点的带权路径长度。
树中所有叶结点的带权路径长度之和称为该树的带权路径长度（WPL）。 - 哈夫曼树
- 在含有个带权叶结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树，也称最优二叉树
- 哈夫曼树的构造
- 图片
- 注：如果之后的两个单独的叶子结点的构造出的权值比它于树的根构造出的权值更小，那么两个叶子结点先自行构造
- 如此题选C，此时9和12先进行自行的构造
- 如此题选C，此时9和12先进行自行的构造
- 图片
- 特点
- 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
- 构建过程中共创建了n-1个新结点（非叶结点），哈夫曼树的结点总数为2n-1
- 如此题：度为m,此时若含有n个叶子结点，则总的需要处理的结点数为n-1个，此时每次将处理m-1个，因此非叶子结点的数量为$\frac{n-1}{m-1}$
- 如此题：度为m,此时若含有n个叶子结点，则总的需要处理的结点数为n-1个，此时每次将处理m-1个，因此非叶子结点的数量为$\frac{n-1}{m-1}$
- 哈夫曼树中不存在度为1的结点。
- 哈夫曼树并不唯一，但WPL必然相同且为最优
- 哈夫曼编码（一种被广泛应用而且非常有效的数据压缩编码）
- 固定长度编码与可变长度编码
- 在数据通信中，若对每个字符用相等长度的二进制位表示，称这种编码方式为固定长度编码。
- 若允许对不同字符用不等长的二进制位表示，则这种编码方式称为可变长度编码。
- 可变长度编码比固定长度编码要好得多，其特点是对频率高的字符赋以短编码，而对频率较低的字符则赋以较长一些的编码，从而可以使字符的平均编码长度减短，起到压缩数据的效果。
- 前缀编码：若没有一个编码是另一个编码的前缀，则成为前缀编码，此时将不会产生歧义
- 采用的前一位数的编码将会影响后一位数的编码
- 例题
- 例题
- 采用的前一位数的编码将会影响后一位数的编码
- 通过哈夫曼编码可以构造哈夫曼树，此时最大编码长度为树的带权路径长度（WPL），并且可以算出压缩的数据率
- 固定长度编码与可变长度编码
- 带权路径长度：从树的根到任意结点的路径长度（经过的边数）与该结点上权值的乘积，称为该结点的带权路径长度。
并查集（集合逻辑结构）
集合的表示：要将元素划分为互不相交的子集。可以用互不相交的树，来表示多个集合
存储结构：使用双亲表示法，双亲指针指向其父节点的序号
基本操作
初始化：将所有元素初始化为-1。
代码表示
1
2
3
4
5
6
7
int UFSets[SIZE]; //双亲指针数组
void Initial(int S[]){
for(int i=0;i<SIZE;i++)
S[i]=-1; //初始化时，数组指针设置为-1
}
查操作（时间复杂度为 O(n)）
如何查到某个元素属于哪个集合：可以通过树的根结点来判断
如何判断两个元素之间的关系：通过对比各自所在的树的根结点来判断
代码表示
1
2
3
4
5int Find(int S[],int x){
while(S[x]>=0) //循环寻找x的根（一般设置为-1）
x=S[x];
return x; //此时找到x的根，返回之
}
并操作（时间复杂度为 O(1)，并操作n个独立元素为一个集合则需要O($n^{2}$)）
让一棵树成为另一棵树的子树即可
1
2
3
4void Union(int S[],int Root1,int ROOt2){
if(Root1==Root2) return; //此时要求两个是不同的集合
S[Root2]=Root1; //将根Root2连接到另一根Root1下面
}
对并查集的并操作作优化
- 此时将根结点的值设置为负数（表示其树的结点的总数，有利于将较小的树合并到更大的树，可以控制高度不变）
- 当合并时，小树的双亲指针变为大树的数组下标，此时大树的指针需要累加结点总数
- 进行优化之后，查操作的时间复杂度可变为：$O ( \log _ { 2 } n )$
- 图片
对并查集的进一步优化（优化查操作）
并查集的优化后的时间复杂度的变化
