Question

数据结构问题

给定一组数列（15,8,10,21,6,19,3）分别代表字符A,B,C,D,E,F,G出现的频度，试叙述建立哈夫曼树的算法思想，画出哈夫曼树，给出各字符的编码值，并说明这种编码的优点。

Answer 1

建立哈夫曼树的算法思想：

1.初始化： 根据给定的n个权值{w1,w2,…wn}构成n棵二叉树的集合F={T1,T2,..,Tn}，其中每棵二叉树Ti中只有一个带权wi的根结点，左右子树均空。

2. 找最小树：在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。

3. 删除与加入：在F中删除这两棵树，并将新的二叉树加入F中。

4. 判断：重复前两步（2和3），直到F中只含有一棵树为止。该树即为哈夫曼树

------------------------------------------------------------------------------------------

哈夫曼树

-------------------------------------------------------------------------------------------

字符编码：

A  111

B  000

C  110

D  10

E  0011

F  01

G 0010

------------------------------------------------------------------------------------------

编码的优点（具体你可以百度）

可以得到最短的编码长度。

------------------------------------------------------------------------------------------