资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2016-12-26,#,2016,数据结构,Data structure,讲授：刘斌,哈夫曼树的构造,常州信息职业技术学院,02,教,学,目标,1,2,哈夫曼算法,03,构造哈夫曼树,三、链表的插入,04,哈夫曼树的构造,1.2,3,1,2,哈夫曼树及哈夫曼编码,二、,哈夫曼树的构造,1,哈夫曼算法,哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，故称其为,哈夫曼算法,。,初始时，根据给定的,n,个权值,wl,w2,wn,构成具有,n,棵二叉树的森林,F=T1,T2, Tn,，其中每棵二叉树,Ti,中都只有一个权值为,wi,的根结点，其左右子树均为空；,在森林,F,中选出两棵根结点权值最小的树（当这样的树不止两棵树时，可以从中任选两棵），将这两棵树合并成一棵新树，为了保证新树仍是二叉树，需要增加一个新结点作为新树的根，并将所选的两棵树的根分别作为新根的左右孩子（谁左，谁右均可），这两个孩子的权值之和作为新树根的权值，将新树放回森林；,对新的森林,F,重复，直到森林,F,中只剩下一棵树为止。这棵树便是哈夫曼树。,05,哈夫曼树的构造,1.2,示例：,哈夫曼树的构造,给定,5,个叶子结点,a,，,b,，,c,，,d,和,e,，分别带权,7,，,6,，,12,，,15,和,10,。用哈夫曼算法构造哈夫曼树的过程如下：,第,1,步：,根据给定的,5,个权值,7,，,6,，,12,，,15,和,10,构成,5,棵二叉树的森林,F=T1,T2,T3,T4,T5,，如图,4-25(a),；,第,2,步：,在森林,F,中选出两棵根结点权值最小的树，将这两棵树合并成一棵新树，并添加到森林中，得到新的森林，如图,4-25(b),；,a,b,c,d,e,7,6,12,15,10,图,4-25 (a),c,d,e,a,b,12,15,10,7,6,13,图,4-25 (b),06,哈夫曼树的构造,1.2,第,3,步：,重复第,2,步，进行第二次合并，得到新的森林，如图,4-25(c),；,第,4,步：,重复第,2,步，进行第三次合并，得到新的森林，如图,4-25(d),；,a,a,b,7,6,13,c,e,12,10,22,15,a,b,13,15,28,a,b,7,6,c,e,12,10,22,图,4-25 (d),图,4-25 (c),示例：,哈夫曼树的构造,07,哈夫曼树的构造,1.2,第,5,步：,重复第,2,步，进行第四次合并，由于森林,F,中只剩下一棵树，所以它就是哈夫曼树，如图,4-25(e),。,b,a,d,c,e,50,22,28,12,10,13,15,7,图,4-25(e),6,示例：,哈夫曼树的构造,08,哈夫曼树的构造,1.2,2,3,1,说明,：,初始森林中的,n,棵二叉树，每棵树是一个孤立的结点，它们既是根，又是叶子。,n,个叶子的哈夫曼树要经过,n-1,次合并，产生,n-1,个新结点。最终求得的哈夫曼树中共有,2n-1,个结点。,哈夫曼树是严格的二叉树，没有,1,度的分支结点。,b,a,d,c,e,12,10,15,7,6,THANKS,2016.9.18,
展开阅读全文