哈弗曼树/霍夫曼树

热门标签

哈弗曼树 霍夫曼

一些概念

路径:从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径;
路径长度:路径上的分支数目称为路径长度;
树的路径长度:从根到每个结点的路径长度之和。
结点的权:根据应用的需要可以给树的结点赋权值;
结点的带权路径长度:从根到该结点的路径长度与该结点权的乘积;
树的带权路径长度=树中所有叶子结点的带权路径之和;通常记作 WPL=∑wi×li
哈夫曼树:假设有n个权值(w1, w2, … , wn),构造有n个叶子结点的二叉树,每个叶子结点有一个 wi作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。最优二叉树。
前缀码的定义:在一个字符集中,任何一个字符的编码都不是另一个字符编码的前缀。霍夫曼编码就是前缀码,可用于快速判断霍夫曼编码是否正确。霍夫曼树是满二叉树,若有n个节点,则共有(n+1)/2个码子

给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为霍夫曼树(Huffman Tree)。霍夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

假设哈夫曼树是二叉的话,则度为0的结点个数为N,度为2的结点个数为N-1,则结点总数为2N-1。哈夫曼树的结点个数必为奇数。

哈夫曼树不一定是完全二叉树,但一定是最优二叉树。

若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为[(n-1)/(m-1)]。边的数目等于度。

特别声明:文章多为网络转载,资源使用一般不提供任何帮助,特殊资源除外,如有侵权请联系!

评论 (0)