1．哈夫曼树的基本概念
- 结点间的路径和路径长度
路径是指从一个结点到另一个结点之间的分支序列。
路径长度是指从一个结点到另一个结点所经过的分支数目。 - 结点的权和带权路径长度
在实际的应用中，给树的每个结点赋予一个具有某种实际意义的实数，称该实数为这个结点的权。
在树型结构中，把从树根到某一结点的路径长度与该结点的权的乘积，叫做该结点的带权路径长度。 - 树的带权路径长度
树的带权路径长度为树中从根到所有叶子结点的各个带权路径长度之和，通常记为：
2. 构造哈夫曼树
哈夫曼树：它是由 n 个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树。因为这种树最早由哈夫曼（Huffman）研究，所以称为哈夫曼树，又叫最优二叉树。
- 构造哈夫曼树的算法步骤如下：
直观地看，先选择权小的，所以权小的结点被放置在树的较深层，而权较大的离根较近，这样自然在哈夫曼树中权越大叶子离根越近，这样一来，在计算树的带权路径长度时，自然会具有最小带权路径长度，这种生成算法就是一种典型的贪心法。
3. 哈夫曼树的类型定义
4．哈夫曼树的算法实现
该算法分成两大部分，其中第一部分是初始化，先初始化 ht 的前 1~n 号元素，存放叶子结点（相当初始森林），它们都没有双亲与孩子。再初始化 ht 的后 n-1 个（从 n+1~2n-1）非叶结点元素；第二部分为实施选择、删除合并 n-1 次（相当步骤（2）~（4））：选择是从当前森林中（在森林中树的根结点的双亲为 0）选择两棵根的权值最小的树；删除合并是将选到的两棵树的根权和存入 ht 的当前最前面的空闲元素中（相当于合并树中新结点），并置入相应的双亲与孩子的位置指示。
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/6203.html