构造赫夫曼树课件.ppt

1、数数 据据 结结 构构本章内容本章内容6.1 树的定义和基本概念6.2 二叉树 6.2.1 树的定义和基本术语 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构6.3 遍历二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.4.3 树和森林的遍历6.6 赫夫曼树及其应用 6.6.1 最优二叉树（赫夫曼树）6.6.2 赫夫曼编码线性结构与非线性结构线性结构与非线性结构 线性结构 线性表 栈和队列 串 数组和广义表 非线性结构 树 图 树是以分支关系定义的层次结构，在自然界中大量存在树的定义和基本概念树的定义

2、和基本概念 定义：树(Tree)是n(n=0)个结点的有限集T，T为空时称为空树，否则满足如下两个条件：有且仅有一个特定的称为根(Root)的结点；其余的结点可分为m(m=0)个互不相交的子集T1,T2,T3,Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。图图6-1 树的示例树的示例AABDCEGFHIMJNKL(a)只有根结点只有根结点(b)一般的树一般的树树的其他表示形式树的其他表示形式树的基本术语树的基本术语 结点(node)：一个数据元素及其若干指向其子树的分支。结点的度(degree)：结点所拥有的子树的棵数称为结点的度。树的度：树中结点度的最大值称为树的度 如图中结

3、点A的度是_，结点B的度是_，结点M的度是_，树的度是_。叶子(leaf)结点：树中度为0的结点称为叶子结点(或终端结点)。度不为0的结点称为非叶子结点(或非终端结点或分支结点)。除根结点外，分支结点又称为内部结点。ABDCEGFH IMJNKL树的基本术语树的基本术语 一个结点的子树的根称为该结点的孩子结点(child)或子结点；相应地，该结点是其孩子结点的双亲结点(parent)或父结点。同一双亲结点的所有子结点互称为兄弟结点。规定树中根结点的层次为1，其余结点的层次等于其双亲结点的层次加1。若某结点在第l(l1)层，则其子结点在第l+1层。双亲结点在同一层上的所有结点互称为堂兄弟结点。A

4、BDCEGFH IMJNKL树的基本术语树的基本术语 从根结点到达结点p所经分支上的所有结点称为p的祖先祖先(ancester)。以某结点为根的子树中的任一结点都称为该结点的子孙子孙(descent)。树的深度深度(depth)：树中结点的最大层次值，又称为树的高度，如前图中树的高度为_。有序树有序树和无序树无序树：对于一棵树，若其中每一个结点的子树（若有）具有一定的次序，则该树称为有序树，否则称为无序树。森林森林(forest)：是m(m0)棵互不相交的树的集合。显然，若将一棵树的根结点删除，剩余的子树就构成了森林。树的逻辑结构树的逻辑结构 任何一棵树是一个二元组Tree=(root,F)。

5、其中root是数据元素，称做树的根结点；F是m棵树组成的森林，F=(T1,T2,Tm)，其中Ti=（ri，Fi）称做根root的第i棵子树。当m0时，在树根和其子树森林之间存在关系：RF=|i=1,2,m,m0二叉树二叉树 二叉树是一种树形结构，每个结点至多只有两棵子树，并且二叉树的子树有左右之分，次序不能任意颠倒。二叉树的性质二叉树的性质1性质1：在非空二叉树中，第i层上至多有2i-1个结点(i1)。证明：用数学归纳法证明。当i=1时：只有一个根结点，21-1=20=1，命题成立。现假设处在第i-1层上至多有2(i-1)-1个结点。由归纳假设知，第i-1层上至多有2i-2个结点。由于二叉树每

6、个结点的度最大为2，故在第i层上最大结点数为第i-1层上最大结点数的2倍。即 22i-22i-1 二叉树的性质二叉树的性质2性质2：深度为k的二叉树至多有2k-1个结点（k1)证明：深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和。由性质1知，二叉树的第1层、第2层 第k层上的结点数至多有：20、21 2k-1。总的结点数至多有：20+21+2k-1=2k-1 二叉树的性质二叉树的性质3性质3：对任何一棵二叉树，若其叶子结点数为n0，度为2的 结点数为n2，则n0=n2+1。证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为N，则有：N=n0+n1+n2再看二叉树中的分支数

7、：除根结点外，其余每个结点都有唯一的一个进入分支，而所有这些分支都是由度为1和2的结点射出的则有：n0+n1+n2=n1+2n2+1 即 n0=n2+1 满二叉树满二叉树 一棵深度为k且有2k-1个结点的二叉树称为满二叉树(Full Binary Tree)。下页图a就是一棵深度为4的满二叉树。满二叉树的特点：每一层上的结点数总是最大结点数。满二叉树的所有的支结点都有左、右子树。可对满二叉树的结点进行连续编号，约定从根结点开始，按“自上而下、自左至右”的原则进行。完全二叉树完全二叉树 如果深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，该

