考研408笔记之数据结构（四）——树与二叉树

数据结构（四）——树与二叉树

1. 树的基本概念

1.1 树的定义

树的定义：树是n（n>=0）个结点的有限集。当n=0时，称为空树。

在任意一棵非空树中应满足：

1. 有且仅有一个特定的称为根的结点。
2. 当n>1时，其余结点可分为m（m>0）个互不相交的有限集T₁，T₂，…，T_m，其中每个集合本身又是一棵树，并且称为根的子树。

这里第二点不太好理解，其实就是一棵树去掉根结点以后，剩下的几个分支，每个分支都可以构成一个新的树（有点森林的意思）。

显然，树的定义是递归的，即在树的定义中又用到了其自身，树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

1. 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
2. 树中所有结点都可以有零个或多个后继。

1.2 树的基本术语

树的基本术语很简单，建议参考上面的图自己回想，这些基础知识没啥理解难度，重点要记住。如果有不清楚的，可以跳转看视频的介绍：树的定义和基本术语

1.3 树的性质

第一条：

第二条：

第三条：

第四条：

第五条：

第六条：

2. 二叉树的概念

2.1 二叉树的定义及其主要特性

2.1.1 二叉树的定义

二叉树的基本概念：

二叉树是树的一种，所以二叉树也是一种递归结构。

由于二叉树是有序树，所以二叉树有以下5种基本形态：

2.2.2 几种特殊的二叉树

(1) 满二叉树与完全二叉树

满二叉树：除了最下面一层的叶子结点外，其余每一层的结点都长满了两个分支。即满二叉树就是每层都含有最多的结点的二叉树。

完全二叉树：当且仅当二叉树每个结点都与满二叉树的编号对应时，称为完全二叉树。对于完全二叉树来说，如果某结点只有一个孩子的话，那一定是左孩子。

(2) 二叉排序树

(3) 平衡二叉排序树

平衡二叉树与二叉排序树组合起来，构成平衡二叉排序树结构，这样的结构搜索效率会大大提高，可以利用此结构，来实现经常要进行搜索的算法。

2.2 二叉树与完全二叉树的性质

第一条：

第二条：

第三条：

完全二叉树的性质：

第一条：

这里给出了完全二叉树两种知道结点数求高度的公式推导过程：

第一种是依据h层完全二叉树的结点数大于h-1层满二叉树的结点数，小于等于h层满二叉树结点数来求解。

第二种是依据h层完全二叉树比h-1层满二叉数至少多1个结点，但小于等于h层满二叉树，但为了求解方便，所以可以认为比h层满二叉树的结点数+1小（即h+1层有一个结点）。

注意理解两种推导方法的区别。

第二条：

2.3 二叉树的存储结构

2.3.1 二叉树的顺序存储

二叉树的存储结构同我们前面所学的几种结构的存储方式一样，都分为顺序存储和链式存储。

首先看二叉树的顺序存储：

在二叉树的顺序存储中，将二叉树看成一连串地址连续的数组，根据二叉树的结点编号，将其一层一层存入数组中，如上图，为了后续操作方便，可以将数组首位空出，让二叉树的第一个结点从数组第2位开始存储，这样可以令二叉树的结点编号与数组下标相同。从这里，不难看出，二叉树的顺序存储，本质上还是建立数组，所以，二叉树的顺序存储结构和表很类似，进而可以将二叉树的存储程序描述如下：

//二叉树的顺序存储结构
#define MaxSzie 100
struct TreeNode{
    ElemType value;	//结点中的数据元素
    bool isEmpty;	//结点是否为空
};

//二叉树初始化，每个结点赋0
void InitTree(TreeNode &t){
    for(int i=0;i<MaxSize;i++)
        t[i].isEmpty=true;
}

int main(){
    TreeNode t[Maxsize];	//定义一个树结构数组
}

将二叉树的存储结构描述完以后，就应该考虑，如何实现二叉树的基本操作，首先我们可以考虑一下，有哪几种常用的操作。

第一种，假设，我们现在知道结点i，那该如何通过i去查找i的左孩子，右孩子，父节点以及i的所在层次呢？

第二种，假设，若完全二叉树中共有n个结点，则怎么判断第i个结点是否有左孩子，右孩子以及如何判断i是叶子还是分支节点？

