树——最优二叉树哈夫曼树是带权路径最小的一种特殊二叉树 所以也称最优二叉树 在这里不讨论基本概念如如何计算路径等 而只着重于树的创建 具体过程让我们举例而言 其基本的原理为 将所有节点一开始都视为森林 每次从森林中选取两个根节点权值最小的树合并为一棵新树 新树的根节点大小为两个子节点大小的和 并将这棵新树重新加入到森林中 如此一来每一轮操作都可以简化为两个基本操作 合并两棵树 插入新树 直到森林中只剩下一
以7个节点的权值分别为 1 3 7 9 12 18 25而言
创建的第一步:合并1、3,新增4

创建的第二步:合并4、7,新增11

创建的第三步:合并9、11,新增20

创建的第四步:合并12、18,新增30

创建的第五步:合并20、25,新增45

合并最后两棵树,得到哈夫曼树

转自https://blog.csdn.net/wang2332/article/details/
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。
发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/203383.html原文链接:https://javaforall.net