8、二叉树称为完全二叉树(Complete Binary Tree)。完全二叉树是满二叉树的一部分，而满二叉树是完全二叉树的特例。完全二叉树的特点：若完全二叉树的深度为k，则所有的叶子结点都出现在第k层或k-1层。对于任一结点，如果其右子树的最大层次为l，则其左子树的最大层次为l或l+1。二叉树的性质二叉树的性质4性质4：n个结点的完全二叉树深度为：2n+1。证明：假设完全二叉树的深度为k，则根据性质2及完全二叉树的定义有：2k-1-1n2k-1 即2 k-1n2k 取对数得：k-1 2n1，则其双亲结点编号是 i/2。如果2in：则结点i为叶子结点，无左孩子；否则，其左孩子结点编号是2i如果2i

9、+1n：则结点i无右孩子；否则，其右孩子结点编号是2i+1。二叉树的顺序存储结构二叉树的顺序存储结构 用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。完全二叉树上编号为i的结点元素存储在一维数组的下标值为i-1的分量中。对于一般的二叉树，将其每个结点与完全二叉树上的结点相对照，存储在一维数组中。二叉树的链式存储结构二叉树的链式存储结构 二叉树的结点由数据元素和分别指向其左、右子树的两个分支构成。每个结点至少包含三个域：数据域和左右指针。为了便于找到双亲，也会在结点结构中增加一个指向双亲的指针域。思考：在含有n个结点的二叉链表中有n+1个空链域。Why？二叉链表存储表示

10、二叉链表存储表示遍历二叉树遍历二叉树 遍历二叉树的问题：如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。二叉树的基本组成：根结点、左子树、右子树。若能依次遍历这三部分，就遍历了二叉树。LRD(根结点)(右子树)(左子树)二叉树的遍历二叉树的遍历 假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树有六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：DLR先（根）序遍历，LDR中（根）序遍历，LRD后

11、（根）序遍历。先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。LRD(根结点)(右子树)(左子树)二叉树的遍历二叉树的遍历 假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树有六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：DLR先（根）序遍历，LDR中（根）序遍历，LRD后（根）序遍历。中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。LRD(根结点)(右子树)(左子树)二叉树的遍历二叉树的遍历 假如以L、D、R分别表示

12、遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树有六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：DLR先（根）序遍历，LDR中（根）序遍历，LRD后（根）序遍历。后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树。（3）访问根结点；LRD(根结点)(右子树)(左子树)如图所示的二叉树表达式。其先序序列为：-+a*b-cd/ef 按中序遍历,其中序序列为：a+b*c-d-e/f 按后序遍历,其后序序列为：abcd-*+ef/-e*a/b-dcf例：二叉树的遍历例：二叉树的遍历二叉树的遍历与生成二叉树的遍历与生成 遍历是二叉树各种操作

13、的基础，可以在遍历过程中对结点进行各种操作，也可在遍历过程中生成结点，建立二叉树的存储结构。上机练习上机练习 按照前面所示的算法生成一棵二叉树，并且要求程序能按照先序、中序和后序输出二叉树上的元素值。先序遍历的递归算法实现先序遍历的递归算法实现中序遍历的非递归算法中序遍历的非递归算法 设T是指向二叉树根结点的指针变量，非递归算法是：if二叉树为空，则返回；else令p=T while p不为空，p进栈，p=p-Lchild；否则(即p为空)，退栈到p，访问p所指向的结点；p=p-Rchild，转(1)；直到栈空为止。中序遍历的非递归算法实现中序遍历的非递归算法实现线索二叉树线索二叉树 遍历二叉

14、树是按一定的规则将树中的结点排列成一个线性序列，即对非线性结构的线性化操作。使每个结点仅有一个直接前驱和一个直接后继。如何保存这种前驱和后继信息呢？每个结点增加两个指针域fwd和bkwd.在含有n个结点的二叉链表中有n+1个空链域。可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息。对结点的指针域做如下规定：若结点有左孩子，则Lchild指向其左孩子，否则，指向其直接前驱；若结点有右孩子，则Rchild指向其右孩子，否则，指向其直接后继；线索二叉树线索二叉树 为避免混淆,每个结点需要增加两个标志域 用这种结点结构构成的二叉树的存储结构叫做线线索链表索链表；指向结点前驱和后继的指针叫做线

15、索线索；加上线索的二叉树称之为线索二叉树线索二叉树。Lchild Ltag data Rchild Rtag0：Lchild域指示结点的左孩子域指示结点的左孩子1 1：Lchild域指示结点的前驱域指示结点的前驱Ltag=0 0：Rchild域指示结点的右孩子域指示结点的右孩子1 1：Rchild域指示结点的后继域指示结点的后继Rtag=AFHIEGBDC(a)二叉树二叉树(b)先序线索树的逻辑形式先序线索树的逻辑形式 结点序列：结点序列：ABDCEGFHIAFHIEGBDCNIL(c)中序线索树的逻辑形式中序线索树的逻辑形式 结点序列：结点序列：DBAGECHFIAFHIEGBDCNILNI

