树和二叉树

树的定义和基本术语

注：这一节一些概念的具体定义请见书本

树的基本概念

课本上对于树的定义：

树是$n(n\ge 0)$个结点的有限集合，$n=0$时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：

1.有且仅有一个特定的称为根的结点

2.当$n>1$时，其余结点可分为$m(m>0)$个互不相交的有限集合$T_1,T_2,...,T_m$，其中每个集合本身又是一棵树，并且称为根结点的子树

 

自行分辨以下概念

• 根节点
• 边
• 结点
• 分支结点
• 叶子结点
• 空树——结点数为0的树
• 非空树——有且仅有一个根节点

非空树的特性：

1.有且仅有一个根节点

2.没有后继的结点称为“叶子结点”（或终端结点）

3.有后继的结点称为“分支结点”（或非终端结点）

4.除了根节点外，任何一个结点都有且仅有一个前驱，每个结点可以有0个或多个后继

• 子树

树是一种递归定义的数据结构，任何一个树都可以看成是由一个根结点和多个子树所组成的

结点之间的关系描述

自行分辨以下概念

• 祖先结点
• 子孙结点
• 双亲结点（父结点）
• 孩子结点
• 兄弟节点
• 堂兄弟结点
• 路径

当我们在树里面描述两个结点之间的路径时，路径只能是从上往下单向的，即树里面的边实际是有向边

• 路径长度

结点，树的属性描述

• 结点的层次（深度）——从上往下数第几层

默认从1开始

• 结点的高度——从下往上数，越往上高度越高
• 树的高度（深度）——总共多少层
• 结点的度——有几个孩子（分支）

非叶子结点的度>0，叶子结点的度=0

• 树的度——各结点的度的最大值

有序树/无序树

• 有序树——从逻辑上看，树中结点的各子树从左到右是有次序的，不能互换

• 无序数——从逻辑上看，树中结点的各子树从左到右是无次序的，可以互换

森林

• 森林。森林是$m(m\ge 0)$棵互不相交的树的集合
• 空森林（$m=0$）

树的常考性质

1.结点数=总度数+1

总度数其实就是分支的总数量，而除了根节点以外，每一个结点都往上连了一个分支

 

2.度为$m$的树，$m$叉树的区别

$m$叉树——每个结点最多只能有$m$个孩子的树

 

3.度为$m$的树第$i$层至多有$m^{i-1}$个结点（$i\ge 1$）

$m$叉树的第$i$层至多有$m^{i-1}$个结点（$i\ge 1$）

 

4.高度为$h$的$m$叉树至多有$\frac{m^h-1}{m-1}$个结点

第1层：$m^0$，第2层：$m^1$，第3层：$m^2$，…，依次类推即得性质3，对该等比数列求和即得性质4

 

5.高度为$h$的$m$叉树至少有$h$个结点

​ 高度为$h$，度为$m$的树至少有$h+m-1$个结点

6.具有$n$个结点的$m$叉树的最小高度为$[log(n(m-1)+1)]$

高度最小的情况时所有结点都有$m$个孩子。前$h-1$层最多有$\frac{m^{h-1}-1}{m-1}$，前$h$层最多有$\frac{m^h-1}{m-1}$个结点。可得等式$\frac{m^{h-1}-1}{m-1}<n\le \frac{m^h-1}{m-1}$。化简后得$m^{h-1}<n(m-1)+1\le m^h$，对两边取对数后得$h-1<lo{g}_m(n(m-1)+1)\le h$，得$h_{min}=[lo{g}_m(n(m-1)+1)]$

二叉树的定义及基本性质

二叉树的基本概念

二叉树是$n(n\ge 0)$个结点的有限集合：

1.或者为空二叉树，即$n=0$

2.或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树

特点：

1.每个结点至多只有两颗子树

2.左右子树不能颠倒（二叉树是有序数）

注意与度为2的有序树的区别

二叉树是递归定义的数据结构

因为上述定义中的左右子树都可以是空二叉树，所以二叉树可能有下图的五种状态

几个特殊的二叉树

满二叉树与完全二叉树

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

特点：

1.只有最后一层有叶子结点

2.不存在度为1的结点，度要么为0要么为2

3.按层序从1开始编号，结点$i$的左孩子为$2i$，右孩子为$2i+1$；结点$i$的父节点为$[i/2]$（如果有的话）

这个性质有利于我们用顺序存储的方式存储这些结点

 

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

在满足一一对应的原则下从满二叉树中删去几个编号较大的结点

特点：

1.只有最后两层可能有叶子结点

2.最多只有一个度为1的结点

这条性质在笔试中用的很多

3.与满二叉树一样，按层序从1开始编号，结点$i$的左孩子为$2i$，右孩子为$2i+1$；结点$i$的父节点为$[i/2]$（如果有的话）

4.$i\le [n/2]$为分支结点，$i>[n/2]$为叶子结点

5.完全二叉树中，如果某一个结点只有一个孩子，这个孩子一定是左孩子不是右孩子

 

下图中左边为满二叉树，右边为完全二叉树

二叉排序树

二叉排序树。一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：

左子树上所有结点的关键字均小于根结点的关键字；

右子树上所有结点的关键字均大于根结点的关键字。

左子树和右子树又各是一棵二叉排序树

二叉排序树可用于元素的排序，搜索

平衡二叉树

平衡二叉树。树上任一结点的左子树和右子树的深度之差不超过1

 

下图中左边是平衡二叉树，右边就不是平衡二叉树

尽可能地追求左右子树的平衡就能得到更好更高效的二叉排序树。上面的两个例子都是二叉排序树，并且里面存的元素也都是一样的。可以明显看到虽然都是二叉排序树，平衡二叉树能有更高的搜索效率

平衡二叉树希望树在生长的时候尽量往宽处长，高度尽可能的低。这样从根节点开始往下搜索一个元素的时候，因为高度不会很高，对比的次数也就相应减少

二叉树的常考性质

二叉树的常考性质

1.设非空二叉树中度为0，1，2的结点个数分别为$n_0,n_1,n_2$，则$n_0=n_2+1$（叶子结点比二分支结点多一个）

推导过程：假设树中结点总数为$n$，则联立$n=n_0+n_1+n_2$和$n=n_1+2n_2+1$（树的结点数=总度数+1）可得上述结论

这条性质很重要，在选填中经常会考察

2.二叉树的第$i$层至多有$2^{i-1}$个结点$(i\ge 1)$

推导过程：把$m=2$代入上节树的性质3即可得

 

3.高度为$h$的二叉树至多有$2^h-1$个结点（满二叉树）

推导过程：把$m=2$代入上节树的性质4即可得

完全二叉树的常考性质