那基于这些问题总结的结论就如下：

不难发现，我们上面所说的每一条结论，都是基于完全二叉树的，那对于普通的二叉树又是怎么样的呢？

如上图，是二叉树进行存储的样子，其中我们会发现，用数组存储普通二叉树时，会出现很多地址上没有存储数据，这是什么原因造成的呢？

原因很简单，当我们把二叉树按照顺序存储进数组时，如果为了节省地址空间，而将图中1,2,3,4,5,6,7,8,按照t[1]~t[8]存储，就无法反映二叉树中，各节点间的关系。为了保持结点间的关系，就要在二叉树的顺序存储中，把二叉树的结点编号与完全二叉树对应起来。如上面图中所示，这样才能体现二叉树的存储结构。

基于这种存储模式，前面提到的两种基础操作类型，第一种我们仍可以通过完全二叉树的手段进行左孩子、右孩子及父结点查找。但是判断是否有孩子和是否为叶子结点时，就不能沿用上面操作，需要通过我们一开描述存储结构时，所设计的IsEmpty判空指针进行判断。

当然，通过上面的图，我们还可以发现，若二叉树不是完全二叉树，会导致有大量空间浪费。若高度为h且只有h个结点单支树（所有结点只有右孩子），也至少需要2^h-1个存储单元。所以，我们可以得出结论，二叉树的顺序存储结构，只适合存储完全二叉树。

若想描述二叉树的结构（不仅有完全二叉树）又不想浪费地址，就需要通过链式存储的方式来实现。

2.3.2 二叉树的链式存储

二叉树的链式存储结构：

typedef struct BiTNode{
    ElemType data;						//数据域
    struct BiTNode *lchild,*rchild;		//左、右孩子指针
}BiTNode,*BiTree;

对二叉树进行链式存储，我们就可以对每个树结点加上左右孩子指针，类似于表的前驱和后继一样，我们可以使用结点的左孩子指针指向左孩子，右孩子指针指向右孩子，依次类推，将所有结点串到一起。使用这种方式，我们可以很容易查找一个结点的左右孩子结点。

注意，使用链式存储时，如果有n个结点，则一共就会有2n个指针域，但是其中只有n-1个指针域是有只向的，剩下的n+1个指针域全为NULL，而这些空的指针域可以用于构造线索二叉树（线索二叉树在下面，这里做个铺垫）。

说完二叉树的结点存储结构如何描述，接下来就该考虑如何构建一个二叉树，二叉树的构建过程如下图：

对于链式二叉树，我们只说了他对于查找左孩子与右孩子会很方便，那这里就产生了一个疑问，我们要是想找父结点该怎么办？很显然，想找父结点，只能通过遍历的方式查找，但是对于树这种地址不连续且复杂的结构，如何通过遍历去查找到我们想要的信息呢？这就是我们下面要说的树的遍历问题。

补充：除了遍历还有第二种方法，在描述二叉树链式存储结构时添加父结点指针：

struct BiTNode *father;		//父结点指针

2.4 二叉树的遍历

遍历：就是按照某种次序把所有结点都访问一遍。

由二叉树的递归定义可知，遍历一棵二叉树便要决定对根节点N、左子树L和右子树R的访问顺序，按照先遍历左子树再遍历右子树的原则，常见的遍历次序有先序（NLR）、中序（LNR）、后序（LRN）三种遍历算法。

2.4.1 先序

先序遍历步骤：

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

根据上面的动图，我们可以轻而易举的看出先序遍历的执行过程，所以，可以写出上面二叉树的先序遍历顺序为：A B D H I E J C F K G。

先序代码实现如下：

这里主要是递归算法的进行结点遍历，说白了根据思想，摆正访问根结点位置就行，有不明白，可以看下视频里讲解的算法递归过程，我感觉这个东西写多了程序就很容易理解，所以我给个视频链接，就不写递归过程了。先序中序后序遍历（11~16分钟讲执行过程）

2.4.2 中序

中序遍历步骤：

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

根据上面的动图，我们可以轻而易举的看出中序遍历的执行过程，所以，可以写出上面二叉树的中序遍历顺序为：H D I B E J A F K C G。

中序代码实现如下：

2.4.3 后序

先序遍历步骤：

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