16、L(d)后序线索树的逻辑形式后序线索树的逻辑形式 结点序列：结点序列：DBGEHIFCAAFHIEGBDCNIL写出先序、中序和后序线索树的结点序列线索二叉树的遍历线索二叉树的遍历 在线索树上进行遍历，先找到序列中的第一个结点，然后就可以依次找结点的直接后继结点直到后继为空为止。如何在线索树中找结点的直接后继?中序线索树的结点序列：DBAGECHFIAFHIEGBDCNILNIL 如果结点的右链是线索，则右链直接指示了结点的直接后继。如果结点的右链是指针。根据中序遍历的规律，非叶子结点的直接后继是遍历其右子树时访问的第一个结点，即右子树中最左下的(叶子)结点。如结点C的直接后继：沿右指针找到右

17、子树的根结点F，然后沿左链往下直到Ltag=1的结点即为C的直接后继结点H。线索二叉树的遍历线索二叉树的遍历 如何在线索树中找结点的直接前驱?若结点的Ltag=1，则左链是线索，指示其直接前驱；否则，遍历左子树时访问的最后一个结点(即沿左子树中最右往下的结点)为其直接前驱结点。二叉树的二叉线索存储表示二叉树的二叉线索存储表示 可以为二叉树的线索链表添加一个头结点，令其lchild域的指针指向二叉树的根结点，rchild域的指针指向访问的最后一个结点。并令访问的第一个节点的lchild域和最后一个结点的rchild域指向头结点。这样就建立一个双向线索链表。线索二叉树的中序遍历算法线索二叉树的中序

18、遍历算法树和森林树和森林 前面介绍了二叉树的存储结构，本节继续介绍树的存储结构。常见的树存储结构有三种 双亲表示法 孩子表示法 孩子兄弟表示法双亲表示法双亲表示法 用一组连续的存储空间来存储树的结点，同时在每个结点中附加一个指示器(整数)指示其双亲结点在链表中的位置。缺点：求孩子结点的操作需要进行遍历。孩子表示法（孩子表示法（1）树中每个结点有多个指针域，每个指针指向其一棵子树的根结点。有两种结点结构。定长结点结构 指针域的数目就是树的度。链表结构简单，但指针域的浪费明显。不定长结点结构 树中每个结点的指针域数量是该结点的度，结点不同构，节约存储空间，但操作不便。孩子表示法（孩子表示法（2）另

19、一个办法是把每个结点的孩子排列起来，看成一个线性表，以单链表作存储结构，则n个结点有n个孩子链表(叶子的孩子链表为空)，而n个头指针又组成一个线性表，可采用顺序存储结构。孩子表示法孩子表示法孩子兄弟表示法孩子兄弟表示法 又称二叉树表示法或二叉链表表示法。链表中结点的两个指针域分别指向结点的第一个孩子结点和下一个兄弟结点。树与二叉树树与二叉树 由于二叉树和树都可用二叉链表作为存储结构，以二叉链表作为媒介可以导出树和二叉树之间的一个对应关系。从物理结构来看，树和二叉树的二叉链表是相同的，只是对指针的逻辑解释不同而已。从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树一定为空。树与二叉

20、树树与二叉树森林与二叉树森林与二叉树 若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，同样可导出森林与二叉树的关系森林与二叉树的转换森林与二叉树的转换森林转换成二叉树的算法如下：设F=T1,T2,Tn是森林，则按以下规则可转换成一棵二叉树B=(root，LB，RB)若n=0，则B是空树。若n0，则二叉树B的根是森林T1的根root(T1)，B的左子树LB是从T1中根结点的子树森林F1=T11,T12,T1m 转换而成的二叉树，而其右子树RB是从森林F=T2,T3,Tn转换而成的二叉树。二叉树与森林的转换二叉树与森林的转换 二叉树转换成森林的算法如下：若B=(root，LB，RB)是一棵

21、二叉树，则按如下规则转换成森林：F=T1,T2,Tn。若B是空树，则F为空。若B非空，则F中第一棵树T1的根root(T1)就是二叉树的根root，T1中根结点的子森林F1是由树B的左子树LB转换而成的森林；F中除T1外其余树组成的的森林F=T2,T3,Tn 是由B右子树RB转换得到的森林。树和森林的遍历树和森林的遍历树的遍历有二种方法：先序遍历：先访问根结点，然后依次先序遍历完每棵子树。下图的树先序遍历的次序是：ABCDE 后序遍历：先依次后序遍历完每棵子树，然后访问根结点。下图的树后序遍历的次序是：BDCEA树和森林的遍历树和森林的遍历设F=T1,T2,Tn是森林，对F的遍历有二种方法 先

