ch06_4 树和二叉树4-哈夫曼树和回溯

第6章树和二叉树数据结构讲义-哈夫曼树信息工程学院魏洪涛Email:[e-mail]1．路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。2．结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。6.6哈夫曼树一、基本术语3．树的带权路径长度树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为wpl=，其中n为叶子结点数目，wi为第i个叶子结点的权值，li为第i个叶子结点的路径长度。niiilw11．哈夫曼树的定义在一棵二叉树中，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffmantree)。二、构造哈夫曼树例有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35nkKKLWWPL12．哈夫曼树的构造假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1,w2,…,wn,则哈夫曼树的构造规则为：(1)将w1,w2,…,wn看成是有n棵树的森林(每棵树仅有一个结点)；(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。下面给出哈夫曼树的构造过程，假设给定的叶子结点的权分别为1,5,7,3，则构造哈夫曼树过程如图7-24所示。375157134(a)初如森林(b)一次合并后的森林59134759134716(c)二次合并后的森林(d)三合并后的森林图哈夫曼树的构造过程构造哈夫曼树的模拟演示在远程通讯中，要将待传字符转换成由二进制组成的字符串：设要传送的字符为：ABACCDA若编码为：A—00B—01C—10D---11若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能减少。00010010101100三、哈夫曼树的应用(哈夫曼编码)设要传送的字符为：ABACCDA若编码为：A—0B—00C—1D---01关键：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀。这种编码称作前缀编码。ABACCDA000011010但：0000AAAAABABB重码设要传送的字符为：ABACCDA若编码为：A—0B—110C—10D---1110110010101110ACBD000111采用二叉树设计二进制前缀编码规定：左分支用“0”表示；右分支用“1”表示译码过程：分解接收字符串：遇“0”向左，遇“1”向右；一旦到达叶子结点，则译出一个字符，反复由根出发，直到译码完成。0110010101110ACBD000111ABACCDA求Huffman编码：由叶子→根，若：（1）从左分支下去，则分支为“0”；（2）从右分支下去，则分支为“1”。ACBD000111例：已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为2，4，2，3，3，试设计Huffman编码。由Huffman树得Huffman编码为：TBACS000110110111148464220001113301TBACS出现频率越大的字符，其Huffman编码越短。６.7回溯法与树的遍历一、回溯法的基本思想回溯法：是对解空间树进行搜索的算法，从根结点开始，对树进行先序遍历，若遍历到某一结点时肯定不包含问题的解，则将该结点及其子树去掉，并从该结点向根的方向回溯到其上一结点，继续进行先序遍历。直到找到解或所有结点均遍历完。分治法：将规模为n的问题分解为k个规模较小的子问题，而这些子问题与原问题是同一问题，只是规模小了。例６-３：求含n个元素的集合的幂集Ａ的幂集：由Ａ的所有子集构成的集合。如Ａ＝｛１，2，３｝则Ａ的幂集为：ρ(A)={{1,2,3},{1,2},{1,3},{2,3},{1},{2},{3},Ø}求Ａ的幂集的解空间树：可以用高度为３的满足二叉树表示，其中由根到第一层结点的分支表示对第１个元素的取舍，第一层到第二层的分支表示对第２个元素的取舍，第二层到第三层的分支表示对第３个元素的取舍，从根到叶子的路径构成一个解。１１１１１１１００００００1,2,31,21,312,323０１表示取，０表示不取，到每个叶子的路径构成一个子集，所有路径的集合即为Ａ的幂集。例：n=3时的0-1背包问题三件物品，重量分别为16,15,15，即w=[16,15,15]价值分别为45,25,25，即p=[45,25,25]，背包空间Ｃ＝30，问：应如何装，才能使得所装物品总价值最大？穷举法：考虑所有情形，取其最大值，共有23=8种情形。贪心法：先取单位价值最大者，再取次大者。结果取重量为１６的物品。回溯法：先建立解空间树如下：１１１１１１１０００００００１表示取，０表示不取，每个分支代表一个物品第2层:w=16,p=45,第2,3层:w=15,p=25ABDHIJKLMNOGCFE用回溯法解题的三个步骤１，针对所给问题，定义问题的解空间２，确定易于搜索的解空间结构３，以先序遍历（深度优先搜索）的方式搜索解空间，并在搜索过程中使用剪枝函数避免无效搜索。使用递归方法实现回溯voidbacktrack(intt){if(tn)output(x);elsefor(inti=f(n,t);i=g(n,t);i++){x[t]=h(i);//h(i)为当前结点处x[t]的第i个可选值if(constraint(t)&&bound(t))backtrack(t+1);}//if函数内的两个函数为约束函数和界限函数}t为递归深度，tn时表示已搜索到叶子结点，for循环是对剩下的分支进行循环。例6-4求４皇后问题的所有合法布局解空间树（４叉树）的构成：根结点为空棋盘（４×４棋盘），根结点的４个孩子为由在根结点上放置了第一个皇后后形成的棋盘，第三层则是在第二层的基础上放置了第二个皇后后形成的棋盘，共有4层，第4层共有44=256个叶子。约束函数为：任何两个棋子均不在同一行，不在同一列和不在同一斜线上使用递归方法实现回溯voidTrial(inti,intn){if(in)输出棋盘的当前布局;elsefor(j=1;j=n);j++){在第i行第j列放置一个皇后if(当前布局合法)Trial(i+1,n);}//if函数内的两个函数为约束函数和界限函数}1.熟练掌握二叉树的结构特性，了解相应的证明方法。2.熟悉二叉树的各种存储结构的特点及适用范围。3.遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。4.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握1至2种建立二叉树和树的存储结构的方法。5.学会编写实现树的各种操作的算法。6.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。作业1，假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码并画出相应的哈夫曼树。2，n=5时的0-1背包问题：设有五件物品，重量分别为2,6,5,4，价值分别为6,5,4,6，背包空间Ｃ＝10，问：应如何装，才能使得所装物品总价值最大？分别用贪心算法和回溯法求解（回溯法求解时只要求画出解空间树并给出最后的解）。