1.3 问题求解
1.3.1 建立哈夫曼树
首先,定义哈夫曼树的储存结构,该哈夫曼树的结构体需要一个整型变量储存
结点的权值 weight,由两个指针分别储存结点的左右孩子,此外,由于输入的
权值存在重复,需要额外用一个整型变量 id 加以区分。
其次,构造哈夫曼树,构造哈夫曼树的哈夫曼算法如下:
(1) 由给定的 n 个权值,构造具有 n 棵二叉树的森林,其中每一棵二叉树只
有一个带有权值的根结点,其左、右结点均为空;
(2) 在森林中选取两棵根结点权值最小和次小的二叉树,作为左右子树构造
一棵二叉树,其根结点的权值即为其左、右子树的根结点的权值之和;
(3) 从森林中删除已构成新二叉树的左右子树的两棵二叉树,并将新构成的
二叉树放入森林中;
(4) 重复(2)和(3),直到 F 中仅剩一颗二叉树,即哈夫曼树。
根据算法可知,一个由 n 个叶子结点组成的初始集合,要生成哈夫曼树需要进
行 n-1 次合并,产生 n-1 个新结点,最终所得的哈夫曼树共有 2n-1 个结点。
C 语言描述如下:
// 哈夫曼树结点结构体
typedef struct HuffmanTree
{
int weight;
int id; // id 用来主要用以区分权值相同的结点
struct HuffmanTree* lchild;
struct HuffmanTree* rchild;
}HuffmanNode;
// 构建哈夫曼树
HuffmanNode* createHuffmanTree(int* a, int n)
{
评论0