例:已知某系统在通信联络中只可能出现八种字符，其概率分别为 0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11 试设计赫夫曼编码。1.排序 A B C D E F G H 0.03 , 0.05 , 0.07 , 0.08 , 0.11 , 0.14 , 0.23 , 0.29
2. <1>: 1.00 0/ /1 0.58 0.42 0/ /1 0/ /1 0.29 H 0.19 G 0/ /1 0/ /1 0.15 F D E 0/ /1 0.08 C 0/ /1A B
WPL = A*5 + B*5 + C*4 + F*3 + H*2 + D*3 + E*3 + G*2 = 2.71前缀编码: A:00000 B:00001 C:0001 D:100 E:101 F:001 G:11 H:01<2>: 1.00 0/ /1 0.42 0.58 0/ /1 0/ /1 0.19 G 0.29 H 0/ /1 0/ /1 0.08 E 0.15 F 0/ /1 0/ /1A B C D WPL = A*4 + B*4 + E*3 + G*2 + D*4 + C*4 + F*3 + H*2 = 2.71前缀编码: A:0000 B:0001 C:1000 D:1001 E:001 F:101 G:01 H:11
这题有两解了，出现这种情况的原因是：出现两个相等的权和一个比这两个都小的权，这种情况下不能确定选择哪个权和那个更小的权组合(比如:0.11,0.12,0.12)．所以，如果我们用手工去求解，可能会得出很多种不同答案，它们的WPL值都一样，但形状不一，其赫夫曼编码当然也相关甚大，这就给网络传输、编码、解码带来了很大的难度，为了确保对于同一个问题无论在什么情况下得到的赫夫曼编码都是一样的，这就会规定一定的顺序，具体怎么的，就不知道了．．．
赫夫曼树定义:假设有n个权值{w1,w2,...wn}，试构造一棵有n个叶子结点的二叉树， 每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树称做 最优二叉树或赫夫曼树。赫夫曼树可以用于构造赫夫曼编程(前缀编码)。
结论：赫夫曼树(最优二叉树),又称最优树,是一“类”(并不一定是一棵)带权路径长度最短的树。
PS:当然,赫夫曼树不一定要用赫夫曼算法构造,特例:1,2,3,4,5
http://bbs.csai.cn/bbs/view.Asp?Id={D0E15691-E9E4-4194-BD86-A0332D19358D}
