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

第6章树和二叉树数据结构讲义-哈夫曼树信息工程学院魏洪涛Email:greattide@163.com1．路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。2．结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。6.6哈夫曼树

一、基本术语3．树的带权路径长度树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为wpl=，其中n为叶子结点数目，wi为第i个叶子结点的权值，li为第i个叶子结点的路径长度。1．哈夫曼树的定义在一棵二叉树中，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(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=352．哈夫曼树的构造假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1,w2,…,wn,则哈夫曼树的构造规则为：(1)将w1,w2,…,wn看成是有n棵树的森林(每棵树仅有一个结点)；(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。

下面给出哈夫曼树的构造过程，假设给定的叶子结点的权分别为1,5,7,3，则构造哈夫曼树过程如图7-24所示。构造哈夫曼树的模拟演示

在远程通讯中，要将待传字符转换成由二进制组成的字符串：设要传送的字符为：ABACCDA若编码为：A—00B—01 C—10D---11

若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能减少。00010010101100三、哈夫曼树的应用(哈夫曼编码)设要传送的字符为：ABACCDA若编码为：A—0B—00 C—1D---01

关键：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀。这种编码称作前缀编码。

ABACCDA

000011010但：0000AAAAABABB重码设要传送的字符为：ABACCDA若编码为：A—0B—110 C—10D---111

0110010101110ACBD000111采用二叉树设计二进制前缀编码规定：左分支用“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,