关于哈夫曼树与哈夫曼编码以及WPL计算

哈夫曼树与哈夫曼编码以及WPL计算"/>

关于哈夫曼树与哈夫曼编码以及WPL计算

哈夫曼树

哈夫曼树又称为最优二叉树:给定n个权值作为n的叶子结点,构造一课二叉树,带权路径长度达到最小

哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近

构造哈夫曼树:根据给定结点的权值,首先选择两个由下向上依次构造

1.从森林中选出两棵根节点权值最小的树作为一课新树的左子树和右子树,此新树的附加根结点的权值为这两个左右子树的权值之和(左子树的权值要小于右子树)
2.从森林中剩余结点选取权值最小的树加入到构造的新树中,向上再次形成新树,直至将森林中所有树加入到构造的新树中,最后形成一课哈夫曼树.

哈夫曼树的带权路径长度(WPL)计算

WPL=叶子结点权值X叶子结点的深度累加

哈夫曼编码:利用哈夫曼树求得的二进制编码称为哈夫曼编码

构造完成树中从根到每个叶子节点都有一条路径，对路径上的各分支约定指向左子树的分支表示”0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为各个叶子节点对应的字符编码，即是哈夫曼编码。