在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛,如JPEG中就应用了哈夫曼编码。...首先介绍什么是哈夫曼树。
哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。...可以证明哈夫曼树的WPL是最小的。
哈夫曼编码步骤:
一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,......eg:对于这样的8个节点:5 29 7 8 14 23 3 11,我们进行哈夫曼编码的过程如下:
?
----
?
----
?
----
?
----
?
----
?
----
?...----
Huffman 编码树
例:D={A,B…, M}
W={2,3,5,7,11,13,17,19,23,29,31,37,41},则对应的哈夫曼树如下:
?