[工学]数据结构11树和二叉树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 赫夫曼编码赫夫曼编码6.6 6

2、.6 哈夫曼哈夫曼(Huffman)(Huffman)树及运用树及运用1 1、哈夫曼树的概念、哈夫曼树的概念途径：从一个祖先结点到子孙结点之间的分支构成这两个结途径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的途径；点间的途径；途径长度：途径上的分支数目称为途径长度；途径长度：途径上的分支数目称为途径长度；树的途径长度：从根到每个结点的途径长度之和。树的途径长度：从根到每个结点的途径长度之和。6.6 6.6 哈夫曼哈夫曼(Huffman)(Huffman)树及运用树及运用1 1、哈夫曼树的概念、哈夫曼树的概念结点的权：根据运用的需求可以给树的结点赋权值，给树的结点的权：根据运用的需求可

3、以给树的结点赋权值，给树的每个结点赋予一个具有某种实践意义的实数，称该实数为这每个结点赋予一个具有某种实践意义的实数，称该实数为这个结点的权；个结点的权；结点的带权途径长度：从根到该结点的途径长度与该结点权结点的带权途径长度：从根到该结点的途径长度与该结点权的乘积；的乘积；树的带权途径长度树的带权途径长度= =树中一切叶子结点的带权途径长度之和；树中一切叶子结点的带权途径长度之和；通常记作通常记作 WPL= WPL= ni=1 wi ni=1 wi li li 其中其中n n为叶子结点的个为叶子结点的个数，数， wi wi 为第为第i i个叶子结点的权值，个叶子结点的权值，lili为第为第i

4、i个叶子结点的途个叶子结点的途径长度。径长度。哈夫曼树：假设有哈夫曼树：假设有n n个权值个权值(w1 , w2 , , wn )(w1 , w2 , , wn )，构造，构造有有n n个叶子结点的二叉树，每个叶子结点有一个个叶子结点的二叉树，每个叶子结点有一个 wi wi 作为它的作为它的权值。那么带权途径长度最小的二叉树称为哈夫曼树。最权值。那么带权途径长度最小的二叉树称为哈夫曼树。最优二叉树优二叉树例例 有有4个结点，权值分别为个结点，权值分别为7，5，2，4，构造有，构造有4个叶子结点的二叉树个叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36WPL=7*3+

5、5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35dcab2475nkKKLWWPL1思索思索1：什么样的二叉树的途径长度最小？：什么样的二叉树的途径长度最小？ n个结点的二叉树中，完全二叉树具有最小的途径长度。个结点的二叉树中，完全二叉树具有最小的途径长度。 分析：分析： 一棵树的一棵树的 途径长度为途径长度为0的结点至多只需的结点至多只需1个根；个根； 途径长度为途径长度为1的结点至多只需的结点至多只需2个两个孩子；个两个孩子； 途径长度为途径长度为2的结点至多只需的结点至多只需4个；个； 依此类推：途径长度为依此类推：途径长度为k的结点至多只需的结点

6、至多只需2k个，个， 所以具有所以具有n个结点的二叉树其途径长度至少等于如下序列的前个结点的二叉树其途径长度至少等于如下序列的前n项之和。项之和。Log以以2为底的为底的n思索思索1：什么样的二叉树的途径长度最小？：什么样的二叉树的途径长度最小？ 虽然完全二叉树具有最小途径长度的性质，但不具有虽然完全二叉树具有最小途径长度的性质，但不具有独一性。独一性。 如下面的不同外形的二叉树具有最小的途径长度。如下面的不同外形的二叉树具有最小的途径长度。 因此：只能说因此：只能说 完全二叉树具有最小途径长度的性质。完全二叉树具有最小途径长度的性质。思索思索2：什么样的二叉树的带权途径长度最小？：什么样的二