1.具有$n(n>0)$个结点的完全二叉树的高度$h$为$[lo{g}_2(n+1)]$或$[lo{g}_{2}n]+1$

推导过程：

法一：已知高为$h$的满二叉树共有$2^h-1$个结点，高为$h-1$的满二叉树共有$2^{h-1}-1$个结点，则
$$\begin{gathered} 2^{h-1}-1<n\le 2^h-1 \\ {2}^{h-1}<n+1\le 2^h \\ h-1<lo{g}_2(n+1)\le h \\ h=[lo{g}_2(n+1)] \end{gathered}$$

法二：已知高为$h-1$的满二叉树共有$2^{h-1}-1$个结点，则高为$h$的完全二叉树至少$2^{h-1}$个结点。高为$h$的完全二叉树至多$2^h-1$个结点，则
$$\begin{gathered} 2^{h-1}\le n<2^h \\ h-1\le lo{g}_{2}n<h \\ h=[lo{g}_{2}n]+1 \end{gathered}$$

2.对于完全二叉树，给定结点数$n$推出度为0，1，2的结点个数为$n_0,n_1,n_2$

推导过程：已知1.完全二叉树最多只有一个度为1的结点，即$n_1=0$或$1$。2.$n_0=n_2+1$，故$n_0+n_2$一定为奇数，则

若完全二叉树有$2k$（偶数）个结点，则必有$n_1=1,n_0=k,n_2=k-1$

若完全二叉树有$2k-1$（奇数）个结点，则必有$n_1=0,n_0=k,n_2=k-1$

树的存储结构

二叉树的顺序存储

完全二叉树

先以一个完全二叉树为例演示顺序存储一个二叉树

要存储一个完全二叉树，可定义一个长度为$MaxSize$的数组$t$，按照从上到下，从左到右的顺序依次存储完全二叉树中的各个结点。这里可以让第一个位置空缺，保证数组下标和结点编号一致

#define MaxSize 10
struct TreeNode{
    ElemType value; //结点中的数据元素
    bool isEmpty;   //结点是否为空
}
TreeNOde t[MaxSize] //数组t按照从上到下，从左到右的顺序依次存储完全二叉树中的各个结点
    
//初始化操作
for(int i=0;i<MaxSize;i++){
    t[i].isEmpty=true;
}
1
2
3
4
5
6
7
8
9
10
11

这种存储关系要反映各个结点之间的前驱后继关系，或者说父子的关系，可以通过如下几个重要基本操作

• $i$的左孩子——$2i$
• $i$的右孩子——$2i+1$
• $i$的父节点——$[i/2]$
• $i$所在的层次——$[lo{g}_2(n+1)]$或$[lo{g}_{2}n]+1$

完全二叉树中共有$n$个结点，则

• 判断$i$是否有左孩子？——$2i\le n$?
• 判断$i$是否有右孩子？——$2i+1\le n$?
• 判断$i$是否是叶子/分支结点？——$i>[n/2]$?

非完全二叉树

如果像下图一样不是完全二叉树时呢？

为了使用上面罗列的法则来快速判断各个结点之间的前驱后继关系，二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来

现在若给定一个编号为$i$的结点，则和完全二叉树的情况一样

• $i$的左孩子——$2i$
• $i$的右孩子——$2i+1$
• $i$的父节点——$[i/2]$

但是现在如果要判断一个结点$i$是否有左孩子，右孩子，是不是叶子/分支结点就不能像之前那样用它的结点编号和结点的总数$n$作比较来判断，而是用$isEmpty$字段来判断。例如如果要查看编号为$i$结点是否存在左孩子，就看编号为$2i$的结点的$isEmpty$字段是否为$True$

• 判断$i$是否有左孩子？——$2i\le n$?
• 判断$i$是否有右孩子？——$2i+1\le n$?
• 判断$i$是否是叶子/分支结点？——$i>[n/2]$?

显然二叉树的顺序存储会有大量的空间是浪费的，因此二叉树的顺序存储只适合存储完全二叉树

最坏情况：高度为$h$的且只有$h$个结点的单支树（所有结点只有右孩子），也至少需要$2^h-1$个存储单元

二叉树的链式存储

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

若有n个结点，则有2n个指针域，而除了根结点每个节点头上都会连一个指针，故n个结点的二叉链表共有n+1个空链域。这些空出的空链域可以用于构造线索二叉树

构建链式二叉树

现在演示用代码实现如下过程

struct ElemType{
    int value;
};

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

//定义一颗空树
BiTree root=NULL;

//插入根节点
root=(BiTree)malloc(sizeof(BiTNode));
root->data={1};
root->lchild=NULL;
root->rchild=NULL;

//插入新结点作为根结点的左孩子
BiTNode*P=(BiTNode*)malloc(sizeof(BitNode));
p->data={2};
p->lchild=NULL;
p->rchild=NULL;
root->lchild=p;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

利用类似的方法就可以得到一棵二叉树

现在要找到指定结点的左/右孩子很简单，但是找到指定结点的父结点就只能从根开始遍历寻找。如果要频繁的查找父结点，就需要用到三叉链表

typedef struct BiTNode{
    ElemType data;                       
    struct BiTNode *lchild,*rchild;      
    struct BitNode *parent;             //父结点指针
}BiTNode,*BiTree;
1
2
3
4
5

二叉树的先中后序遍历

先中后序遍历利用二叉树的递归特性制定遍历规则。复习之前二叉树的定义也可以得出二叉树本身就是递归定义的数据结构。

 

二叉树的递归特性：

1.要么是个空二叉树

2.要么就是由“根节点+左子树+右子树”组成的二叉树（当然左右子树也有可能是空二叉树）

现在基于这种递归特性制订规则：

1.如果要遍历的二叉树是空二叉树就什么都不做

2.如果是非空二叉树，可以根据根/左子树/右子树被访问的顺序这样三种规则

• 先序遍历：根左右（NLR）
• 中序遍历：左根右（LNR）
• 后序遍历：左右根（LRN）

如果子树还有下一级的结点，则要根据同样的遍历规则来遍历这颗子树

 

下面给出一个具体的例子演示三种规则的遍历顺序：

先序遍历：A B D G E C F

中序遍历：D G B E A F C

后续遍历：G D E B F C A

这些叶子结点应该把它理解为下面还连了两个空子树，只不过对空子树的遍历不用写上

二叉树的遍历（手算练习）

手算先中后序遍历顺序可以采用分支结点逐层展开法，先不管结点有没有后续结点都写上，下一步再对该结点进行展开遍历

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-myrcCS8f-1660133432887)(数据结构.assets/image-20220810105727520.png)]

下面再给一个具体的例子：

对这棵树的遍历结果是：

先序遍历：-+a*b-cd/ef

