哈夫曼树带权路径 树的路径长度怎么算

大家好，今天来为大家分享哈夫曼树带权路径的一些知识点，和树的路径长度怎么算的问题解析，大家要是都明白，那么可以忽略，如果不太清楚的话可以看看本篇文章，相信很大概率可以解决您的问题，接下来我们就一起来看看吧！

哈夫曼树带权路径长度

先构造哈夫曼树：17/\89/\36/\12所以带权路径长度WPL=（1+2）*3+6*2+8*1=29

6个叶子的哈夫曼树的带权路径

先构造哈夫曼树：17/\89/\36/\12所以带权路径长度WPL=（1+2）*3+6*2+8*1=29

5个叶子的哈夫曼树的带权路径

首先1与2结合生出3节点,再选剩下的3与刚生成的3结合生出6节点,剩下的4,5都小于6,所以4,5结合生出9节点,最后9和6结合为根节点.

1的路径000

2的路径001

3的路径01

4的路径10

5的路径11

哈夫曼树左边一定比右边小吗

不一定。

哈夫曼树是一种带权路径最小的最优二叉树，它要解决的是权重最大的叶子结点到根结点路径最短，而不是像二叉排序树一样每个结点左右子树的数值大小有严格区分。因此哈夫曼树的左子树权值不一定比右边小。

比如一堆权值为1、3、4、6、7的叶子结点要构建成哈夫曼树，先找出最小的两个结点1、3，并为它们添加父结点a1，只要保证1、3是最小的结点就行，至于它们谁是a1的左子树还是右子树不重要。同理，此时a1的权值是4，与4结点的权值相同，为它们添加父结点a2时也无所谓谁左谁右。

｛7，2，8，4，16，3，9｝构造出哈夫曼树。并计算带权路径

7个权值是72841639(1)从小到大排序23478916(这是有序序列)(2)每次提取最小的两个结点,取结点2和结点3,组成新结点N5,其权值=2+3=5,取数值较小的结点作为左分支,结点2作为左分支,而结点3就作为右分支.(3)将新结点N5放入有序序列,保持从小到大排序:4N578916(4)重复步骤(2),提取最小的两个结点,结点4与N5组成新结点N9,其权值=4+5=9,结点4的数值较小,作为左分支,N5就作为右分支.(5)将新结点N9放入有序序列,保持从小到大排序:789N916[注意:新结点N9排在原有结点9的后面](6)重复步骤(2),提取最小的两个结点,结点7与结点8组成新结点N15,其权值=7+8=15,结点7的数值较小,作为左分支,结点8就作为右分支.(7)将新结点N15放入有序序列,保持从小到大排序:9N9N1516(8)重复步骤(2),提取最小的两个结点,结点9与N9组成新结点N18,其权值=9+9=18,结点9作为左分支,N9就作为右分支.(9)将新结点N18放入有序序列,保持从小到大排序:N1516N18(10)重复步骤(2),提取最小的两个结点,N15与结点16组成新结点N31,其权值=15+16=31,N15的数值较小,作为左分支,结点16就作为右分支.(11)将新结点N31放入有序序列,保持从小到大排序:N18N31(12)重复步骤(2),提取剩下的两个结点,N18与N31组成新结点N49,其权值=18+31=49,数值较小的N18作为左分支,N31就作为右分支.最后得到哈夫曼树:N49/\N18N31/\/\9N9N1516/\/\4N578/\23带权路径长度(WPL):根结点N49到结点16的路径长度是2,结点16的带权路径长度是16*2根结点N49到结点9的路径长度是2,结点9的带权路径长度是9*2根结点N49到结点8的路径长度是3,结点8的带权路径长度是8*3根结点N49到结点7的路径长度是3,结点7的带权路径长度是7*3根结点N49到结点4的路径长度是3,结点4的带权路径长度是4*3根结点N49到结点3的路径长度是4,结点3的带权路径长度是3*4根结点N49到结点2的路径长度是4,结点2的带权路径长度是2*4所以,哈夫曼树的带权路径长度(WPL)等于16*2+9*2+8*3+7*3+4*3+3*4+2*4=127附:哈夫曼编码:规定哈夫曼树的左分支代表0,右分支代表1.从根结点N49到结点16,连续经历两次右分支,编码就是11从根结点N49到结点9,连续经历两次左分支,编码就是00从根结点N49到结点8,先经历右分支,再左分支,最后右分支,编码就是101如此类推,可以得出所有的结点的哈夫曼编码:权值16:11权值9:00权值8:101权值7:100权值4:010权值3:0111权值2:0110

n个杈的哈夫曼树多少个节点

n个叶子结点的哈夫曼树共有2n-1个结点。给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(HuffmanTree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

OK，关于哈夫曼树带权路径和树的路径长度怎么算的内容到此结束了，希望对大家有所帮助。