7、叉树的带权途径长度最小？ 例如：给定一个权值序列例如：给定一个权值序列2,3,4,7，可构造多种二叉树形状，可构造多种二叉树形状如下：如下：2 哈夫曼树的构造哈夫曼树的构造构造哈夫曼树的步骤：构造哈夫曼树的步骤：1)根据给定的根据给定的n个权值个权值 ，构造，构造n棵只需一个根结点的二叉棵只需一个根结点的二叉树，树， n个权值分别是这些二叉树根结点的权。设个权值分别是这些二叉树根结点的权。设F是是由这由这n棵二叉树构成的集合棵二叉树构成的集合2)在在F中选取两棵根结点树值最小的树作为左、右子树，中选取两棵根结点树值最小的树作为左、右子树，构造一颗新的二叉树，置新二叉树根的权值构造一颗新的二叉树

8、，置新二叉树根的权值=左、右左、右子树根结点权值之和；子树根结点权值之和；3)从从F中删除这两颗树，并将新树参与中删除这两颗树，并将新树参与F；4)反复反复 2) 和和3)，直到，直到F中只含一颗树为止，此时得到的这中只含一颗树为止，此时得到的这棵二叉树就是哈夫曼树。棵二叉树就是哈夫曼树。例例 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 23148715292914871529113581923421135819234229148715295

9、8113581923422914871529581003、最优断定、最优断定等级等级分数段分数段比例比例ABCDE059606970798089 901000.050.150.400.300.10cini;/cini;/利用利用ifif条件语句实现条件语句实现while(i=0) while(i=0) if(i=59) cout if(i=59) coutE E else if(i=69) cout else if(i=69) coutD D else if(i=79) cout else if(i=79) coutC C else if(i=89) cout else if(i=89) co

10、utB B else cout else couti; cini; 在解某些断定问题时，利用哈夫曼树可以得到最正确断定算法。例如，下面完在解某些断定问题时，利用哈夫曼树可以得到最正确断定算法。例如，下面完成的功能是要编制一个将百分制转换成五级分制的程序。成的功能是要编制一个将百分制转换成五级分制的程序。等级等级分数段分数段比例比例ABCDE059606970798089 901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNA70a80a60CYNBYNDYNEYNA80a9060a70a80a70a60a0，构造赫夫曼树，构造赫夫曼树HTif (n

11、=1) return;m=2* n-1;HT=(HuffmanTree)malloc(m+1) * sizeof(HTNode); /为哈夫曼树分配存储空间为哈夫曼树分配存储空间for (p=HT, i=1; i=n; +i, +p, +w) * p= * w, 0, 0, 0; /用给定的用给定的n个权值个权值 ，构造，构造n棵只需一个根结点的二叉树棵只需一个根结点的二叉树for(;i=m;+i,+p) *p = 0,0,0,0;/对剩余空间进展初始化对剩余空间进展初始化for (i=n+1; i=m; +i) /按构造哈夫曼树的步骤按构造哈夫曼树的步骤2、3、4，建哈夫曼树，建哈夫曼树/在

12、在HT1.i-1 选择选择parent为为0且且weight最小的两个结点，其序号分别为最小的两个结点，其序号分别为s1和和s2。Select(HT, i-1, s1, s2);HTs1. parent =i; HTs2.parent=i; /HTi存放新子树的根结点，存放新子树的根结点，HTi.lchild=s1; HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;哈夫曼树哈夫曼树哈夫曼树对应的静态三叉链表哈夫曼树对应的静态三叉链表w,p,lch,rch w,p,lch,rch 是是weight,parent,weight,parent,lch

13、ild,rchildlchild,rchild的缩写的缩写292919195858424210010015158 8 7 7 3 3 5 5 8 8 11112323141429290 01 12 23 34 45 56 67 78 89 9101011111212131314143 39 90 00 0111111110 00 08 811111 17 7151512123 34 4191913138 89 9292914145 51010w p lch rch5 59 90 00 0292914140 00 07 710100 00 08 810100 00 0141412120 00 0

14、232313130 00 0585815156 611111001000 013131414哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示4哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示4哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示4哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示4哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示4哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示4哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示4哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示4哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示4哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示4哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示4哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示4哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示4哈夫曼算法主要步骤图示哈夫曼算法主要步骤图示4练习： 1. 假设以假设