第7章树和二叉树-5（哈夫曼树和并查集）

7.2二叉树的概念和性质7.3二叉树的存储结构7.4二叉树基本运算及其实现7.8哈夫曼树7.7线索二叉树7.6二叉树的构造7.5二叉树的遍历7.9并查集第7章树和二叉树

7.1树的概念1/42设二叉树具有n0个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积的和，叫做二叉树的带权路径长度WPL。7.8.1哈夫曼树的定义7.8哈夫曼树7.8哈夫曼树2/42123WPL的计算：WPL=(2+3)×2+1×1=117.8.1哈夫曼树的定义3/429247524579相同的叶结点可以构造出不同的二叉树WPL(T1)=72+52+23+43+92=60WPL(T2)=74+94+53+42+21=89

具有最小带权路径长度的二叉树称为哈夫曼树（也称最优树）。7.8.1哈夫曼树的定义4/42构造哈夫曼树的原则：7.8.2构造哈夫曼树权值越大的叶结点越靠近根结点。权值越小的叶结点越远离根结点。7.8.2构造哈夫曼树5/42

（1）给定的n0个权值{W1，W2，…，Wn0}，构造n0棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F={T1，T2，…，Tn0}。

（2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和。

（3）在F中用新得到的二叉树代替这两棵树。

（4）重复（2）、（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。构造哈夫曼树的过程7.8.2构造哈夫曼树6/428W={0.05，0.29，0.07，0.08，0.14，0.23，0.03，

0.11}52971481523311835191578294258100建立哈夫曼树示例的演示创建完毕7.8.2构造哈夫曼树7/42哈夫曼树的特点n1=0：因为每次是两棵树合并为一棵树。n=n0+n1+n2

=n0+n2 =2n0-1。7.8.2构造哈夫曼树8/42

一棵哈夫曼树中共有199个结点，它用于（）个字符的编码。A.99 B.100 C.101 D.199n=2n0-1。n0=(n+1)/2=200/2=100答案为B。7.8.2构造哈夫曼树9/42规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的编码称为哈夫曼编码。7.8.3哈夫曼编码哈夫曼编码属0、1二进制编码7.8.3哈夫曼编码10/42哈夫曼编码特点：权值越大的字符编码越短，反之越长。7.8.3哈夫曼编码11/42291423118351915782942581003:0000 5:0001 11:001 7:10008:1111 23:01 29:10 14:11000001001011111产生哈夫曼编码示例的演示5：00017.8.3哈夫曼编码12/42在一组字符的哈夫曼编码中，不可能出现一个字符的哈夫曼编码是另一个字符哈夫曼编码的前缀。例如，有4个字符的编码如下：

100，001，0，1这是哈夫曼编码吗？×哈夫曼编码也称为前缀编码。创建哈夫曼树和哈夫曼编码的算法（省略）7.8.3哈夫曼编码13/42根据使用频率为5个字符设计的哈夫曼编码不可能是（）。A.111,110,10,01,00B.000,001,010,011,1C.100,11,10,1,0D.001,000,01,11,107.8.3哈夫曼编码14/42一组哈夫曼编码中没有一个编码是另外一个编码的前缀。答案为C。

设哈夫曼编码的长度不超过4，若已对两个字符编码为1和01，则最多还可对（）个字符编码。A.2 B.3C.4 D.51101010001答案为C。7.8.3哈夫曼编码15/42例如：如果已经得到完整的家谱，判断两个人是否亲戚应该是可行的。但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系就十分复杂。为了将问题简化，将得到一些亲戚关系的信息，如Marry和Tom是亲戚，Tom和Ben是亲戚，等等。从这些信息中，可以推出Marry和Ben是亲戚。7.9.1并查集的定义7.9并查集7.9并查集16/42输入：第一部分以N，M开始。N为问题涉及的人的个数（1≤N≤20000）。这些人的编号为1，2，3，…，

N。下面有M行（1≤M≤1000000），每行有两个数ai、bi，表示已知ai和bi是亲戚。第二部分以Q开始。以下Q行有Q个询问（1≤Q≤1000000），每行为ci和di，表示询问ci和di是否为亲戚。输出：对于每个询问ci、di，输出一行：若ci和di为亲戚，则输出“Yes”，否则输出“No”。解决分类问题7.9.1并查集的定义17/42输入样例：107 //N=10，M=7245713891256233 //Q=33471089类似于离散数学中的等价类问题：给定一个集合U和一个等价关系R，产生具有等价关系的等价类。7.9.1并查集的定义18/42采用集合的思路求解输入关系分离集合初始状态{1}，{2}，{3}，{4}，{5}，{6}，{7}，{8}，{9}，{10}（2，4）{1}，{2，4}，{3}，{5}，{6}，{7}，{8}，{9}，{10}（5，7）{1}，{2，4}，{3}，{5，7}，{6}，{8}，{9}，{10}（1，3）{1，3}，{2，4}，{5，7}，{6}，{8}，{9}，{10}（8，9）{1，3}，{2，4}，{5，7}，{6}，{8，9}，{10}（1，2）{1，2，3，4}，{5，7}，{6}，{8，9}，{10}（5，6）{1，2，3，4}，{5，6，7}，{8，9}，{10}（2，3）{1，2，3，4}，{5，6，7}，{8，9}，{10}7.9.1并查集的定义19/42{1，2，3，4}，{5，6，7}，{8，9}，{10}34

3、4在同一个集合中Yes求解：710

7、10不在同一个集合中No89

