建哈夫曼树及编码,例如：已知某系统在通讯网络中只可能出现8种字符（A、B、C、D、E、F、G、H）,其频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,生成哈夫曼树并为各个字符设计哈夫曼编码.

Question

建哈夫曼树及编码,例如：
已知某系统在通讯网络中只可能出现8种字符（A、B、C、D、E、F、G、H）,其频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,生成哈夫曼树并为各个字符设计哈夫曼编码.

Answer 1

步骤：
一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空.（为方便在计算机上实现算 法,一般还要求以Ti的权值Wi的升序排列.）
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和.
三、从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中.
四、重复二和三两步,直到集合F中只有一棵二叉树为止.
简易的理解就是,假如我有A,B,C,D,E五个字符,出现的频率（即权值）分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树,即取1,2构成新树,其结点为1+2=3!