根据上面的动图，我们可以轻而易举的看出后序遍历的执行过程，所以，可以写出上面二叉树的后序遍历顺序为：H I D J E B K F G C A。

后序代码实现如下：

2.4.4 二叉树的层序遍历

二叉树的层序遍历就是按照从上到下，从左到右的顺序进行遍历，有了这个思想，就可以查看下面的算法思想：

根据上面的算法思想，自己模拟一下运行过程，进而我们可以设计如下的算法：

在这个算法中有一点要注意，我们保存的是结点的指针而非结点本身，因为结点指针所占用的空间要比结点本身少很多，所以我们可以通过保存结点指针缩短占用空间。

2.4.5 补充知识

对一个算术表达式进行先中后序遍历，可以分别得到这个表达式的前缀、中缀、后缀。但是中缀表达式没有界限符，所以需要我们自己添加界限符。

遍历应用——求树的深度：

2.5 由遍历序列构造二叉树

二叉树的遍历有前序遍历、中序遍历、后序遍历和层序遍历，若只知道其中一种的遍历序列，不能唯一确定一棵二叉树。所以要想由遍历序列确定二叉树，至少要知道其中两种的遍历序列。

要注意的是，这两种遍历序列的组合，其中的一种必须是中序遍历序列，不能是另外三种遍历序列两两组合。

这里给个例子：

接下来看由中序遍历序列与其他的遍历序列组合如何确定二叉树。

2.5.1 前序+中序遍历序列

根据前序遍历的方式可以知道前序遍历序列第一个一定是整棵二叉树的根结点，然后根据上图的对应方式，可以找到中序遍历序列里的根节点，在中序遍历序列里，根节点左边是左子树，右边是右子树。然后在前序遍历序列里，找到左子树与右子树，这时候前序遍历序列里的左子树和中序遍历序列里的左子树可以看成一个树的前序遍历和中序遍历，原树的左子树的结点就可以看成当前树的根结点，照着这样的方式往下套娃，最后可以确定一个只有一层左右结点的根结点，这样就可以确定根节点的左子树结构。右子树结构使用同样方式确定。

下面给道例题：

2.5.2 后序+中序遍历序列

原理同前序+中序遍历序列。下面给例题：

2.5.3 层序+中序遍历序列

层序与中序遍历序列确定二叉树与前面不同，前面的通过中序序列可以确定左右子树，而左右子树在前序遍历和后序遍历里是连续的。但是在层序遍历里，它的遍历是一层一层的，所以只能通过中序遍历序列和层序遍历序列来确定每一层根结点的左子树的根和右子树的根，进而到最后一层可以确定一整棵二叉树。

下面给出一道例题，加深理解：

2.5.4 由遍历序列确定二叉树总结

写在最后，贴个连接，这部分光靠文字和图片描述可能不易理解，可以去视频里看看动态的例题解题过程，进而加深理解：由遍历序列构造二叉树

3. 线索二叉树

3.1 线索二叉树的概念

二叉树可以通过前序遍历、中序遍历和后序遍历。上面的二叉树经过中序遍历，可以得到中序遍历序列为DGBEAFC。在二叉树中，数据元素之间呈现的是非线性的关系，而在遍历序列里，数据元素之间呈现的是线性关系，每个元素有一个与之对应的前驱和后继，而且同线性表一样，第一个元素没有前驱，最后一个没有后继。而从树本身来说，一个结点会有一个前驱，但可能有多个后继。所以，这里要区分一下说结点前驱与后继的角度是从树本身来说，还是从遍历序列来说。

对于普通的二叉树，我们知道结点的左右孩子，是无法从中间的某个结点进行遍历的。如上图我们无法从G点开始进行之后的中序遍历，得到GBEAFC。

除此以外，如果给了指定结点的指针，能否找到该结点的遍历前驱和后继呢？答案是可以的，但是需要从根节点出发，重新遍历一遍才可以。这样做起来很麻烦。

如果在某些场合需要频繁找遍历前驱后继的话，普通的二叉树就显得太麻烦，所以就有人提出了线索二叉树的概念。

所谓线索二叉树，就是让二叉树里的空链域记录前驱和后继的信息。说白了，就是一个结点的左孩子如果为NULL，则让它的左孩子指向前驱；如果右孩子为NULL，则让右孩子指向后继。如上图就是中序线索二叉树。

有了线索二叉树，我们就很容易找到遍历序列里一个结点的前驱和后继，也可以从某个结点开始往后进行遍历。

由此，我们可以进一步推广线索二叉树的存储结构。

如图，是线索二叉树的存储结构，相比较于普通二叉树，我们在里面添加了ltag和rtag，来分别表示左孩子指针和右孩子指针指向孩子还是前驱和后继。如果ltag=1，则左孩子指向前驱结点；如果ltag=0，则左孩子指针指向左孩子结点，rtag同理。

之前说，二叉树是二叉链表，现在改成线索二叉树也可以称之为线索链表。

下面看一下线索二叉树的存储结构，以前序为例（前面的中序线索二叉树展示的是逻辑结构，下面是具体的存储结构）：

既然有中序线索二叉树的存储结构，就肯定也有先序和后序的，可以自己去画一下，这里就不多说。下面看三种线索二叉树的对比：

从图中可以看到，中序线索二叉树存在结点前驱指针为NULL和后继指针为NULL的结点，但是先序线索二叉树只存在后继指针为NULL的结点，而后序线索二叉树只存在前驱为NULL的结点。

下面是对线索二叉树基本概念总结：

3.2 二叉树的线索化

3.2.1 中序二叉树线索化

中序二叉树的线索化思想就是先中序遍历二叉树，一边遍历，一边线索化。在遍历之前，要先建立一个全局变量树节点pre用来指向当前访问结点的前驱。

在遍历的时候，线索化执行在访问当前结点函数里，如果当前访问结点的左孩子为NULL，说明左孩子指针应当指向前驱，即指向pre结点。若当前结点右孩子为NULL，由于没有指向下一个后继的指针，所以应当让pre以及当前访问结点指针向下遍历，指向下一个结点（pre指向当前访问节点，当前访问结点指针指向后继结点），此时让pre指向当前访问结点指针。这里算法思想需要注意一下。

当指到最后一个结点时，由于其后没有结点，所以我们要对其单独做处理，这里由于定义了全局变量pre，而pre最后会指向遍历的最后一个结点，所以对最后一个结点做操作很方便，但记住一定要处理。

3.2.2 先序二叉树线索化

先序二叉树线索化与中序二叉树线索化一样，只是将中序遍历改为先序遍历。

其余线索化以及对最后一个结点的操作没有改变。

但是这里有个易错点，在先序遍历时，要加上左孩子指针指向的不是前驱的判断，如上图，这样做是为了避免出现在原地转圈的情况。

举个例子，如下图结构，采用先序遍历，定义全局变量pre指向当前结点前驱，p指向当前访问结点。假设p指向D，pre指向B，根据线索化程序可以看到会先让p的左孩子指向pre，再让pre等与q，此时如果对于先序遍历的访问左孩子递归不做判断，由于在上一步访问结点线索化时让p左孩子指向pre，此时再次访问左孩子，p会往回指向B，而pre又跟回去指向B，p接着又一次指向D，这时就会发现，我们的先序遍历在次绕圈，所以需要在遍历时对左孩子指针进行判断。这个地方容易出错，也是先序遍历算法与其他两种算法不一样的地方。

3.2.3 后序二叉树线索化

后序二叉树线索化同中序一样，只是遍历使用的是后序遍历。

3.2.4 二叉树线索化总结

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

3.3.1 中序线索二叉树找后继

对于中序线索二叉树查找后继next，如果该结点的rtag1，则next直接等于右孩子指针。如果该结点的rtag0，则一定可以确定该结点有右孩子结点，由于采用中序遍历，所有可以按照上图右下角的规律，找到该结点的后继就是右子树的最下面一层的最左结点。算法程序设计如上图左。

3.3.2 中序线索二叉树找前驱

同理，对于中序线索二叉树查找前驱pre，如果该结点的ltag1，则pre直接等于左孩子指针。如果该结点的ltag0，则一定可以确定该结点有左孩子结点，由于采用中序遍历，所有可以按照上图右下角的规律，找到该结点的前驱就是左子树的最下面一层的最右结点。算法程序设计如上图左。

3.3.3 先序线索二叉树找后继

