求哈夫曼树的带权路径长度 算法

laishuangfa 1年前 已收到1个回答 举报
赞

AYLN 幼苗

共回答了21个问题采纳率：85.7% 举报

1, T->lchild == NULL && T->rchild == NULL //叶节点
2, n + T->weight * h //加上当前叶节点的带权路径长度
3, WPL(T->lchild, h+1) //遍历左子树
4, WPL(T->rchild, h+1) //遍历右子树

1年前 追问

7

laishuangfa 举报

h好像不对哦，你这样，在遍历过第一个叶节点之后，h一直在不断累加的

举报 AYLN

h是当前节点到根节点的路径长度，h和T参数是对应的，每次调用WPL，T指向它的一个孩子，h是要加1的。由于是递归调用，当右子树递归结束时，h的值会恢复到调用之前的值，继续在其左子树递归！这两行： 3, WPL(T->lchild, h+1) //遍历左子树 4, WPL(T->rchild, h+1) //遍历右子树 两个h+1的值是相等的。形式上跟二叉树的中序遍历很相似，可参考下数据结构教材。希望采纳，如有问题，欢迎继续交流！
可能相似的问题

你能帮帮他们吗

精彩回答

Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 0.016 s. - webmaster@yulucn.com