《数据结构》-哈夫曼树的构造示例(三)
·
哈夫曼树的基本概念
哈夫曼树的构造算法
哈夫曼树的构造示例
哈夫曼编码的基本概念
哈夫曼编码的程序实现
存储结构
采用顺序存储结构–一维结构数组
哈夫曼树中共有 2n-1 个结点，不使用 0 下标，数组大小为 2n。
结点类型定义
typedef struct
{
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
示例
例如，有 n = 8，权值为 W = {7 19 2 6 32 3 21 10}
构造哈夫曼树
| weight | parent | lch | rch |
| 7 | 11 | 0 | 0 |
| 19 | 13 | 0 | 0 |
| 2 | 9 | 0 | 0 |
| 6 | 10 | 0 | 0 |
| 32 | 11 | 0 | 0 |
| 3 | 9 | 0 | 0 |
| 21 | 13 | 0 | 0 |
| 10 | 11 | 0 | 0 |
| 5 | 10 | 3 | 6 |
| 11 | 12 | 4 | 9 |
| 17 | 12 | 1 | 8 |
| 28 | 14 | 10 | 11 |
| 40 | 15 | 2 | 7 |
| 60 | 15 | 5 | 12 |
| 100 | 0 | 0 | 0 |
对应的哈夫曼树为
更多推荐
2
0- 0
已为社区贡献2条内容
所有评论(0)