对于先序线索二叉树查找后继next，如果该结点的rtag1，则next直接等于右孩子指针。如果该结点的rtag0，则一定可以确定该结点有右孩子结点，由于采用先序遍历，所有可以按照上图右下角的规律，找到该结点的后继结点。这里发现，采用先序遍历的话，后继结点与该结点有没有左孩子有关，若有左孩子，则后继结点为左孩子；若无左孩子，则后继结点为右孩子。这里王道没有说算法程序设计，等我有时间再补。

3.3.4 先序线索二叉树找前驱

对于先序线索二叉树查找前驱pre，我们会发现，ltag1时，前驱就是左孩子指针。但是ltag0，采用先序遍历的话，我们发现某个结点只能做根或根的后继，无法做前驱，要想找前驱只能用土方法就是从头遍历。这里我们可以添加一个父指针，指向结点的父结点，将二叉树变成三叉树。这个时候前驱就会有如下四种情况：

3.3.5 后序线索二叉树找后继

后序线索二叉树找后继和先序线索二叉树找前驱一样，当rtag==0时，后序线索二叉树只能是根的前驱，不能是根的后继，所以无法查找后继。要查找只能采用后序遍历或像先序线索二叉树一样添加父指针。

下面是添加了父指针以后，后序线索二叉树查找后继的四种情况。

3.3.6 后序线索二叉树找前驱

对于后序线索二叉树查找前驱pre，如果该结点的ltag1，则pre直接等于左孩子指针。如果该结点的ltag0，则一定可以确定该结点有左孩子结点，由于采用后序遍历，所有可以按照上图右下角的规律，找到该结点的前驱结点。这里发现，采用后序遍历的话，前驱结点与该结点有没有右孩子有关，若有右孩子，则前驱结点为右孩子；若无右孩子，则前驱结点为左孩子。这里王道没有说算法程序设计。

3.3.7 在线索二叉树里找前驱和后继小结

这里说一下，我对几个线索二叉树后继与前驱查找可行性的理解，在我看来，一个结点能不能查找前驱或后继，关键在于看该结点作为根结点时，采用的遍历方式中，它放在什么位置，我们知道三种遍历方式无外乎就是左孩子、根节点、右孩子的排列，如果根节点放在中间，则可以查找前驱和后继，对应的就是中序遍历。如果根结点放在左边就只能查找后继，对应的是先序遍历。如果根结点放在右边，则只能查找前驱，对应的就是后序遍历。

说的再直白点，就是该结点作为根结点只能向下层查找，不能往上层查找，在先序遍历里，根结点下层的全是他的前驱，上层的全是他的后继。后序遍历里，根节点下层的全是他的后继，上层的全是他的前驱。而在中序遍历里，根结点的左子树全是它的前驱，右子树全是它的后继。

4. 树、森林

4.1 树的存储结构

4.1.1 树的逻辑结构

4.1.2 树的存储方法一——双亲表示法（顺序存储）

在双亲表示法里，定义了一个数组来存储各个结点数据，同时定义了int类型的parent变量用来指向双亲结点在数组中的存储位置下标，如上图右。

下面看下使用这种结构怎么进行增删改查操作。

首先，看下添加的操作：

使用双亲表示法进行添加操作时，只需要在数组里的data域里写上数据，并在parent里指明父结点位置即可。如上图，先添加M结点，就在11的data里写M，parent里写7；再添加L结点时，就继续往数组里添加数据。这里会发现，右边的数组看似按一行一行的逻辑顺序排列存储，其实并不需要，就像我们添加的M、L，就不是按次序存储的。

接下来，看删除的操作：

如上图，删除有两种方案，第一种删除该结点，并将该位置的双亲指针改为-1；第二种删除该结点，然后将数组最后一个存储的结点移到被删除的结点位置。

上面演示的是删除叶子结点G的方案，但是如果删除的不是叶子结点呢？假设删除D结点，如果删除D结点，意味着删除了以D为根的整棵子树，因此，还要找到D下的其他子孙结点，把所有子孙结点都给删除。这就涉及到从一个结点找到其孩子结点的操作，也就是查询的操作。如下图：

根据双亲表示法，找到一个结点的双亲结点很简单，但要想找到它的孩子就要从头到尾依次遍历，查看所有结点的双亲结点指针是否指向当前结点。所以，使用双亲表示法查找孩子很不方便。