中序遍历：a+b*c-d-e/f

后续遍历：abcd-*+ef/-

补充：这棵树实际上是由算术表达式a+b*(c-d)-e/f得到的“分析树”。对这棵分析树进行先/中/后序遍历的得到的遍历序列实际上分别对应的是这个算术式的前/中/后缀表达式（不过要注意遍历得到的“中缀表达式”还需要加界限符才是完整的）

先中后序遍历的代码实现

先序遍历

先序遍历的操作过程：

1.若二叉树为空，则什么也不做

2.若二叉树非空

1. 访问根结点
2. 先序遍历左子树
3. 先序遍历右子树

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

//先序遍历
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);               //访问根结点
        PreOrder(T->lchild);    //递归遍历左子树
        Preorder(T->rchild);    //递归遍历右子树
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

 

下面看一下先序遍历的递归实现过程：

下图中红色箭头表示第一次路过，绿色箭头表示第二次路过，紫色箭头表示第三次路过

脑补空结点，从根结点出发，画一条路：

如果左边还有没走的路，优先往左走。走到路的尽头（空结点）就往回走。如果左边没路了，就往右边走。如果左右都没有路了，则往上边走。

先序遍历第一次路过时访问结点，显然每个结点都会被路过三次

中序遍历

中序遍历的操作过程：

1.若二叉树为空，则什么也不做

2.若二叉树非空

1. 中序遍历左子树
2. 访问根结点
3. 中序遍历右子树

void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);    //递归遍历左子树
        visit(T);              //访问根结点
        Inorder(T->rchild);    //递归遍历右子树
    }
}
1
2
3
4
5
6
7

 

下面看一下中序遍历的递归实现过程：

可以看出每个结点都会被路过三次，画一条路的方式和先序遍历一样。区别在于第二次路过时才会访问结点

后序遍历

后序遍历的操作过程：

1.若二叉树为空，则什么也不做

2.若二叉树非空

1. 后序遍历左子树
2. 后序遍历右子树
3. 访问根结点

void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);    //递归遍历左子树
        Postorder(T->rchild);    //递归遍历右子树
        visit(T);                //访问根结点
    }
}
1
2
3
4
5
6
7

 

下面看一下后序遍历的递归实现过程：

可以看出每个结点都会被路过三次，画一条路的方式和先序遍历一样。区别在于第三次路过时才会访问结点

递归实现的算法空间复杂度为$O(h)$,$h$指二叉树的深度

画路的方法也能用来手算一棵已知二叉树用不同遍历方式得到的序列

应用：求树的深度

要求一棵二叉树的深度，根据二叉树的递归特性（分为根节点，左子树，右子树）可以先递归地求出左子树和右子树的高度，然后选取左子树和右子树中高度高的一边$+1$这样就求出了树的深度，下面的代码其实就是后序遍历的变种

int treeDepth(BiTree T){
    if(T==NULL){
        return 0;
    }else{
        int l=treeDepth(T->lchild);
        int r=treeDepth(T->rchild);
        //树的深度=Max(左子树深度，右子树深度)+1
        return l>r?l+1:r+1;
    }
}
1
2
3
4
5
6
7
8
9
10

二叉树的层序遍历

采用辅助队列实现按层序遍历二叉树

算法思想：

1.初始化一个辅助队列

2.根结点入队

3.若队列非空，则队头结点出队，访问该结点，并将其左右孩子插入队尾（如果有的话）

4.重复3直至队列为空

层序遍历的代码实现