22、序遍历森林：访问森林中第一棵树的根结点 先序遍历第一棵树中根结点的子树森林 先序遍历除第一棵树外其他树构成的森林 中序遍历森林 中序遍历第一棵树中根结点的子树森林 访问森林中第一棵树的根结点 中序遍历除第一棵树外其他树构成的森林例：森林的遍历例：森林的遍历 对该森林的先序遍历序列为：ABCDEFGHIJ 对该森林的中序遍历序列为：BCDAFEHJIG赫夫曼树及其应用赫夫曼树及其应用 从树中一个结点到另一个结点的之间的分支构成这两个结点之间的路径路径。结点路径上的分支数目称为路径长度路径长度。树的路径长度树的路径长度：从树根到每一个结点的路径长度之和。结点的带权路径长度带权路径长度：从该结点的到

23、树的根结点之间的路径长度与结点的权(值)的乘积。树的带权路径长度树的带权路径长度：树中所有叶子结点的带权路径长度之和，记做：Huffman树：具有n个叶子结点(每个结点的权值为wi)的二叉树中，必定存在一棵WPL值最小的树，称这棵树为最优二叉树或Huffman树。赫夫曼树举例赫夫曼树举例 图示三棵二叉树，都有四个叶结点abcd，分别带权7、5、2、4，他们的带权路径长度分别是？赫夫曼树的应用赫夫曼树的应用 在解许多判定问题时，利用Huffman树可以得到最佳判断算法。例：编制一个将百分制转换成五级分制的程序例：编制一个将百分制转换成五级分制的程序 059 bad 6069 pass 7079

24、general 8089 good 90100 excellentif(a60)b=“bad”;else if(a70)b=“pass”;else if(a80)b“general”;else if(a90)b=“good”;else b=“excellent”;5%15%40%30%10%a60不及格不及格YNa70及格及格YNa80中等中等YNa90良好良好YN优秀优秀根据出现的频率根据出现的频率决定比较的次数决定比较的次数 判定树判定树赫夫曼树的应用赫夫曼树的应用构造赫夫曼树构造赫夫曼树 7524初始F:7 5 6合并2 475246F:7 11 1175246 合并5 6F:18 合并

25、 11527461118例：构造赫夫曼树例：构造赫夫曼树例：构造赫夫曼树例：构造赫夫曼树 请为权值集合W=8,3,4,6,5,5构造Huffman树并计算其WPL值 WPL=62+33+43+82+53+53=79345568第一步5568第二步34768第三步34755108第四步5510634713第六步1111100000855101863471331第五步8551018634713赫夫曼编码赫夫曼编码 在电报收发等数据通讯中，常需要将传送的文字转换成由二进制字符0、1组成的字符串来传输。为了使收发的速度提高，就要求电文编码要尽可能地短。此外还要保证任意字符的编码都不是另一个字符编码的前

26、缀，这种编码称为前缀编码前缀编码。Huffman树可以用来构造编码长度不等且译码不产生二义性的编码。赫夫曼编码的设计赫夫曼编码的设计 设电文中的字符集C=c1,c2,ci,cn，各个字符出现的次数或频度集W=w1,w2,wi,wn。以字符集C作为叶子结点，次数或频度集W作为结点的权值来构造 Huffman树。规定Huffman树中左分支代表0，右分支代表1”。从根结点到每个叶子结点所经历的路径分支上的“0”或“1”所组成的字符串，为该结点所对应的Huffman编码。由于每个字符都是叶子结点，不可能出现在根结点到其它字符结点的路径上，所以一个字符的Huffman编码不可能是另一个字符的Huffm

27、an编码的前缀。赫夫曼编码的设计赫夫曼编码的设计 若字符集C=a,b,c,d,e,f所对应的权值集合为W=8,3,4,6,5,5，则字符a,b,c,d,e,f所对应的Huffman编码分别是：10，010，011，00，110，111。1111100000855101863471331赫夫曼编码的实现赫夫曼编码的实现 Huffman树中没有度为1的结点，此类树称为严格的或正则的二叉树。一棵有n个叶子结点的赫夫曼树共有2n-1个结点，why？可存储在大小为2n-1的一维数组中。数据结构设计数据结构设计 生成赫夫曼树之后，编码需要从叶子结点走到根，译码需要从根走到叶子结点。因此每个结点中既要存放孩子的信息，又要存放双亲的信息。赫夫曼编码算法赫夫曼编码算法赫夫曼编码算法赫夫曼编码算法练习练习 假设用于通信的电文是由字符集a,b,c,d,e,f,g,h中的字符构成，这8个字符在电文中出现的概率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。编写一段程序，设计用于通信的赫夫曼编码。