同时，这个地方也暴露了删除方案的第一种方案的问题，如果没有用最后一个元素来填充被删除的元素，这时候进行遍历操作就意味着要多判断一个无效的结点。所以会导致遍历速度更慢。

4.1.3 树的存储方法二——孩子表示法（顺序+链式存储）

孩子表示法：顺序存储各个节点，每个结点中保存孩子链表头指针。

4.1.4 树的存储方法三——孩子兄弟表示法（链式存储）

孩子兄弟表示法就是用左指针指向第一个孩子，右指针指向该结点右边的第一个兄弟。根据孩子兄弟表示法的思路就可以将一个树转换成二叉树，如上图的转换。同理，既然可以将树转换成二叉树，也可以将二叉树逆向转换成树。

4.1.5 森林与二叉树的转换

**森林：是m棵互不相交的树的集合。**一棵树，去掉根结点，剩下的所有互不相连的子树的集合就是森林。

森林转化为二叉树：

二叉树转化为森林：

4.1.6 树的存储结构小结

4.2 树和森林的遍历

4.2.1 树的先根遍历

树的先根遍历就是先访问根结点，然后对每棵子树进行先根遍历，注意先根遍历完第一课子树才会遍历第二课子树，这是一个递归遍历的结构。

树的先根遍历序列与将这棵树转换为相应的二叉树的先序遍历序列相同。

4.2.2 树的后根遍历

树的后根遍历就是先对每棵子树进行后根遍历，然后再访问根结点。

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

4.2.3 树的层次遍历

到这里，不难发现，前面探索树的先根和后根遍历，是尽可能的往树的深处钻；而树的层次遍历，则是尽可能的横向探索。所以对树的层次遍历也可以称为对树的广度优先遍历，而对树的先根和后根遍历也可以称为对树的深度优先遍历。

4.2.4 森林的先序遍历

森林的先序遍历，就可以看成从左到右对每棵树进行先根遍历。

当然也可以将森林转换为二叉树，这时对森林的先序遍历就是对二叉树的先序遍历，如下图。

4.2.5 森林的中序遍历

森林的中序遍历，就可以看成从左到右对每棵树进行后根遍历。

同先序遍历一样，也可以将森林转换为二叉树，这时对森林的中序遍历就是对二叉树的中序遍历，如下图。

4.2.6 树和森林的遍历小结

树的先根遍历与森林的先序遍历和二叉树的先序遍历在效果上是等价的。

树的后根遍历与森林的中序遍历和二叉树的中序遍历在效果上是等价的。

在考408考试里，一般只考到求树或森林或二叉树的遍历序列。所以上面三种会其中一种的遍历序列求法即可，这样可以通过互相转换的方式进行求解。

但是外一考遍历到算法，可以将树和森林的存储结构转换为二叉树的存储结构，然后对二叉树进行算法遍历。

所以，在这里，我个人推荐掌握二叉树，毕竟二叉树本身就是很重要的考点，而且前面也对二叉树的遍历算法进行过很详细的说明，如果考试时连二叉树的都不会，我的评价，洗洗睡吧，明年再考。

4.3 哈夫曼树

4.3.1 哈夫曼树

根据上图，先了解结点的权，结点的带权路径长度和树的带权路径长度三个概念。

了解完这三个概念以后，就可以接着介绍什么是哈夫曼树。

哈夫曼树也称最优二叉树，就是在含有n个带权叶结点的二叉树中，其中带权路径长度最小的二叉树就是哈夫曼树。

注意，从上图也能看出来，哈夫曼树不唯一。

接下来看一下哈夫曼树的构造：

哈夫曼树的构造过程如上，这里说几个要注意的地方。

将n个结点分别作为n棵仅含一个结点的二叉树，构造成一个哈夫曼树，则这个哈夫曼树的结点总数为2n-1，因为每两个结点会构成1个新结点，新结点与另一个结点又会构成一个新结点，往下递推，n个结点就可以产生n-1个新结点作为连接。

从哈夫曼树的构造中不难看出，每次构造都需要两个结点，所以不存在度为1的结点，只有度为0和2的结点。

另外，哈夫曼树的构造不唯一，例如上图构造哈夫曼树的图例里，从第二个图到第三个图，是将新产生的权为3的结点和权为2的结点结合，但也可以将权为2的结点与另一个权为3的结点结合。这时产生的就是另一个哈夫曼树。但哈夫曼树不论结构怎么样，他们的WPL必然相同且为最优。

