数据结构与算法——哈夫曼树
一、哈夫曼树的定义及构造思想
哈夫曼树定义：满足WPL最小的二叉树，即最优树
WPL(带权路径长度):设二叉树有n个叶结点，每个叶子结点带有权值wk，从根结点到每个叶结点长度为lk，则每个叶结点的WPL = ∑wk*lk
哈夫曼树特点：
1.没有度为1的结点，要么度为2要么度为0，因为每个结点都是由子结点两两合并而来。
2.哈夫曼树的任意非叶结点的左右子树交换后仍是哈夫曼树
3.n个叶结点的哈夫曼树共有2n-1个结点
简单证明：
n2——有2个子结点的结点
n1——有1个子结点的结点
n0——叶结点
n2 = n0 – 1
由于哈夫曼树没有n1，所以总结点数为n2+n0 = n – 1 + n = 2n – 1
4.对于同一组权值，存在不同的哈夫曼树
构造思想：每次把权值最小的两棵二叉树合并，合并后树的权值为合并前两棵树权值的和，所以这样子哈夫曼树的结构有点像金字塔，最顶端权值最大。那权值最小如何获得呢？我们可以想到用最小堆可以每次删除得到当前权值的最小值。
二、哈夫曼树用最小堆实现的代码
结果：
三、哈夫曼编码：
跟据哈夫曼树形成的非前缀编码，一个哈夫曼树的叶结点对应一个字符，附一张图：
代码实现：在之前输入的7个叶结点上，对应7个字符
结果：
链接资源：最小堆实现哈夫曼树的构造及哈夫曼编码、解码
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/95359.html
