资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2016-12-26,#,2016,数据结构,Data structure,讲授：刘斌,哈夫曼树的概念,常州信息职业技术学院,02,教,学,目标,1,哈夫曼树（,Huffman Tree,）的有关概念,03,三、链表的插入,04,哈夫曼树的概念,1.1,一、,哈夫曼树（,Huffman Tree,）的有关概念,1,树的路径长度：,从根结点到树中每一结点的路径长度之和称为树的路径长度。,说明,：在结点数目相同的二叉树中，完全二叉树的路径长度最短。,哈夫曼树及哈夫曼编码,三、链表的插入,05,哈夫曼树的概念,1.1,一、,哈夫曼树（,Huffman Tree,）的有关概念,哈夫曼树及哈夫曼编码,2,树的带权路径长度,（,1,）结点的权（,Weight,）：,赋予树中某结点的一个有某种意义的实数，称为该结点的权。,（,2,）结点的带权路径长度：,结点到树根之间路径长度与该结点上权的乘积，称为结点的带权路径长度。,（,3,）树的带权路径长度（,Weighted Path Length of Tree,）：,树中所有叶结点的带权路径长度之和，称为树的带权路径长度，亦称为树的代价。记为：,n,表示叶子结点的数目，,w,i,和,l,i,表示叶结点,k,i,的权值和根到,k,i,之间的路径长度。,b,a,d,c,e,12,10,15,7,6,05,哈夫曼树的概念,1.1,2,3,1,3,哈夫曼树：,在权为,wl,w2,wn,的,n,个叶子所构成的所有二叉树中，带权路径长度最小（即代价最小）的二叉树称为,哈夫曼树或最优二叉树,。,叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树；,哈夫曼树中，权越大的叶子离根越近；,哈夫曼树的形态不唯一，但,WPL,值相同且最小。,06,哈夫曼树的概念,1.1,给定,5,个叶子结点,a,，,b,，,c,，,d,和,e,，分别带权,7,，,6,，,12,，,15,和,10,。可构造出许多棵二叉树，如图,4-24,所示的是其中两棵二叉树。,示例,：,a,b,c,d,e,a,b,c,d,e,它们的带权路径长度分别为：,(a)WPL=7*2+6*3+12*3+15*3+10*3=143,(b) WPL=7*3+6*3+12*2+15*2+10*2=113,THANKS,2016.9.18,
展开阅读全文