西安电子科技大学计算机学院数据结构课件 第6章（3）.pptVIP

例5: 编写按层次（同一层从左至右）遍历二叉树的算 法。 void LayerOrder(Bitree T)//层序遍历二叉树 {??InitQueue(Q); ?? EnQueue(Q,T); ??while(!QueueEmpty(Q)) { ????DeQueue(Q,p); ?visit(p); ????if(p-lchild) EnQueue(Q,p-lchild); ?if(p-rchild) EnQueue(Q,p-rchild); ?} } 作业： 6.26 * 第6章 树和二叉树 6.6 哈夫曼树及其应用 1. 哈夫曼树 ①路径长度 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径， 路径上的分支数目称做路径长度。 ②树的路径长度 从树根到每一结点的路径长度之和。 ③结点的权和带权路径长度 给树的每个结点赋予一个具有某种实际意义的实数，我们称该实数为这个结点的权。在树形结构中，我们把从树根到某一结点的路径长度与该结点的权的乘积，叫做该结点的带权路径长度。 ④树的带权路径长度WPL (Weighted Path Length of Tree) 树中所有叶子结点的带权路径长度之和，通常记为： WPL(a)=7×2＋5×2＋2×2＋4×2＝36 WPL(b)=4×2＋7×3＋5×3＋2×1＝46 WPL(c)=7×1＋5×2＋2×3＋4×3＝35 ⑤哈夫曼树(最优二叉树) 设二叉树具有n个带权值的叶子结点,那么从根结点到各个叶子结点的路径长度与相应结点权值的乘积的和,叫做二叉树的带权路径长度。 具有最小带权路径长度的二叉树称为哈夫曼树。 60 bad 0~59 70 pass 60~69 80 general 70~79 90 good 80~89 excellent 90~100 80 70 90 60 general 70~79 bad 0~59 pass 60~69 good 80~89 excellent 90~100 2.构造哈夫曼树(哈夫曼算法) 由给定的n个权值{W1,W2,...,Wn},构造n棵只有一个叶子结点的二叉树,从而得到一个二叉树的集合F={T1,T2,...,Tn}; 在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树,这棵新的二叉树根结点的权值为其左、右子树根结点权值之和; 在集合F中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到集合F中; 重复(2)、(3)两步,当F中只剩下一棵二叉树时,这棵二叉树便是所要建立的哈夫曼树。 给定权值w=(1,3,5,7)来构造一棵哈夫曼树 。 3. 哈夫曼编码 前缀编码 任一字符的编码都不是另一个字符的编码的前缀。 哈夫曼编码（最优前缀编码） 由哈夫曼树求得的前缀编码。 1 3 5 7 对应的哈夫曼编码如下： a：000 b：001 c：01 d：1 4. 哈夫曼编码算法的实现 typedef struct  { unsigned int weight ; // 结点的权值 unsigned int parent, lchild, rchild ;  }HTNode, * HuffmanTree; //动态分配数组存储哈夫曼树 typedef char * *HuffmanCode ; //动态分配数组存储哈夫曼编码 哈夫曼树中没有度为1的结点(严格的或正则的二叉树)。 n个叶子结点，共有2n-1个结点。 7 6 5 4 4 2 3 5 2 7 1 R L P w 6 3 4 5 5 11 2 5 6 6 18 1 6 7 7 0 0 0 0 0 0 0 0 0 void HuffmanCoding( HuffmanTree HT , HuffmanCode HC, int *w, int n) { m=2*n-1;  HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));  for(p=HT, i=1; i=n; ++i;++p;++w) *p ={ *w, 0, 0, 0}; for( ; i=m; ++i) *p = {0, 0, 0, 0}; for(i=n+1; i=m; i++){ select(HT, i-1, s1, s2); //在HT[1