15哈夫曼树和哈夫曼编码

6.8哈夫曼树与哈夫曼编码1.哈夫曼树与哈夫曼编码2.回溯策略3.章末复习4.例题讲解5.课堂练习6.作业6.8哈夫曼树与哈夫曼编码1.最优二叉树的定义2.如何构造最优二叉树3.前缀编码树的路径长度定义为：最优二叉树的定义从根结点到该结点的路径上分支的数目。结点的路径长度定义为：树中每个结点的路径长度之和。ACBED树的路径长度为5最优二叉树的定义树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和WPL(T)=wklk(对所有叶子结点)nk=1ABCHIDEFG75249WPL(T)=7×2+5×2+2×3+4×3+9×2=60最优二叉树的定义ABHDGCIFE74952WPL(T)=7×4+9×4+5×3+4×2+2×1=89最优二叉树的定义最优二叉树定义为：带权路径长度WPL最小的二叉树，又称为哈夫曼树。例如:已知权值W={5,6,2,9,7}95627769713952761)2)3)527赫夫曼树WPL=2×3+5×3+6×2+7×2+9×2=65赫夫曼树713952764)16713952765)1629练习:已知权值W={5,6,2,9,8}9562876865271)2)3)529赫夫曼树89134)5)WPL=2×3+5×3+6×2+8×2+9×2=67赫夫曼树6527891317652789131730赫夫曼树(赫夫曼算法)以二叉树为例:1.根据给定的n个权值{w1,w2,…,wn}，构造n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树;2.在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;赫夫曼树3.从F中删去这两棵树，同时将刚生成的新树加入到F中;4.重复(2)和(3)两步，直至F中只含一棵树为止。赫夫曼树赫夫曼树特点：1、有n个叶子结点2、没有度为1的结点3、总的结点数为2n-14、形态不唯一编码编码：用二进制数表示字符例如：ASCII码，扩展的ASCII码特点：等长编码编码假设有8个符号:a0a1a2a3a4a5a6a7000001010011100101110111011110000100001???前缀编码有时候，每个字符出现的频率不一样，采用变长编码，使得出现频率多的编码短，频率低的编码长假设A0.4B0.3C0.2D0.1ABCD0100010001011???前缀编码任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即:所传电文的总长度最短。前缀编码ABCDE67259假设有5个符号以及它们的频率：求前缀编码95271667132901010011000110010111前缀编码1、建立赫夫曼树2、对边编号3、求出叶子结点的路径4、得到字符编码ABCDE67259000110010111EDC716AB132901010011前缀编码如何译码？001011110001？？？ADECBABCDE000110010111回朔策略假设问题的解为n元组(x1,x2,…,xn)，其中xi取值于集合Si。n元组的子组(x1,x2,…,xi)(in)称为部分解，应满足一定的约束条件。对于已求得的部分解(x1,x2,…,xi)，若在添加xi+1Si+1之后仍然满足约束条件，则得到一个新的部分解(x1,x2,…,xi+1),之后继续添加xi+2Si+2并检查之;回朔策略若对于所有取值于集合Si+1的xi+1都不能得到新的满足约束条件的部分解(x1,x2,…,xi+1)，则从当前自组中删去xi，回溯到前一个部分解(x1,x2,…,xi-1)，重新添加那些值集Si中尚未考察过的xi，看是否满足约束条件。如此反复进行，直到求得满足约束条件的问题的解，或者证明问题无解。回朔策略--皇后问题求解设四皇后问题的解为(x1,x2,x3,x4),其中:xi(i=1,2,3,4)Si={1,2,3,4}约束条件为:其中任意两个xi和xj不能位于棋盘的同行、同列及同对角线。回朔策略--皇后问题求解按回溯法的定义，皇后问题求解过程为:解的初始值为空；首先添加x1=1,之后添加满足条件的x2=3，由于对所有的x3{1,2,3,4}都不能找到满足约束条件的部分解(x1,x2,x3),则回溯到部分解(x1),重新添加满足约束条件的x2=4,依次类推。回朔策略--皇后问题求解voidTrial(inti,intn){/*进入本函数时，在n×n棋盘前i-1行已放置了互不攻击的i-1个棋子。现从第i行起继续为后续棋子选择满足约束条件的位置。当求得(in)的一个合法布局时，输出之。*/if(in)输出棋盘的当前布局;elsefor(j=1;j=n;++j){在第i行第j列放置一个棋子;if(当前布局合法)Trial(i+1,n);移去第i行第j列的棋子;}}//trial回朔策略--回溯法求解的算法一般形式voidB(inti,intn){//假设已求得满足约束条件的部分解(x1,...,xi-1)，本函//数从xi起继续搜索，直到求得整个解(x1,x2,…xn)。if(in)elsewhile(!Empty(Si)){从Si中取xi的一个值viSi;if(x1,x2,…,xi)满足约束条件B(i+1,n);//继续求下一个部分解从Si中删除值vi;}}//B回朔策略—求幂集ABCABACBCABC回朔策略—求幂集000100000010100110000001010011100101110111000回朔策略—求幂集voidpowerSet(intnum){if(num=len-1){for(inti=0;i2;i++){if(i==0)mask[num]=1;elsemask[num]=0;powerSet(num+1);}}else{for(intj=0;jlen;j++){if(mask[j]==1)printf(%c,set[j]);}printf(\n);}}回朔策略—求幂集intlen=3;intmask[]={0,0,0};charset[]={'A','B','C'};intmain(intargc,char*argv[]){powerSet(0);return0;}章末复习1.熟练掌握二叉树的结构特性，了解相应的证明方法。2.熟悉二叉树的各种存储结构的特点及适用范围。3.遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。章末复习4.理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。章末复习5.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此应掌握1至2种建立二叉树和树的存储结构的方法。6.学会编写实现树的各种操作的算法。7.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。例题讲解1、在结点个数为n(n1)的各棵树中，（1）高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？（2）高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？【答案】（1）结点个数为n时，高度最小的树的高度为2，有2层；它有n-1个叶结点，1个分支结点；（2）高度最大的树的高度为n，有n层；它有1个叶结点，n-1个分支结点。例题讲解2、试分别找出满足以下条件的所有二叉树：(1)二叉树的前序序列与中序序列相同;(2)二叉树的中序序列与后序序列相同;(3)二叉树的前序序列与后序序列相同。【解答】(1)二叉树的前序序列与中序序列相同：空树或缺左子树的单支树；(2)二叉树的中序序列与后序序列相同：空树或缺右子树的单支树；(3)二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。例题讲解3、深度为k（根的层次为1）的完全二叉树至少有多少个结点？至多有多少个结点？k与结点数目n之间的关系是什么？【分析】由完全二叉树的定义可知，对于k层的完全二叉树，其上的k-1层是一棵深度为k-1的满二叉树。所以对于所有深度为k的完全二叉树，它们之间的结点数目之差等于各树最后一层的结点数目之差。例题讲解3、深度为k（根的层次为1）的完全二叉树至少有多少个结点？至多有多少个结点？k与结点数目n之间的关系是什么？【解答】深度为k的完全二叉树，其最少的结点数=深度为k-1的满二叉树的结点数+1=；其最多的结点数=深度为k的满二叉树的结点数=。k与结点数目n之间的关系可以根据二叉树的性质4得出：112112kk12knk2log1例题讲解4、对于深度为h，且只有度为0或2的结点的二叉树，结点数至少有多少？至多有多少？(分析)【分析】对于结点数至多为多少的问题比较好回答，我们知道满二叉树中只有度为0或2的结点，所以结点数至多为同等深度的满二叉树的结点数。对于结点数至少为多少的问题，由于树中只存在度为0或2的结点，即对一个结点而言，要么它没有子结点，要么就有两个子结点，所以在这样的树中，除第一层（根所在的层）外，每一层至少有两个结点。例题讲解5、已知一棵二叉树的中序序列为BDCEAFHG，后序序列为DECBHGFA，求对应的二叉树。(分析)【分析】根据各种遍历方法的定义，可知：二叉树先序序列=根+左子树先序序列+右子树先序列；二叉树中序序列=左子树中序序列+根+右子树中序列；二叉树后序序列=左子树后序序列+右子树后序序列根；例题讲解5、已知一棵二叉树的中序序列为BDCEAFHG，后序序列为DECBHGFA，求对应的二叉树。(分析)【分析】从先序和后序序列中可以很容易的知道那一个结点是根，而在中序序列中，可以根据根得到左、右子树的中序序列，相应的也就知道左、右子树的结点集合了。可以根据集合中的结点划分先序或后序序列中除根以外的结点序列，从而得到左、右子树的先序或后序序列。依次类推，便可以递归得到整棵二叉树。中序序列左子树中序序列根右子树中序序列前序序列根左子树前序序列右子树前序序列例题讲解5、已知一棵二叉树的中序序列为BDCEAFHG，后序序列为DECBHGFA，求对应的二叉树。(分析)【解答】构造这棵二叉树的过程如下所示：中序序列：BDCE[A]FHG后序序列：DECBHGF[A]中序：[B]DCE后序：DEC[B]中序：[F]HG后序：HG[F]中序：D[C]E后序：DE[C]中序：H[G]后序：H[G]中序：[D]后序：[D]中序：[E]后序：[E]中序：[H]后序：[H]AFGHEDCB可以画出这棵二叉树为：例题讲解例题讲解1、二叉树的先序遍历和中序遍历为：先序遍历：EFHIGJK；中序遍历：HFIEJKG。该二叉树根的右子树的根是（）A）EB）FC）GD）H【答案】1、C2、B3、D2、某二叉树结点的对称序（中序）序列为ABCDEFG，后序序列为BDCAFGE。该二叉树结点的前序序列为（）A）EGFACDBB）EACBDGFC）EAGCFBDD）EGACDFB3、如果一棵二叉树结点的前序序列是ABC，后序序列是CBA，则该二叉树结点的对称序序列A)必为ABCB)必为ACBC)必为BCAD)不能确定6、分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。并判断下列论述是否正确，为什么？（1）二叉树是一种特殊的树；（2）度为2的树是一棵二叉树；（3）度为2的有序树是一棵二叉树。【解答】具有3个结点的树有两种形态，如图1所示；而具有3个结点的二叉树有5种形态，如图2所示。图1图2具有3个结点的二叉树的5种形态例题讲解6、分别画出具有3个结点的树和具有3个结点的二