//二叉树的结点（链式存储）
typedef struct BiTNode{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//链式队列结点
typedef struct LinkNode{
    BiTNode *data; //存指针而不是结点
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front,*rear; //队头队尾
}LinkQueue;

//层序遍历
void LevelOrder(BiTree T){
    LinkQueue Q;
    InitQueue(Q);                   //初始化辅助队列
    BiTree p;
    EnQueue(Q,T);                   //将根结点入队
    while(!IsEmpty(Q)){             //队列不空则循环
        DeQueue(Q,p);               //队头结点出队
        visit(p);                   //访问出队结点
        if(p->lchild!=NULL){
            EnQueue(Q,p->lchild);   //左孩子入队
        }
        if(p->rchild!=NULL){
            EnQueue(Q,p->rchild);    //右孩子入队
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

上面一直在说让某一个结点入队，但是我们并不用在队列中保存整个结点的真实数据，而是只需要保存这个结点的指针就可以了。因此让结点入队的时候其实真正入队的是这个结点的指针

由遍历序列构造二叉树

不同二叉树的中序遍历序列

中序遍历：中序遍历左子树，根结点，中序遍历右子树

从上图中可以看出一棵二叉树的中序遍历序列是唯一的，但是给定一个中序遍历序列并不能确定其对应的二叉树的形态。同一个中序遍历序列可能对应多种二叉树形态。同理同一个前/后/层序遍历序列可能对应多种二叉树形态。

因此只给出一种遍历序列是不能唯一确定一棵二叉树的。这一节学习如何利用前序+中序遍历序列/后序+中序遍历序列/层序+中序遍历序列构造二叉树

一定要有中序遍历序列才能确定一棵二叉树。没有中序遍历序列的话，前序，后序，层序序列的两两组合无法唯一确定一棵二叉树

前序+中序遍历序列

现在给定一个二叉树的前序+中序遍历序列，则

前序遍历：根结点，前序遍历左子树，前序遍历右子树。由此得出的

前序遍历序列：根结点+左子树的前序遍历序列+右子树的前序遍历序列

 

中序遍历：中序遍历左子树，根结点，中序遍历右子树。由此得出的

中序遍历序列：左子树的中序遍历序列+根结点+右子树的中序遍历序列

 

从上面可以看到前序遍历序列中最先出现的肯定是根结点，因此就可以确定根结点在中序遍历序列中的位置，在根结点左边出现的结点肯定是左子树中出现的结点，而右边的部分肯定是右子树中的结点。我们用这样的方式递归地还原这棵二叉树

 

下面给一个具体的例子来说明：

前序遍历序列：A D B C E

中序遍历序列：B D C A E

前序遍历序列中最先出现的肯定是根结点，故A可以确定是根结点。它左边的部分B D C是左子树的中序遍历序列，它右边的部分E是右子树的中序遍历序列。现在可以确定左子树中有三个结点B D C，所以在前序遍历序列中，根结点后面的三个结点肯定就是左子树的前序遍历序列，剩下的就是右子树的前序遍历序列。由相同的逻辑，D肯定是左子树的根结点，在它左边的B是它的左孩子，右边的C是它的右孩子结点。这棵二叉树还原后就是

后序+中序遍历序列

逻辑和上面的其实类似，所以写的会比较简略

后序遍历：后序遍历左子树，后序遍历右子树，根结点。由此得出的

后序遍历序列：左子树的后序遍历+右子树的遍历序列+根结点

 

中序遍历：中序遍历左子树，根结点，中序遍历右子树。由此得出的

中序遍历序列：左子树的中序遍历序列+根结点+右子树的中序遍历序列

 

利用后序遍历序列中最后出现结点肯定是根结点的性质并仿造上一种情况得出还原逻辑

 

下面给出一个具体的例子来说明：

后序遍历序列：E F A H C I G B D

中序遍历序列：E A F D H C B G I

这棵二叉树还原后为

层序+中序序列

利用层序遍历序列的特点，即根结点后面紧跟左子树和右子树的根可以推出还原逻辑

 

下面给出一个具体的例子来说明：

层序遍历序列：A B C D E

中序遍历序列：A C B E D

这颗二叉树还原后为

这个例子中层序遍历的根结点后所跟的并不是左子树的根，因为我们可以从中序遍历中得出这棵树的左子树为空树，它只有右子树

线索二叉树

下面以中序遍历为例。

对二叉树进行中序遍历后，本来这些元素之间呈现的是非线性的关系。但是从得到的遍历序列来看，它们呈现的是一种线性关系。每一个元素有一个与之对应的前驱，也有一个与之对应的后继（如下图中B的前驱是G，B的后继是E），当然和线性表一样第一个元素没有前继，最后一个元素没有后继

注意我们刚开始讲树的时候说一个结点有一个唯一前驱,并且可能有多个后继。这是从树本身的逻辑结构出发所定义的前驱和后继，但是刚才我们所说的一个元素的前驱和后继是基于它的遍历序列所定义的前驱和后继，二者不要混淆

每当我们要对一棵二叉树进行中序遍历的时候，都要从根结点出发，只有我们知道根结点是哪一个，才有可能对整个二叉树进行中序遍历。

但是有可能在某些场景当中我们只知道某一节点的指针而不知道根结点是哪一个，现在要求从这个节点出发继续完成剩下的中序遍历（比如上图中若知道G节点的指针，要继续完成对BEAFC节点的遍历）。

显然这种操作是普通二叉树所完成不了的，因为上图中G结点只有指向它孩子的指针，并不能从G结点出发往回找找到它的双亲，或者说它的后继节点B。而如果是线性表，给定线性表中任意一个元素的指针都可以由这个元素开始继续完成后续元素的遍历而并不需要像二叉树一样每一次都从头开始遍历

此外还有一个问题。对于普通二叉树，若给定一个节点的指针，不能找到该指定节点在遍历序列中的前驱。因为每一个节点只拥有向下一层的指针，不可能向上找。只能进行一次完整的中序遍历，下面讲的就是这种最土也最基本的方法

要找到一个节点在中序遍历的前驱，可以对整个二叉树再进行一次中序遍历，用指针q记录当前访问的结点，指针pre记录上一个被访问的结点。

观察下面中序遍历的代码。在中序遍历的代码当中，当我们在访问一个节点的时候会对该节点进行$visit(T)$操作，当前正在$visit$的节点其实就是q。在上图中D节点是是第一个被$visit$的节点，所以刚开始会让q指向D，pre指向NULL（因为D节点没有前驱，所以它的前驱指针现在指向NULL），现在对比发现q和p不相等，所以继续往后$visit$，在下一个节点被$visit$前让pre指针指向q当前指向的节点，再让q指针指向下一个被$visit$的节点，现在pre指针指向的节点就是q指针指向的节点的中序的前驱，重复以上操作直到q==p，此时pre即为p结点的前驱

//中序遍历
void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);              //递归遍历左子树
        visit(T);                        //访问根结点
        InOrder(T->lchild);              //递归遍历右子树
    }
}
1
2
3
4
5
6
7
8

现在如果要找到节点p的中序后继，原理也是类似的。我们只需要让q再往后移一次，也就是判断是否找到的条件变成判断pre和p是否指向同一个节点，当pre==p时，q所指向的节点就是p节点的后继

 

具体的代码实现如下

//中序遍历
void findPre(BiTree T){
    if(T!=NULL){
        findPre(T->lchild);       //递归遍历左子树
        visit(T);                 //访问根结点
        findPre(T->rchild);       //递归遍历右子树
    }
}

//访问结点p
void visit(BiTNode *q){
    if(q==p){                     //当前访问结点刚好是结点p
        final=pre;                //找到p的前驱
    }else{
        pre=q;                    //pre指向当前访问的结点
    }
}

//辅助全局变量，用于查找结点p的前驱
BiTNode *p;                       //p指向目标结点
BiTNode *pre=NULL;                //指向当前访问结点的前驱
BiTNode *final=NULL;              //用于记录最终结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

 

从上面的论述中可以看出普通二叉树还存在很多问题。找前驱，后继很不方便而且遍历操作必须从根开始。因此如果在某些场景中找前驱和找后继，遍历操作十分频繁的话，最好用线索二叉树。

下面给出了一棵中序遍历序列已知的二叉树（已经给各个节点标上了表示访问顺序先后的序号），改造该二叉树为线索二叉树，让它能更方便的查找前驱，查找后继或者进行遍历操作。

线索二叉树利用二叉树本身存在的$n+1$个空链域记录前驱和后继的信息。

例如像G这个节点是第二个被访问到的，可以让它的左孩子指针指向它的前驱D，右孩子指针指向它的后继B。这样我们就能很方便的从一个节点出发找到它的前驱和后继。对E，F节点的处理也和G类似。

至于像D这个节点，作为第一个被访问的节点，它没有前驱，可以让它的左孩子指针指向NULL，表示没有前驱。类似的C这个节点是最后被访问到的，可以让它的右孩子指针指向NULL，表示没有后继。

这样就按照中序遍历序列体现的节点前后继关系对这棵二叉树进行线索化，使它变成了一棵中序线索二叉树。如果一个节点的左孩子或者右孩子指针指向前驱和后继，而不是它的左右孩子，我们就把这种类型的指针称为线索。

经过线索化后遍历和找前后继显然方便了许多。

这里有一个遗留问题。G的右孩子指针本来就指向它的后继，所以找后继自然方便。但是如果对于一个节点，如节点B，它的右孩子指针就是指向它的右孩子而不是它的后继，这样的节点又如何找它的后继呢？这个问题先放一放，以后再讨论。

线索二叉树的存储结构

普通二叉树的存储结构如下

//二叉树的结点(链式存储)
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree
1
2
3
4
5

在线索二叉树中，一个节点的左孩子指针和右孩子的指针不一定指向它的左孩子和右孩子而是有可能指向它的前驱和后继。为了区分这种状态，增加了两个标志位$ltag$和$rtag$。$tag==0$表示指针指向孩子，$tag==1$表示指针是“线索”。左孩子指针充当指向前驱的线索，右孩子指针充当指向后继的线索。

二叉树可以被称为二叉链表，线索化后又可以被称为线索链表

//线索二叉树结点
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;              //左右线索标志
}ThreadNode,*ThreadTree;
1
2
3
4
5
6

