递归求huffman树的叶子结点的加权路径长度wpl
发布时间
阅读量：
阅读量
由构造方式，显然，huffman树的儿子结点总是成对出现的。因此，一个父节点，要么一个儿子都没有，要么有两个儿子。
下面是递归计算wpl(weighted path length)的代码：
void calc_wpl(htn *root, int path_count, int *wpl) //root是整个huffman树的根结点
{
if(root->leftc==NULL && root->rightc==NULL) //叶子节点
{
(*wpl) += path_count * (root->weight);
return; //加不加这个return都一样
}
else //非叶节点必有两个儿子
{
calc_wpl(root->leftc, path_count+1, wpl);
calc_wpl(root->rightc, path_count+1, wpl);
}
}
cpp
然后，
int wpl=0;
calc_wpl(root, 0, &wpl);
cpp
即可。
全部评论 (0)
还没有任何评论哟~