构造哈夫曼树:以数据集(3,4,5,8,11,18,20,30)为结点,构造一棵哈夫曼数,并求其带权路径长度。

来源:百度知道 编辑:UC知道 时间:2024/05/19 00:04:26
谢谢啦 急需知道

构建哈夫曼树的步骤:
1,选取结点(node)中最小的两个,相加,构成一个新结点
2,重复第一步,直至所有结点都在同一个树型里面。
所以,大概构成后就是这样
................................... 81
.................................0/ \1
................................./ \
................................31 50
..............................0/ \1 0/\1
............................../ \ / \
............................18 13 20 30
...........................0/ \1 0/ \1
.........................../ \ / \
..........................7 11 5 8
........................0/ \1
......................../ \
........................3 4

从最下面向上读,node3和node4是初始数据里面最小的两个,
它们组成一个新结点7,
然后再重复相同的步骤,在新数据里面,7和11是最小,他们组成18,
原始数据里面的18可以消去。
重复步骤直至所有结点在同一个树型里面
现在看看
3的哈夫曼编码就是0000,而数字最大的30编码就是11

#define n 8
typedef
struct node
{
int dat