依据不同的遍历方式，又可以把线索二叉树分为先序，中序，后序线索二叉树

中序线索二叉树

线索指向中序前继，中序后继

从逻辑视角看

从存储视角看

先序线索二叉树

线索指向先序前继，先序后继

从逻辑视角看

从存储视角看

后序线索二叉树

线索指向后序前继，后序后继

从逻辑视角看

从存储视角看

二叉树的线索化

当给定一个结点指针p的时候，怎么找到这个结点在中序遍历序列中的前驱？

回顾上一节讲过的土办法，可以对二叉树重新进行中序遍历，当我们在访问到一个结点的时候同时用另一个指针pre指向当前访问结点的前驱结点。

当我们要对某一个二叉树结点进行线索化的时候，实际上就是要把这个结点的左孩子指针连上它的前驱或者它的右孩子指针连上它的后继，因此上述算法的思想可以迁移到二叉树的线索化中

中序线索化

中序线索化实际上就是一个中序遍历的过程（下面代码中$InThread$函数内部实际上就是一个中序遍历），只不过在中序遍历访问各个结点的过程中需要一边遍历一边处理这个结点。

假设现在已经有一个初步建成的并未线索化的二叉树，$ltag$和$rtag$都事先在初始化时被置为0。表示暂时这些结点的左右孩子指针都指向它的左右孩子

定义全局变量pre用来指向当前访问结点的前驱。按照中序遍历的规则，下图二叉树中第一个被访问的结点是D，而这个结点没有前驱，所以一开始让pre指向NULL。

接下来从这个图里看，当前访问的结点D是没有左孩子的，所以要把它的左孩子指针线索化，这个过程可以在$visit$函数里完成。判断如果当前结点的左孩子为空，就把它的左孩子指针指向它的前驱pre并修改$ltag$值（如下图中D的左孩子指针变为指向pre，pre==NULL）。然后让pre指向当前结点

下一个被访问的结点是G，按照同样的逻辑由于G的左孩子是空的，对其进行线索化，让它的左孩子指针指向它的前驱pre并修改$ltag$值，并让pre指针指向当前结点G。然后访问下一个结点B

B结点的左右孩子指针都是非空的。但是它的前驱，也就是pre指针所指向的结点G此时右孩子是空的，因此要把G的右孩子指针线索化，指向G的后继也就是当前访问的q，同时修改G的$rtag$值。

后续的过程类似，就不再赘述

现在注意当我们访问到最后一个结点时，在$visit$该结点的时候最终会把pre指向当前这个结点，在这个结点之后就不会再有任何结点被$visit$。但是这里存在一个问题，如果最后一个结点的右孩子指针本来是空的，就应该要被线索化（下图中C作为最后一个被访问的结点，右孩子指针为空）。由于pre是个全局变量，因此我们可以在其他函数中（如下面的代码中的$CreateInThread$函数）对pre指针当前指向的结点进行一个处理，让它的右孩子指针指向NULL表示没有后继，同时修改$rtag$值为1。总之要对最后一个结点特殊处理

完整代码如下

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre=NULL;

//线索二叉树结点
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;        //左，右线索标志
}ThreadNode,*ThreadTree;

//中序遍历二叉树，一边遍历一边线索化
void InThread(ThreadTree T){
    if(T!=NULL){
        InThread(T->lchild);   //中序遍历左子树
        visit(T);              //访问根结点
        InThread(T->rchild);   //中序遍历右子树
    }
}

void visit(ThreadNode *q){
    if(q->lchild==NULL){       //左子树为空，建立前驱线索
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
       pre->rchild=q;          //建立前驱结点的后继线索
       pre->rtag=1;
    }
    pre=q;
}

//中序线索化二叉树T
void CreateInThread(ThreadTree T){
    pre=NULL;                  //pre初始为NULL
    if(T!=NULL){               //非空二叉树才能线索化
        InThread(T);           //中序线索化二叉树
        if(pre->rchild==NULL){
            pre->rtag=1;       //处理遍历的最后一个结点
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

书上给的代码略有不同

//中序线索化
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->rchlld=p;         //建立前驱结点的后继线索
            pre->rtag=1;
        }
        pre=p;                     //标记当前结点成为刚刚访问过的结点
        
        InThread(p->rchild,pre);   //递归，线索化右子树
    }
}

