数据结构与算法-Huffman树及其应用

5二叉树2/985.1二叉树的概念5.2二叉树的周游5.3二叉树的存储结构5.4二叉搜索树5.5堆与优先队列5.6Huffman树及其应用5.7二叉树知识点总结主要内容3/98Huffman编码树要求给出一个具有n个外部结点的扩充二叉树该每个外部结点Ki有一个wi与之对应，作为该外部结点的权叶结点带权外部路径长度总和

(注意不管内部结点，也不用有序)权越大的叶结点离根越近；如果某个叶结点的权较小，可能就会离根较远WPL=∑

wi

li

最小ni=14/98例，3棵二叉树，都有4个叶子结点a、b、c、d，分别带权7、5、2、4，求它们各自的带权路径长度。abcd7524(1)abdc7542(2)cdba2457(3)(1)WPL=7×2+5×2+2×2+4×2=36(2)WPL=7×3+5×3+2×1+4×2=46(3)WPL=7×1+5×2+2×3+4×3=355/98假设有n个权值

{w0,w1,…wn-1}，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为

wi

，则其中带权路径长度WPL最小的二叉树称做最优二叉树。Huffman树是最优二叉树。

Huffman编码树6/98(1)根据给定的n个权值{w1,w2,…wn}构成n棵二叉树的集合F={T1,T2,…Tn}，其中每棵二叉树Ti中只有一个权值为wi

的根结点。(2)在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且置新二叉树的根结点的权值为其左、右子树根结点的权值之和。(3)在F中删除这两棵树，同时将新得到的二叉树加入集合F中。(4)重复(2)和(3)，直到F中只含一棵树为止。构造Huffman编码树7/98例，4个叶子结点

a、b、c、d，分别带权7、5、2、4。cd24b5a7初始cd246b5cd24611a7b5cd2461118构造Huffman编码树8/98例，传送ABACCD，四种字符，可以分别编码为00,01,10,11。则原电文转换为000100101011。对方接收后，采用二位一分进行译码。电文编码二进制二进制译码电文编码9/98为电文编码时，总是希望总长越短越好，如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用较短的编码，则可以减短电文的总长。例，对ABACCD重新编码，分别编码为0,00,1,01。ABCD则原电文转换为00001101。减短了。问题:如何译码？前四个二进制字符就可以多种译法。AAAABB编码10/98前缀编码若设计的长短不等的编码，满足任一个编码都不是另一个编码的前缀，则这样的编码称为前缀编码。例，A,B,C,D前缀编码可以为0,110,10,111利用二叉树设计二进制前缀编码。叶子结点表示A,B,C,D这4个字符ACBD000111左分支表示‘0’，右分支表示‘1’从根结点到叶子结点的路径上经过的二进制符号串作为该叶子结点字符的编码A(0)B(110)C(10)D(111)证明其必为前缀编码路径长度为编码长度11/98设每种字符在电文中出现的概率wi

为，则依此n个字符出现的概率做权，可以设计一棵Huffman树，使WPL=∑

wi

li

最小n-1

i=0wi

为叶子结点的出现概率(权)li

为根结点到叶子结点的路径长度Huffman编码12/98例，某通信可能出现ABCDEFGH8个字符，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，试设计Huffman编码不妨设w={5,29,7,8,14,23,3,11}排序后

w={3,5,7,8,11,14,23,29}{7,8,8,11,14,23,29}{8,11,14,15,23,29}{14,15,19,23,29}{19,23,29,29}{29,29,42}{42,58}100{100}01100110101010A(0110)B(10)C(1110)D(1111)E(110)F(00)G(0111)H(010)AG8537815CD1119H1429E

F4223

B582913/98ACEA编码为011011101100110如何译码？1.

从根结点出发，从左至右扫描编码，2.

若为‘0’则走左分支，若为‘1’则走右分支，直至叶结点为止，3.

取叶结点字符为译码结果，返回重复执行

1,2,3

直至全部译完为止10001100110101010A(0110)B(10)C(1110)D(1111)E(110)F(00)G(0111)H(010)AG8537815CD1119H1429E

F4223

B5829ACEA14/98Huffman树类

template<classT>classHuffmanTree

{private:

HuffmanTreeNode<T>*root;//Huffman树的树根

//把ht1和ht2为根的Huffman子树合并成一棵以parent为//根的二叉树

voidMergeTree(HuffmanTreeNode<T>&ht1,

HuffmanTreeNode<T>&ht2, HuffmanTreeNode<T>*parent)；

15/98Huffman树类

//删除Huffman树或其子树

voidDeleteTree(HuffmanTreeNode<T>*root)；public://构造Huffman树，weight是存储权值的数组，n是数组长度

HuffmanTree(T

weight[],intn)；

//析构函数

virtual~HuffmanTree(){DeleteTree(root);}；｝16/98Huffman树的构造

template<classT>HuffmanTree<T>::HuffmanTree(Tweight[],intn){ //定义最小值堆

MinHeap<HuffmanTreeNode<T>>heap(n);

HuffmanTreeNode<T>*parent,firstchild,secondchild;

HuffmanTreeNode<T>*NodeList=newHuffmanTreeNode<T>[n];

for(inti=0;i<n;i++){

NodeList[i].element=weight[i];

NodeList[i].parent=NodeList[i].left=NodeList[i].right=NULL;

heap.Insert(NodeList[i]);//向堆中添加元素

}//endfor17/98Huffman树的构造

for(i=0;i<n-1;i++) {//通过n-1次合并建立Huffman树

parent=newHuffmanTreeNode<T>;

firstchild=heap.RemoveMin();//选择权值最小的结点

secondchild=heap.RemoveMin();//选择权值次小的结点

//合并权值最小的两棵树

MergeTree(firstchild,secondchild,parent);

heap.Insert(*parent);/