![](https://csdnimg.cn/release/download_crawler_static/88521192/bg4.jpg)
构建哈夫曼树时,首先需要确定树中结点的构成。由于哈夫曼树的构建是从叶子结点开
始,不断地构建新的父结点,直至树根,所以结点中应包含指向父结点的指针。但是在使
用哈夫曼树时是从树根开始,根据需求遍历树中的结点,因此每个结点需要有指向其左孩
子和右孩子的指针。
所以,哈夫曼树中结点构成用代码表示为:
1. //哈夫曼树结点结构
2. typedef struct {
3. int weight;//结点权重
4. int parent, left, right;//父结点、左孩子、右孩子在数组中的位置下标
5. }HTNode, *HuffmanTree;
哈弗曼树中的查找算法
构建哈夫曼树时,需要每次根据各个结点的权重值,筛选出其中值最小的两个结点,然后
构建二叉树。
查找权重值最小的两个结点的思想是:从树组起始位置开始,首先找到两个无父结点的结
点(说明还未使用其构建成树),然后和后续无父结点的结点依次做比较,有两种情况需
要考虑:
� 如果比两个结点中较小的那个还小,就保留这个结点,删除原来较大的结点;
� 如果介于两个结点权重值之间,替换原来较大的结点;
实现代码: