浙江龙网

  1. 首页 > 生活百科 > >

到底什么是哈夫曼树啊，求例子

生活百科结点


到底什么是哈夫曼树啊，求例子

文章插图
哈夫曼树是给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree) 。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近 。
例子：
1、将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
2、 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3、从森林中删除选取的两棵树，并将新树加入森林；
4、重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树 。
扩展资料：
按照哈夫曼编码构思程序流程：
1、切割的顺序是从上往下，直至数组中的元素全部出现在叶节点；
2、我们思路正好相反，从数组中找出最小的两个元素作为最下面的叶节点，在向备选数组中存入这两个叶节点的和（这个新的和加入累加运算，这个和也就是所求的最小值的一部分，原因如上图） 。
3、以本题为例，备选数组中现有元素为{30，30}，再次取出两个最小元素进行求和，得到新的元素，回归备选数组并记入累加 。
4、上述2.3布重复执行直至备选数组中只有一个元素，此时累加结束，返回累加值即可
5、求数组中的最小值，可以用小根堆进行提取最为方便；此题用到了贪心的思路，即用相同的策略重复执行，直至我们得到所需的结果 。
参考资料来源:百度百科——哈夫曼树
（1）结点路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径 。
（2）路径长度：从一个结点到另一个结点所经过的分支数目 。
（2）树的路径长度：从根结点到树中每一结点的路径长度之和 。
（4）结点的权：赋予树中某结点的一个有某种意义的数量值 。
（5）结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积 。
（6）树的带权路径长度：树中所有叶子结点的带权路径长度之和，记为WPL＝w1？l1＋w2？l2＋…＋wn？ln＝∑wi？li（i＝1，2，…，n），其中，n为叶子结点的个数；wi为第i个结点的权值；li为第i个结点的路径长度 。
（7）哈夫曼树（最优二叉树）：在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树（最优二叉树） 。
如图6－40所示，各树权值都由2，2，4，11组成，但构成的二叉树的带权路径长度WPL不同，图1所示的树的带权路径长度WPL＝11？1＋4？2＋2？2＋2？2＝24；图1（b）所示的树的带权路径长度WPL＝2？1＋2？2＋4？2＋11？2＝52；图1所示的树的带权路径长度WPL＝2？2＋11？2＋2？2＋4？2＝40 。在这三棵二叉树中，图6－40（a）所示的树的带权路径长度WPL最小，因此它是最优二叉树 。
【到底什么是哈夫曼树啊，求例子】具有不同带权路径长度的二叉树

    推荐阅读


    上一篇：心软善良的三大生肖女

    下一篇：这些星座只是慢热，不是不爱你