另外哈夫曼树的构造并不分左右顺序，即左右顺序任意，一般情况下，我们把权值小的结点写在左边，权值大的结点写在右边。

4.3.2 哈夫曼编码

接下来看一下哈夫曼树的应用，哈夫曼编码。

先看上图的引例，假设小渣向老渣传送100个选择题答案，对于答案选项可以通过两个二进制bit位进行编码，对应关系也在上图，基于这种编码，要传输完100个选择题的答案，需要二进制长度位200bit。

到这里，我们可以将这个引例转化为一个二叉树，树的接结点向左的路径为0，向右为1，根据A、B、C、D的编码值，就可以构造上图左的二叉树，而80题选C，10题选A等这些数据，就可以代表结点的权值。我们所求的二进制长度，就是这个树的WPL。

既然牵扯到WPL了，就可以想到最短的WPL，即将这棵树转换成哈夫曼树，是不是就可以使用更短的长度进行传输？

基于此思想，就可以按照权值，将A、B、C、D构造成如图右的哈夫曼树，依然按照左为0，右为1的原则，在路径上标上值。这时候就可以重新得到A、B、C、D的编码，基于哈夫曼树得出的编码就是哈夫曼编码。根据哈夫曼编码，得出WPL=130，这也就表示，小渣向老渣传送100个选择题答案，只需要发送长为130bit的二进制串就可以实现，并不需要传送200bit。

像上面使用哈夫曼树得出的编码，由于各个字符长度不同，所以也叫可变长度编码。

上面的例子里，A的频率也很高，那能不能仅用1表示A，来进一步缩短长度呢？答案是不可以，具体原因参考下图。

若将A编码为1，此时若传送CAAABD，转换成二进制就是0111111110，但接收方可能解码为CBBD，这就出现了差错。

所以，这里就可以总结出一个结论，对于一个字符集，要设计一个可变长度编码，所有这些字符集中的字符，对应到编码树里，只能当做叶子结点，而不能当做分支节点。从另一个角度来说，就是任何一个字符的编码不能是另一个字符的编码的前缀。

到这里，可以将哈夫曼树的知识点总结如下图：

求哈夫曼树本质上就是求最短WPL，所以，采用哈夫曼树可以应用于实现数据的压缩，这也是哈夫曼树最常用的地方。

4.3.3 哈夫曼树小结

5. 并查集

5.1 并查集

集合这个概念，在初中数学里就已经接触，集合是指具有某种特定性质的具体的或抽象的对象汇总而成的集体。在数据结构里，我们可以把几个不相干的元素，放到一个整体里，这个整体就是集合。

如上图，就是将各个元素划分为3个互不相干的子集。那基于此，可以思考一下，如何用代码表示这种逻辑关系呢？联系前面所学树、森林的结构，发现可以用树、森林来表示集合间的关系。

同一个集合内的元素，在物理上可以把他们组织成一个树状的结构，不同集合的元素就放到不同的树里，如下图，这也是我们用代码表示集合关系的思路。

接下里，我们要考虑一下集合的两个基本操作——查与并。

首先看查操作，所谓查操作就是查找一个元素到底属于哪一个集合。思想就是从指定元素开始出发，一路向根结点查找，找到根结点，就可以知道该元素属于哪一个集合。

基于查找的思想，我们可以实现判断两个元素是否属于同一集合，只要分别查找到两个元素所属集合的根结点，然后对根结点进行判断，如果根结点相同，说明是同一个集合；不同，则不属于一个集合。

如何实现集合的并操作呢？如下图：

若要实现集合的并操作，只需要让一棵树成为另一棵树的子树即可。

知道两个操作的基本思想，接下来就要考虑怎么实现代码。既然集合使用树的结构表示，那就回忆一下树的存储方法有双亲表示法、孩子表示法和孩子兄弟表示法，结合并查集的操作，可以发现，使用双亲表示法会更合适方便一些。

上图为使用双亲表示法来实现并查集，可以看到，将A~M结点划分为对应的数组下标，数组里存储该结点的父结点下标，根结点对应的数组里存储-1，表示没有父结点。基于这种存储结构，我们要想实现并、查操作就很容易了。

