带权9.1.3.5.6的五个叶子生成的哈夫曼树，带权路径长度怎么算 五个叶子的权值是 9 1 3 5 6(1)将权值从小到大排序后是 1 3 5 6 9(这是有序序列)(2)每次提取最小的两个节点，取节点1和节点3，组成新节点N4，其权值=1+3=4，节点1的数值较小，作为左分支，节点3就作为右分支.(3)将新节点N4放入有序序列，保持从小到大排序：N4 5 6 9(节点1和3已经提取掉)(4)重复步骤(2)，提取最小的两个节点，N4与节点5组成新节点N9，其权值=4+5，N4的数值较小，作为左分支，节点5就作为右分支.(5)将新节点N9放入有序序列，保持从小到大排序：6 9 N9(注意，要将新节点N9排在后，如果顺序是 6 N9 9 则会有不同的结果)(6)重复步骤(2)，完成剩下的节点，最后，得到\"哈夫曼树\"：N24\\N9 N15\\/\\N4 5 6 9\\1 3根节点N24到节点9的路径长度是2，节点9的带权路径长度是9*2根节点N24到节点6的路径长度是2，节点6的带权路径长度是6*2如此类推，可以得出其它节点的带权路径长度.所以，哈夫曼树的带权路径长度WPL等于9*2+6*2+5*2+3*3+1*3=52哈夫曼编码：规定哈夫曼树的左分支代表0，右分支代表1.从根节点N24到节点9，先后经历两次右分支，节点9的编码就是11从根节点N24到节点6，先经历右分支，再经历左分支，节点6的编码就是10从根节点N24到节点5，先经历左分支，再经历右。
哈夫曼树的带权路径长度是什么？ 1．树的路径长度树的路径长度是从树根到树中每一结点的路径长度之和.在结点数目相同的二叉树中，完全二叉树的路径长度最短.2．树的带权路径长度(Weighted Path Length of Tree，简记为WPL)结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数.结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积.树的带权路径长度(Weighted Path Length of Tree)：定义为树中所有叶结点的带权路径长度之和，通常记为：其中：n表示叶子结点的数目wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度.树的带权路径长度亦称为树的代价.3．最优二叉树或哈夫曼树在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树.【例】给定4个叶子结点a，b，c和d，分别带权7，5，2和4.构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为：(a)WPL=7*2+5*2+2*2+4*2=36(b)WPL=7*3+5*3+2*1+4*2=46(c)WPL=7*1+5*2+2*3+4*3=35其中(c)树的WPL最小，可以验证，它就是哈夫曼树.注意：① 叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树.② 最优二叉树中，权越大的叶子。
哈夫曼树和哈夫曼编码
