《数据结构A》第05章——07.pptVIP

数据结构 5.7 哈夫曼树和哈夫曼编码 5.1?? 树的基本概念 5.2?? 二叉树 5.3?? 二叉树的遍历 5.4?? 二叉树遍历的非递归算法 5.5?? 树和森林 5.6?? 堆和优先权队列 5.7?? 哈夫曼树和哈夫曼编码 5.8?? 并查集和等价关系 5.7.1 树的路径长度 定义5.7 从根到树中任意结点的路径长度是指从根结点到该结点的路径上所包括的边的数目。树的内路径长度定义为除叶子结点外，从根到树中其它所有结点的路径长度之和。 树的外路径长度是指从根到树中所有叶子结点的路径长度之和。 5.7.2 哈夫曼树和哈夫曼算法 哈夫曼算法 哈夫曼给出了构造具有最小加权路径长度的扩充二叉树的算法，称为哈夫曼算法。用哈夫曼算法构造的扩充二叉树称为哈夫曼编码树或哈夫曼树。 5.7.3? 哈夫曼树类 template class T class HfmTree:public BinaryTreeT { public: operator T()const {return weight;} T getW(){return weight;} void putW(const T x){ weight=x;} SetNull(){root=NULL;} private: T weight; }; 5.7.4? 构造哈夫曼树 HfmTreeT CreateHfmTree (T w[],int n) 设数组w[]中保存n个元素类型为T的权值，函数返回一棵构造成功的哈夫曼树。 ?5.6.5 哈夫曼编码 例如，有字符集S={A，B，C，D}，权值W={4，2，1，1}， 设有电文ABACABDA, 定长编码如： A：00，B：01，C：10，D：11 编码后的码文长16位。 Data Structures in C++ 定理5.1 设I和E分别是一棵扩充二叉树的内路径长度和外路径长度，n是树中非叶结点的数目，则 E＝I＋2n。 证明：对非叶结点个数n 作归纳法证明。 初始情况，令n=1，I＝0，E=2，有E＝0+2＝2。 归纳假设， 非叶结点数为 n-1 时该等式成立。 归纳步骤， 新二叉树的内路径长度为 I-k，外路径长度为 E-2(k+1)+k。根据归纳假设，我们有 E-k-2=(I-k)+2(n-1) 因而有， E＝I＋2n 定义5.8 树的加权路径长度为树中所有叶子结点的加权路径长度之和，记作 其中，m是叶子结点的个数，wk是第k个叶子结点的权，lk是从根到该叶子结点的路径长度。 哈夫曼算法 （1）用给定的一组权值{w1,w2 ,…,wn}，生成一个有n棵树组成的森林F={T1，T2，…，Tn}，其中，每棵二叉树Ti只有一个结点，即权值为wi的根结点（也是叶子）。 （2）从F中选择两棵根结点权值最小的树，作为新树根的左、右子树，新树根的权值是左、右子树根结点的权值之和。 （3）从F中删除这两棵树，另将新二叉树加入F中。 （4）重复（2）和（3），直到F中只包含一棵树为止。 weight root 函数CreateHfmTree的步骤： 首先构造n棵哈夫曼树对象，每棵树只有一个权值为w[i]的根结点，且该对象的weight为w[i]，将它们逐一加入优先权队列。 从优先权队列中取出两棵根结点值最小和次最小的哈夫曼树x和y。以它们根的权值之和为根的权值，x和y为左、右子树构造一棵新哈夫曼树，并将新树对象进优先权队列。重复执行n-1次，此时，队列中只剩下合并完成的哈夫曼树。 从队列中取出构造完毕的哈夫曼树，函数返回该哈夫曼树。 template class T HfmTreeT CreateHfmTree (T w[],int n) { PrioQueue HfmTreeT pq(n);// 空优先权队列 HfmTreeT x,y,z,zero; // 空哈夫曼树 for (int i=0;in;i++){ //构造n棵一个结点哈树 z.MakeTree(w[i],x,y); z.putW(w[i]); pq.Append(z); z.SetNull();