输入带权结点的数目及各结点的权值, 构造哈弗曼树及编码,并画出对应的哈夫曼树。
时间: 2024-02-03 07:12:12 浏览: 27
首先需要了解哈夫曼树的概念:哈夫曼树是一种带权路径长度最短的树,也称为最优二叉树。在哈夫曼树中,权值较大的结点离根较近,权值较小的结点离根较远。
构造哈夫曼树的步骤如下:
1. 将给定的权值按从小到大的顺序排列。
2. 取出权值最小的两个结点作为左右子树,其父节点的权值为左右子树权值之和。
3. 将新生成的父节点按权值大小插入到剩余结点中,重复步骤2,直到所有结点被构建为一棵树。
下面以输入为(6, 3, 8, 2, 9, 2)的哈夫曼树为例,具体步骤如下:
1. 将权值排序:(2, 2, 3, 6, 8, 9)
2. 取出权值最小的两个结点2和2,构建一个新的父节点4,左子树为2,右子树为2。
3. 排序后变为(3, 4, 6, 8, 9),取出3和4,构建一个新的父节点7,左子树为3,右子树为4。
4. 排序后变为(6, 7, 8, 9),取出6和7,构建一个新的父节点13,左子树为6,右子树为7。
5. 排序后变为(8, 9, 13),取出8和9,构建一个新的父节点17,左子树为8,右子树为9。
6. 排序后变为(13, 17),取出13和17,构建一个新的父节点30,左子树为13,右子树为17。
最终构建出的哈夫曼树如下所示:
```
30
/ \
13 17
/ \
6 7
/ \
2 2
/ \
3 4
```
根据哈夫曼树可以得到每个结点的编码,从根节点开始遍历,向左走为0,向右走为1,最终得到的编码为:
| 权值 | 编码 |
| --- | --- |
| 2 | 00 |
| 2 | 01 |
| 3 | 100 |
| 6 | 1010 |
| 8 | 1011 |
| 9 | 110 |
因此,输入为(6, 3, 8, 2, 9, 2)的哈夫曼编码为:00 01 100 1010 1011 110。