第7章 树和二叉树.ppt

图7-31(c) 如果以百分比值5、15、40、30、10为权构造一棵有五个叶子结点构成的哈夫曼树，则可得到图7-31（b）所示的判定树，它使大部分数据经过较少的比较次数，就能得到换算结果。由于每个判定框都有两次比较，将这两次比较分开，就可以得到如图7-31 (c)所示的判定树，按此判定树编写出的程序，将大大减少比较的次数，从而提高运算的速度。 7-6-2 哈夫曼树的建立 1．哈夫曼树构成的基本思想是： （1）由给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合: F＝{T1，T2，…，Tn}； （2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和； （3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中； （4）重复（2）、（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。 动画演示 【例7-11】的叶结点权值：2，3，5，9为例，介绍哈夫曼树的构造过程： (a) 权值之和为5 (b) 其权值之和为10 (c) 其权值之和为19 图7-32 哈夫曼树建立过程 带权路径长度为： WPL=9*1+5*2+3*3+2*3=34 对于同一组给定叶结点权值所构造的哈夫曼树，树的形状可能不同，但其带权路径长度值是相同的，而且必定是最小的。 2 3 5 10 5 5 2 3 19 9 10 5 5 2 3 【例7-12】设结点的权集W ={10，12，4，7，5，18，2}，建立一棵哈夫曼树，并求出其带权路径长度。 图7-33 哈夫曼树建立过程 2．哈夫曼树的构造算法 在构造哈夫曼树时，可以设置一个结构数组HFMT，用以保存哈夫曼树中各结点的信息。由二叉树的性质可知，具有n个叶结点的哈夫曼树共有2n?1个结点，所以2n?1即数组HFMT所需的存储空间，其结构体形式如下： 其中： weight域保存结点的权值； lchild和rchild域分别保存该结点的左、右孩子结点在数组HFMT中的序号； parent域判定一个结点是否已加入到要建立的哈夫曼树中。初始时parent的值为?1，当结点加入到树中时，该结点parent的值为其父结点在数组HFMT中的序号。 构造哈夫曼树时，首先将由n个字符形成的n个叶结点存放到数组HFMT的前n个分量中，然后根据哈夫曼方法的基本思想，不断将两个权值最小的子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HFMT数组中的前n个分量的后面。 7-6-3 哈夫曼编码 1．什么是哈夫编码？ 在数据通讯中，经常需要将传送的文字转换成由二进制字符0，1组成的二进制代码，称之为编码。 如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。哈夫曼编码是一种用于构造使电文的编码总长最短的编码方案。 2．求哈夫曼编码的方法 （1）构造哈夫曼树 设需要编码的字符集合为{d1，d2，…，dn}，它们在电文中出现的次数集合为{w1，w2，…，wn}，以d1，d2，…，dn作为叶结点，w1，w2，…，wn作为它们的权值，构造一棵哈夫曼树。 【例7-13】设有A，B，C，D，E，F 6个数据项，其出现的频度分别为6、5、4、3、2、1，构造一棵哈夫曼树，并确定它们的哈夫曼编码。 构造一棵哈夫曼树，并确定它们的哈夫曼编码。 图7-34 构造哈夫曼树到哈夫曼编码的过程 （2）在哈夫曼树上求叶结点的编码。 　　规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，如图7-34（b）编码为： A=11；B=01；C=00；D=100；E=1011；F=1010。 在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是电文的代码总长。采用哈夫曼树构造的编码是一种能使电文代码总长为最短的、不等长编码。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由