8、9在同一个集合中Yes结果集合：7.9.1并查集的定义20/42并查集的数据结构记录了一组动态集合S={S1，S2，…，Sk}。每个动态集合Si（1≤i≤k），通过一个“代表”加以标识，该代表即为该集合中的某个元素。选取其中哪个元素作为代表是任意的。{{1，2，3，4}，{5，6，7}，{8，9}，{10}}7.9.1并查集的定义21/42对于给定的编号为1～n的n个元素，x表示其中的一个元素，设并查集为S，并查集的实现需要支持如下运算：Init(S，n)：初始化并查集S，即S={S1，S2，…，Sn}，每个动态集合Si（1≤i≤n）仅仅包含一个编号为i的元素，该元素作为集合Si的“代表”。Find(S，x)：返回并查集S中x元素所在集合的代表。Union(S，x，y)：在并查集S中将x和y两个元素所在的动态集合（例如Sx和Sy）合并为一个新的集合Sx∪Sy。并查集{{1，2，3，4}，{5，6，7}，{8，9}，{10}}7.9.1并查集的定义22/42S={S1，S2，…，Sn}。Si用有根树来表示。S对应一个森林。Si以树根作为集合的代表，并且根结点的父结点指向其自身，树上其他结点都用一个父指针表示它的附属关系（树的双亲存储结构）。7.9.2并查集的算法实现4321{1，2，3，4}集合7.9.2并查集的算法实现23/42几个问题：（1）查找结点x4321{1，2，3，4}集合用数组存放：t[i]对应i结点→t[x]对应结点x

7.9.2并查集的算法实现24/42（2）查找x所在的集合4321{1，2，3，4}集合查找1所在的集合：3次比较4321{1，2，3，4}集合查找1所在的集合：4次比较树高度越小越好7.9.2并查集的算法实现→查找x所在树的树根25/42初始状态{1}，{2}，{3}，{4}，{5}，{6}，{7}，{8}，{9}，{10}12345678910（2，4）{1}，{2，4}，{3}，{5}，{6}，{7}，{8}，{9}，{10}12345678910（3）如何合并过程parent7.9.2并查集的算法实现26/42（5，7）{1}，{2，4}，{3}，{5，7}，{6}，{8}，{9}，{10}12345678910123456789107.9.2并查集的算法实现27/42（1，3）{1，3}，{2，4}，{5，7}，{6}，{8}，{9}，{10}12345678910123456789107.9.2并查集的算法实现28/42（8，9）{1，3}，{2，4}，{5，7}，{6}，{8，9}，{10}12345678910123456789107.9.2并查集的算法实现29/421234（1，2）{1，2，3，4}，{5，7}，{6}，{8，9}，{10}5678910123412345678910改为7.9.2并查集的算法实现30/42A和B的高度相同时，a作为b的孩子或者b作为a的孩子均可

合并树高度=hA+1=hB+1。A和B的高度不相同时，将较低的根作为较高根的孩子

合并树高度=max(hA,hB)。如何保证A（根为a）和B（根为b）合并的树高度较低呢？123412341321237.9.2并查集的算法实现

称为按高度合并31/42（4）查找中的路径压缩12312344ABxABxCC7.9.2并查集的算法实现32/42typedefstruct{intrank; //结点秩，大致为树的高度（与树高成正比）intparent; //结点对应双亲下标}UFSTree; //并查集树的结点类型并查集采用顺序方法存储，结点的类型声明如下：7.9.2并查集的算法实现按高度合并→按秩合并33/42（1）并查集树的初始化voidInit(UFSTreeS[]，intn)//初始化并查集树{inti;for(i=1;i<=n;i++){ S[i].rank=0; //秩初始化为0 S[i].parent=i; //双亲初始化指向自已}}7.9.2并查集的算法实现34/42（2）查找一个元素所属的集合intFind(UFSTreeS[]，intx)

//在x所在树中查找根结点{if(x!=S[x].parent) //双亲不是自已S[x].parent=Find(S，S[x].parent));//路径压缩

elsereturnS[x].parent;}递归算法7.9.2并查集的算法实现ABxABxCC

查找x中的路径压缩35/42intFind(UFSTreeS[],intx) //在x所在子树中查找根结点{intrx=x;while(S[rx].parent!=rx) //找到x的根rxrx=S[rx].parent;inty=x;while(y!=rx) //路径压缩{inttmp=S[y].parent;S[y].parent=rx;y=tmp;}returnrx;}非递归算法7.9.2并查集的算法实现ABxABxCC查找x中的路径压缩36/42（3）两个元素各自所属的集合的合并voidUnion(UFSTreeS[],intx,inty) //将x和y所属子集树合并{ intrx=Find(S,x); intry=Find(S,y); if(rx==ry) //x和y属于同一棵子集树 return; if(S[rx].rank>S[ry].rank) //rx结点秩大于ry结点秩 S[ry].parent=rx; //将结点ry作为结点rx的孩子7.9.2并查集的算法实现xrxyryrank[rx]>rank[ry]xrxyry37/42 else //rx结点秩小于等于ry结点秩 { S[rx].parent=ry; //将结点rx作为结点ry的孩子 if(S[rx].rank==S[ry].rank) //秩相同时 S[ry].rank++; //ry结点的秩增1 }}7.9.2并查集的算法实现xrxyryrank[ry]>rank[rx]xrxyry高度不变xrxyryrank[ry]=rank[rx]xrxyryry高度增138/42当采用路径压缩和按秩合并后：7.9.2并查集的算法实现Find(S,x)算法的时间复杂度接近O(1)。同样，Union(S,x,y)算法的时间复杂度也接近O(1)。39/42【例7.21】假设有n（n<100）个微信用户，编号为1～n，现在建立有若干朋友圈，一个朋友圈中的用户至少有2个，每个用户只能加入一个朋友圈。任意两个属于同一个朋友圈的用户称为朋友对，用二维数组R给出所有的朋友对，共m个朋友对，每个朋友对形如(a，b)。设计一个