//中序线索化二叉树T
void CreateInThread(ThreadTree T){
    ThreadTree pre=NULL;
    if(T!=NULL){                 //非空二叉树，线索化
        InThread(T,pre);         //线索化二叉树
        pre->rchild=NULL;        //特殊处理遍历的最后一个结点
        pre->rtag=1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

实际上也是类中序遍历，只不过这里把pre（和上面一样，都用于记录当前被$visit$的结点的前驱）变成了传入函数的局部变量，并设置为引用类型以确保在函数中修改pre的值能影响原始的pre值

这里处理遍历的最后一个结点时，为什么没有判断$rchild$是否为NULL？

如果最后一个结点还有一个右孩子的话，那么根据中序遍历左根右的规则，我们访问完这个根结点之后还要访问它的右孩子。也就是说只要有右孩子就一定不是最后一个结点，中序遍历的最后一个结点右孩子必为空。但是如果是后面的先序线索化和后序线索化，处理遍历的最后一个结点时就要判断$rchild$是否为NULL

接下来的先序线索化和后序线索化不再摘录书上的代码版本，自己见书

先序线索化

先序线索化的原理类似，只不过我们要先$visit$根结点再对左子树和右子树进行线索化。本质上仍是先序遍历，只不过是一边遍历一边对这些结点进行进行线索化的处理。

同样设置一个全局遍历pre，让它指向当前访问节点的前驱节点。执行的过程基本类似，刚开始让pre指向NULL，第一个被$visit$的是A结点，由于A的左右孩子均不为空，所以不做处理，只让pre指向当前的结点就行了，再让访问下一个结点，以此类推。具体的过程就不再分析，和中序遍历基本一样，只不过我们访问各个结点的次序和顺序发生了改变。

但是如果只是简单修改中序遍历的代码像下面一样直接用，会出现小问题

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre=NULL;

//先序线索化二叉树T
void CreatePreThread(ThreadTree T){
    pre=NULL;                  //pre初始为NULL
    if(T!=NULL){               //非空二叉树才能线索化
        PreThread(T);           //先序线索化二叉树
        if(pre->rchild==NULL){
            pre->rtag=1;       //处理遍历的最后一个结点
        }
    }
}

//先序遍历二叉树，一边遍历一边线索化
void PreThread(ThreadTree T){
    if(T!=NULL){
        visit(T);              //先处理根结点
        PreThread(T->lchild);   
        PreThread(T->rchild);   
    }
}

void visit(ThreadNode *q){
    if(q->lchild==NULL){       //左子树为空，建立前驱线索
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
       pre->rchild=q;          //建立前驱结点的后继线索
       pre->rtag=1;
    }
    pre=q;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

假设当前正在$visit$第三个结点，pre指向第二个结点。

按照$visit$函数里的处理逻辑，我们应该让第三个结点的左孩子指针线索化指向pre，同时让pre指向当前访问的结点。回到$PreThread$函数，当我们在处理完第三个结点之后，接下来我们会处理这个结点的左子树，但是刚才我们已经把该结点的左孩子指针指向了该结点的前驱B结点。这时如果要访问它的左子树的话，会导致q再次指回B，对结点的访问会出现无限的循环，原地打转

要解决这个现象，就要在上面的代码基础上对$PreThread$函数稍作修改。因为在把左孩子指针线索化的同时修改了$ltag$变量，所以可以多一步判断，利用$ltag$变量判断左孩子指针是不是真的指向该结点的左孩子

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre=NULL;

//先序线索化二叉树T
void CreatePreThread(ThreadTree T){
    pre=NULL;                  //pre初始为NULL
    if(T!=NULL){               //非空二叉树才能线索化
        PreThread(T);           //先序线索化二叉树
        if(pre->rchild==NULL){
            pre->rtag=1;       //处理遍历的最后一个结点
        }
    }
}

//先序遍历二叉树，一边遍历一边线索化
void PreThread(ThreadTree T){
    if(T!=NULL){
        visit(T);              //先处理根结点
        if(T->ltag==0){        //lchild不是前驱线索
            PreThread(T->lchild);   
        }
        PreThread(T->rchild);   
    }
}

void visit(ThreadNode *q){
    if(q->lchild==NULL){       //左子树为空，建立前驱线索
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
       pre->rchild=q;          //建立前驱结点的后继线索
       pre->rtag=1;
    }
    pre=q;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

后序线索化

原理类似，唯一的区别在于先处理左右子树后处理根节点，因为后序遍历的顺序就是左右根。仿造中序线索化即可，这里不再赘述

后序线索化不会出现像先序线索化那样的转圈问题，原因在于当我们在访问一个结点的时候，这个结点的左子树和右子树都已被遍历处理过，所以我们在访问完该结点后不可能再回头去访问它的左子树。同理中序线索化也不会出现转圈问题，因为在访问一个结点之前左子树也已被遍历处理过

//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre=NULL;

//后序线索化二叉树T
void CreatePostThread(ThreadTree T){
    pre=NULL;                  //pre初始为NULL
    if(T!=NULL){               //非空二叉树才能线索化
        PostThread(T);         //后序线索化二叉树
        if(pre->rchild==NULL){
            pre->rtag=1;       //处理遍历的最后一个结点
        }
    }
}

//后序遍历二叉树，一边遍历一边线索化
void InThread(ThreadTree T){
    if(T!=NULL){
        PostThread(T->lchild);   //后序遍历左子树
        PostThread(T->rchild);   //后序遍历右子树
        visit(T);                //访问根结点
    }
}

void visit(ThreadNode *q){
    if(q->lchild==NULL){       //左子树为空，建立前驱线索
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&&pre->rchild==NULL){
       pre->rchild=q;          //建立前驱结点的后继线索
       pre->rtag=1;
    }
    pre=q;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

在线索二叉树中找前驱和后继

中序线索二叉树找中序后继

在中序线索二叉树中找到指定节点*p的中序后继next

1.若$p->rtag==1$，则$next=p->rchild$

2.若$p->rtag==0$，则

$next=p$的右子树中最左下结点

//找到以p为根的子树中，第一个被中序遍历的结点
ThreadNode* Firstnode(ThreadNode *p){
    //循环找到最左下结点（不一定是叶结点）
    while(p->ltag==0){
        p=p->lchild;
    }
    return p;
}

//在中序线索二叉树中找到结点p的后继结点
ThreadNode* Nextnode(ThreadNode *p){
    //右子树中最左下结点
    if(p->rtag==0){
        return Firstnode(p->rchild);
    }else{
        return p->rchild;  //rtag==1直接返回后继线索
    }
}

//中序线索二叉树进行中序遍历。这是利用线索实现的非递归算法，空间复杂度仅为O(1)
void Inorder(ThreadNode *T){
    for(ThreadNode *P=Firstnode(T);p!=NULL;p=Nextnode(p)){
        visit(p);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

中序线索二叉树找中序前驱

在中序线索二叉树中找到指定结点*p的中序前驱pre

1.若$p->ltag==1$，则$pre=p->lchild$

2.若$p->ltag==0$

$next=p$的左子树中最右下结点

//找到以p为根的子树中，最后一个被中序遍历的结点
ThreadNode *Lastnode(ThreadNode *p){
    //循环找到最右下结点(不一定是叶结点)
    while(p->rtag==0) p=p->rchild;
    return p;
}

//在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){
    //左子树中最右下结点
    if(p->ltag==0) return Lastnode(p->lchild);
    else return p->lchild; //ltag==1直接返回前驱线索
}

//对中序线索二叉树进行逆向中序遍历
void RevInorder(ThreadNode *T){
    for(ThreadNode *p=Lastnode(T);p!=NULL;p=Prenode(p)){
        visit(p);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

先序线索二叉树找先序后继

先序线索二叉树找先序前驱

在先序线索二叉树中找到指定结点*p的先序前驱pre

1.若$p->ltag==1$，则$next=p->lchild$

2.若$p->ltag==0$，则

因为不可能从p的左右子树里面找到它的前驱，而且我们的线索二叉树只有指向孩子结点的指针，不可能往回找。所以在这种情况下我们是找不到p的先序前驱的

除非用之前讲的从头开始遍历的土办法再重新进行一次完整的先序遍历。或者把二叉链表改为三叉链表，给各个结点设置一个指向它父结点的指针

怎么找左兄弟子树中最后一个被先序遍历的结点？

后序线索二叉树找后序前驱

后序线索二叉树找后序后继

类似先序线索二叉树找先序前驱，不可能从左右子树中找到后序后继。所以只能采用土办法或者用三叉链表

当改用三叉链表时

怎么找右兄弟子树中第一个被后序遍历的结点？

总结

先序线索二叉树找前驱和后序线索二叉树找后继都只能用三叉链表或者用之前讲过的土办法从根开始遍历寻找。所以在先序线索二叉树中，给你一个指定结点就可以从这个指定结点开始进行先序遍历。而对于后序线索二叉树，给你一个指定结点你只能从这个指定结点开始进行逆向后序遍历

树的存储结构 森林，树，二叉树的相互转化

双亲表示法（顺序存储）

双亲表示法：每个结点中保存指向双亲的“指针”

#defint MAX_TREE_SIZE 100 //树中最多结点数
typedef struct{           //树的结点定义
    ElemType data;        //数据元素
    int parent;           //双亲位置域
}PTNode;

typedef struct{           //树的类型定义
    PTNode nodes[MAX_TREE_SIZE];   //双亲表示
    int n;                         //结点数
}PTree
1
2
3
4
5
6
7
8
9
10

根结点固定存储在数组下标为0的位置，双亲位置域置为-1表示没有双亲

因为保存了双亲的信息，新增数据元素无需按逻辑上的次序存储

增加数据元素

直接在空白位置写入这个新结点的值，并且记录它和双亲的关系即可

新增数据元素，无需按逻辑上的次序存储

删除数据元素

删除叶子结点

有两种方法

1.直接将该元素的双亲位置域置为-1

2.把尾部的数据移上来填充这个空白（更好）

记得把结点数n进行修改

删除非叶子结点

删除非叶子结点意味着删除了以其为根的整个子树，因此要找到这个结点的子孙结点并删除。这就涉及了从一个结点找到他的孩子结点的查询操作

采用双亲表示法找到指定结点的双亲很方便，但是找到指定结点的孩子只能从头遍历，所以查找孩子很不方便。这也暴露了删除的第一种方案存在的问题，如果没有用最后一个元素来填充这个空白的位置。在进行遍历操作的时候就要多判断一个无效的结点，这会导致遍历的速度更慢。

孩子表示法（顺序+链式存储）

各个结点实际的数据用结构$CTBOX$存储，而链表中的结点保存了各个孩子结点的下标。

struct CTNode{
    int child;             //孩子结点在数组中的位置
    struct CTNode *next;   //下一个孩子
}

typedef struct{
    ElemType data;
    struct CTNode *firstchild; //第一个孩子
}CTBox;

typedef struct{
    CTBox nodes[MAX_TREE_SIZE];
    int n,r;     //结点数和根的位置
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这种方式找孩子很方便，找双亲不方便

孩子兄弟表示法（链式存储）

• 最重要的一种方法，用纯链式存储的方式来存储一棵树

从下图可以看到每个结点中包含了一个数据域和两个指针，从存储的角度看其实就是个二叉链表（每个结点有两个链接指针）。和二叉树的结点本质是一样的，只不过变量的命名和含义有一点区别。下面会具体讲解如何把一棵普通的树转化为二叉树并用二叉链表保存

//二叉树的结点(链式存储)
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//树的存储——孩子兄弟表示法
typedef struct CSNode{
    ElemType data;                      //数据域
    struct CSNode *firstchild,*nextsibling; //第一个孩子和右兄弟指针
}CSNode,*CSTree;
1
2
3
4
5
6
7
8
9
10
11

以下图的树为例

可以把$firstchild$指针看作左指针，指向结点的第一个孩子，$nextsibling$指针看作右指针，指向结点的右兄弟。A是根节点，左指针指向它的第一个孩子结点B。B的右指针连向它的右兄弟C。同时让C的右指针连向它的右兄弟D。B的左指针指向它的第一个孩子E。E的右指针连向它的右兄弟F，左指针连向它的第一个孩子K。再看C，C的左指针连向它的第一个孩子G，右指针连向它的右兄弟D。D的左指针连向它的第一个孩子H。剩下的I，J都是H的兄弟，用右指针把它们连起来。这样就得到了用孩子兄弟表示法，或者说用二叉链表保存的一棵树

用孩子兄弟表示法存储的树在物理上呈现出“二叉树”的样子

上面实现了树和二叉树之间的相互转化，就可以用我们熟悉的二叉树操作来处理树了。

森林和二叉树的转换

这个问题背后的本质也是用二叉链表来存储森林。一棵森林内有几棵互不相交的树，上面已经讲了如何把树转化为二叉树并用二叉链表存储。由于这些树在逻辑上看是平级的，因此可以把这些树的根结点看成兄弟结点。如果用二叉链表存储，右指针表示兄弟关系，因此可以把这些根结点用右指针连起来实现森林和二叉树的转换。

把森林中的树的根结点连起来作为兄弟结点

树和森林的遍历

树的先根遍历

下面是用伪代码描述的算法实现的过程，具体实现的时候还要看是用什么存储结构来实现这颗树的

和二叉树的先序遍历类似。若树非空，先访问根结点，再依次对每颗子树进行先根遍历

//树的先根遍历
void PreOrder(TreeNode *R){
    if(R!=NULL){
        visit(R); //访问根节点
        while(R还有下一棵子树T){
            PreOrder(T); //先根遍历下一棵子树
        }
    }
}
1
2
3
4
5
6
7
8
9

以下图的树为例

采用逐层展开法就能得到这棵树的先根遍历序列

值得注意的是如果把这棵树转化为二叉树，也就是用孩子兄弟法来存储这棵树，就会发现树的先根遍历序列与这棵树相应二叉树的先序序列相同

树的后根遍历

若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。

//树的后根遍历
void PostOrder(TreeNode *R){
    if(R!=NULL){
        while(R还有下一个子树T){
            PostOrder(T); //后根遍历下一棵子树
        }
        visit(R); //访问根节点
    }
}
1
2
3
4
5
6
7
8
9

以下面这棵树为例

利用逐层展开法得到这棵树的后根遍历序列

树的后根遍历序列与这棵树相应二叉树的中序序列相同

树的层次遍历

和二叉树的层序遍历没有什么区别，都用队列实现。实现思想如下

1.若树非空，则根节点入队

2.若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队

3.重复2直到队列为空

 

以下面这棵树为例

按照上述思想就能得到该树的层次遍历序列

A B C D E F G H I J K

 

不难发现我们在探索这些结点的时候都是尽可能横向地去探索。所以对树的层次遍历也可以被称为对树的广度优先遍历。与之相对的，之前介绍的后根遍历和先根遍历在探索各个结点的时候是尽可能的往深处探索直到尽头才会返回，所以后根遍历和先根遍历也可以被称为树的深度优先遍历

森林的先序遍历

森林是$m(m\ge 0)$棵互不相交的树的集合。每棵树去掉根节点后，其各个子树又组成森林。森林这种数据结构其实是和树相互递归定义的，因此我们也可以用递归的思想来遍历森林

法一

若森林为非空，则按如下规则进行遍历：

1.访问森林中第一颗树的根结点

2.先序遍历第一棵树中根结点的子树森林

3.先序遍历除去第一棵树之后剩余的树组成的森林

 

以下面这个森林为例

按照上述思想得到的最终访问次序如下

从结果来看其实效果等同于依次对各个树进行先根遍历，所以问先序遍历森林得到的序列是什么不用钻到上面那个有两层递归嵌套的递归算法里面，直接对各个树进行先根遍历最后排出完整的序列即可

法二

先转化森林为对应的二叉树，再对二叉树进行先序遍历

森林的中序遍历

法一

若森林为非空，则按如下规则进行遍历：

1.中序遍历第一棵树中根结点的子树森林

2.访问第一棵树的根结点

3.中序遍历除去第一棵树之后剩余的树组成的森林

效果等同于依次对各个树进行后根遍历

 

以下面这个森林为例

按照上述思想得到的最终访问次序如下

法二

先转化森林为对应的二叉树，再对二叉树进行中序遍历

代码实现时可以用孩子兄弟法来存储森林，将对森林的遍历操作转换成对二叉树的遍历操作

哈夫曼树

这一节可以参见离散数学里构建最优二叉树和前缀码的内容，这里会记得简略些

概念

结点的权：有某种现实含义的数值（如：表示结点的重要性等）

结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积

树的带权路径长度：树中所有叶结点的带权路径长度之和（WPL）
$$WPL=\sum _{i=1}^n{w}_i{l}_i$$
在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树

下图中间两棵树就是哈夫曼树

哈夫曼树的构造

给定n个权值分别为$w_1,w_2,...,w_n$的结点，构造哈夫曼树的算法描述如下：

1.将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F

2.构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左，右子树，并且将新结点的权值置为左，右子树上根结点的权值之和

3.从F中删除刚才选出的两棵树，同时将新得到的树加入F中

4.重复步骤2和3，直至F中只剩下一棵树为止

 

哈夫曼树具有如下性质：

1.每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度最大

2.哈夫曼树的结点总数为$2n-1$

原有n个结点，结合n-1次，每次结合产生一个新的结点

3.哈夫曼树中不存在度为1的结点

4.哈夫曼树并不唯一，但WPL必然相同且为最优

哈夫曼编码

固定长度编码——每个字符用相等长度的二进制位表示

可变长度编码——允许对不同字符用不等长的二进制位表示

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码

有哈夫曼树得到哈夫曼编码——字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树。哈夫曼树不唯一，因此哈夫曼编码不唯一。哈夫曼编码可用于数据压缩

并查集

 

同一子集中的各个元素，组织成一棵树，用互不相交的树，表示多个“集合”

如何“查”到一个元素到底属于哪一个集合？ —— 从指定元素出发，一路向北，找到根节点

如何判断两个元素是否属于同一个集合？ —— 分别查到两个元素的根，判断根节点是否相同即可

如何把两个集合“并”为一个集合？ —— 把其中一棵树的根节点指向另一棵树的根节点，成为另一棵树的子树即可

 

 

并查集（Disjoint Set）是逻辑结构 —— 集合的一种具体实现，只进行 “并” 和 “查” 两种操作

并查集的存储结构

使用双亲表示法来表示并查集，“并”和“查”两操作实现更方便

并查集的基本操作

集合的两个基本操作 —— “并” 和 “查”

 

$Find$ —— “查” 操作：确定一个指定元素所属集合

$Union$ —— “并” 操作：将两个不相交的集合合并为一个

并查集的代码实现

#define SIZE 13
int UFSets[SIZE];     //集合元素数组

//初始化并查集
void Initial(int S[]){
    for(int i=0;i<SIZE;i++)
        S[i] = -1;
}

//Find “查”操作，找x所属集合（返回x所属根结点）
int Find(int S[],int x){
    while(S[x]>=0)      //循环寻找x的根
        x=S[x];
    return x;           //根的S[]小于0
}

//Union “并”操作，将两个集合合并为一个
void Union(int S[],int Root1, int Root2){
    //要求Root1与Root2是不同的集合
    if(Root1==Root2)    return;
    //将根Root2连接到另一根Root1下面
    S[Root2]=Root1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

如果指定的两个元素不是根节点，要合并这两个元素从属的集合，需要先“查”确定两个元素各自的根节点，然后再对两个根节点进行“并”

时间复杂度分析

$Union$时间复杂度：$O(1)$

$Find$最坏时间复杂度：$O(n)$

Union操作的优化

优化思路：在每次$Union$操作构建树的时候，尽可能让树不长高

1.用根节点的绝对值表示树的结点总数

2.$Union$操作，结点总数小的树是小树，让小树合并到大树

//Union “并”操作，小树合并到大树
void Union(int S[],int Root1,int Root2){
    if(Root1==Root2)    return;
    if(S[Root2]>S[Root1]) {   //Root2结点数更少
        S[Root1] += S[Root2];   //累加结点总数
        S[Root2]=Root1; //小树合并到大树
    } else {
        S[Root2] += S[Root1];   //累加结点总数
        S[Root1]=Root2; //小树合并到大树
    }
}
1
2
3
4
5
6
7
8
9
10
11

 

$Union$操作优化后，该方法构造的树高不超过$[lo{g}_{2}n]+1$,该结论可以用数学归纳法证明

$Union$操作时间复杂度仍为$O(1)$，$Find$操作最坏时间复杂度为$O(lo{g}_{2}n)$

并查集的进一步优化

Find操作的优化（压缩路径）

以下图为例，按照之前实现的$Find$操作，要找到L结点所属的集合会从L出发，沿着L —> E —> B —> A的路径找到根结点A，这条路径称为查找路径。所谓压缩路径，就是缩短查找路径，将查找路径上的各个结点全部挂到根节点A下面

 

//Find “查”操作优化，先找到根节点，再进行“压缩路径”
int Find(int S[],int x){
    int root = x;
    while(S[root]>=0)    root=S[root];  //循环找到根
    while(x!=root){ //压缩路径
        int t=S[x]; //t指向x的父结点
        S[x]=root;  //x直接挂到根节点下
        x=t;
    }
    return root;            //返回根节点编号
}
1
2
3
4
5
6
7
8
9
10
11

每次$Find$操作，先找根，再“压缩路径”，可使树的高度不超过$O(\alpha (n))$。$O(\alpha (n))$是一个增长速度比$lo{g}_{2}n$还要缓慢的函数，对于常见的几万以内的$n$值，通常$\alpha (n)\le 4$，因此优化后并查集的$Find、Union$操作时间开销都很低

并查集的优化

 

 

 

推荐网站 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html