查，只需要从当前结点开始，查找其对应数组下标里的父结点下标，一值往上查，直到查找的数组里存储-1的下标，即可确定根结点。

并，只需要将另一棵树的根结点，将其对应数组下标里的数据从-1改成另一棵树根结点的下标即可。

下面来看一下代码实现：

(1) 并查集初始化

首先，对一些散开的数据元素，我们要先进行初始化操作，即将所有结点的数组内容都初始化为-1，表示各个元素之间各成一派，每个元素都是一个子集。初始化以后，就可以根据实际需求，将各个元素合并成几个互不相交的子集。

(2) 并查集的并与查操作

根据上面所说的并与查的思想，我们来看下代码。

并操作Union，传入存储数组 S [ ] 和两棵树的根结点Root1和Root2，判断Root1和Root2是否相同，相同则说明一个集合，不需要合并；不同，则将Root2的根结点从无改为Root1。

查操作Find，循环找到根，先判断当前结点的父结点数组下标是否小于0，小于0，则说明当前结点就是根结点，直接返回自己的下标位置即可，若不是，则查找自己父结点的父结点的数组下标，看是否小于0，若不小于0则继续往下查找，直到找到小于0的，返回当前父结点下标小于0的结点的下标。

注意，若想将两个存储元素的集合合并，要先通过Find找到两个元素对应的根结点，然后通过union将两个集合合并。

5.2 并查集的优化

接下来分析一下上面两个算法的时间复杂度：

不难发现，Union操作不涉及循环，所以时间复杂度仅有O(1)，而Find操作，由于树的结构不确定性，所以，可能出现上图右最坏的情况，这个时候，时间复杂度就是O(n)。

而为了避免出现右边这种最坏情况，我们在构造时，就要尽可能的让树的高度小，这就是我们的优化思路，即每次Union操作构建树的时候，尽量让树不要太高。

上面便是对Union操作的优化，让根结点对应数组下标的数组里存储结点数，由于正值会与数组下标产生歧义，所以用负值表示，其绝对值表示当前集合有多少结点。如上面A结点里存储-6，其绝对值为6，就表示以A为根结点的树有6个结点。用结点数区分大树和小树，在合并时，让小树合并到大树里，就可以尽可能的缩短树的高度。

注意，合并以后别忘了改变根结点数组里的结点总数数据。

这里我感觉有个疑问，在王道课里，咸鱼说通过结点数判断大树小树，但是目的是尽可能缩短树的高度，所以我感觉应该是判断树的深度，但不得不说，树的深度并不好判断。结合咸鱼说的构造时就要让树尽可能矮，所以我感觉，应该是在还是散列集就时就向最矮树构造，当构造的结点越多，构造树的深度应该就越大。但这里面其实还存在一个问题，就是在构造时为了让树矮，可能会出现我每次构造都向根结点添加，导致树只有2层深度，却很宽的问题。所以，这里我也有点疑惑，感觉还是结合具体题目，具体分析比较好。

通过Union优化算法，构造的树高不会超过[log₂n]+1，这也就是说Find操作最坏时间复杂度为：O(log₂n)。

上面说的是Union的优化算法，接下里，说一下Find的优化算法。

Find优化就是压缩路径，即从当前结点，向上查找到根结点，把这条路上查找所遍历的每一个结点，都挂到根结点下，具体过程如上图左。从L到A要经历L、E、B，所以把这三个全都挂到A下，并改变这三个对应数组下标里的值，让他们全都指向A的下标。

使用Find优化算法，可以使树高度不超过O(α(n))。至于α(n)是什么不用管，只需要知道他是一个增长很慢的函数，比log₂n还慢。对于常见的n值，如n=1000，通常α(n)<4。这也就意味着，对于常见的n值来说，Find操作的时间复杂度小于等于O(4)，几乎可以使用常数级的O(1)时间，就完成Find操作。

5.3 并查集小结

并查集思维图：

优化算法描述小结：

优化时间复杂度小结：

写在最后：该系列笔记是本人在25考研备考408过程中根据王道课程所整理的复习笔记，原本放在个人网站方便自己复习所用。现考完以后，为了给个人网站减负，故将其全部移植到CSDN上。笔记中会存在一些错别字和输入法错误，不过考完以后，实在不想再去纠错，所以欢迎大家在评论区中指出，博主看到以后会进行纠正。