题目

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

提问时间：2021-03-21

答案

构建哈夫曼树的步骤：
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