数据结构问题

2024-10-31 20:15:28
推荐回答(1个)
回答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

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

编码的优点(具体你可以百度)

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

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