数据结构、算法与应用-C++描述9.ppt

* * 具有不同带权路径长度的扩充二叉树 霍夫曼树 带权路径长度达到最小的扩充二叉树即为霍夫曼树。 在霍夫曼树中，权值大的结点离根最近。 * * 若二叉树对于给定的频率具有最小加权外部路径长度，则这棵树被称为霍夫曼树（Huffman tree）。 Huffman于1952年提出。 霍夫曼树 * * 获得不同字符的频率。 建立具有最小加权外部路径的二叉树（即霍夫曼树），树的外部节点用字符串中的字符表示，外部节点的权重(weight)即为该字符的频率。 遍历从根到外部节点的路径得到每个字符的编码。 用字符的编码来代替字符串中的字符。 利用霍夫曼编码进行压缩 * * 为了构造霍夫曼树，首先从仅含一个外部节点的二叉树集合开始，每个外部节点代表字符串中一个不同的字符，其权重等于该字符的频率。 此后不断地从集合中选择两棵具有最小权重的二叉树，并把它们合并成一棵新的二叉树，合并方法是把这两棵二叉树分别作为左右子树，然后增加一个新的根节点。新二叉树的权重为两棵子树的权重之和。 这个过程可一直持续到仅剩下一棵树为止。 构造霍夫曼树 * * 构造霍夫曼树 * * 权重=27。到节点(a,b,c,d,e,f)的路径编码分别为(00，010，011，100，101，11) 构造霍夫曼树 * * 霍夫曼树的建立过程可以利用最小堆来实现。 最小堆用来存贮二叉树集合。 最小堆中的每个元素包括一棵二叉树及其权重值， 霍夫曼树 * * void AllPath( BiTree T, Stack S ) { if (T) { Push( S, T-data ); if (!T-Lchild !T-Rchild ) PrintStack(S); else { AllPath( T-Lchild, S ); AllPath( T-Rchild, S ); } Pop(S); } // if(T) } // AllPath 输出二叉树上从根到所有叶子结点的路径 * * void AllPath( BiTree T, Stack S, bool flag ) { if (T) { if (T-data ) {PrintStack(S);} else {if (flag ) {Push( S, 0 ); AllPath( T-Lchild, S,0 );} else { Push( S, 1 ); AllPath( T-Rchild, S ,1); } }} Pop(S); } // if(T) } // AllPath 输出二叉树上从根到所有叶子结点的路径 * * 作用 1、编码 2、优化程序 3、归并排序 * * 霍夫曼编码 主要用途是实现数据压缩。 设给出一段报文： CAST CAST SAT AT A TASA 字符集合是 { C, A, S, T }，各个字符出现的频度(次数)是 W＝{ 2, 7, 4, 5 }。 若给每个字符以等长编码 A : 00 T : 10 C : 01 S : 11 则总编码长度为 ( 2+7+4+5 ) * 2 = 36. 若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。 因各字符出现的概率为{ 2/18, 7/18, 4/18, 5/18 }。 * * 化整为 { 2, 7, 4, 5 }，以它们为各叶结点上的权值，建立霍夫曼树。左分支赋 0，右分支赋 1，得霍夫曼编码(变长编码)。 A : 0 T : 10 C : 110 S : 111 它的总编码长度：7*1+5*2+( 2+4 )*3 = 35。比等长编码的情形要短。 总编码长度正好等于 霍夫曼树的带权路径长 度WPL。 霍夫曼编码是一种无 前缀编码。解码时不会 混淆。 霍夫曼编码树 * * 编制分数转化程序 if (a60) b=‘不及格’ else if (a70) b=‘及格’ else if (a80) b=‘中等’ else if (a90) b=‘良好’ else b=‘优秀’ * * 作业 分数 0-59 60-69 70-79 80-89 90-100 比例数 0.05 0.15 0.40 0.30 0.10 * * A60 A70 A80 A90 不及格 及格 中等 优秀 良好 N N N N Y Y Y Y * * 70≤A80 80≤A90 6