严蔚敏数据结构课件树和二叉树.pptVIP

练习１：练习册42页6.30　　证明：树中节点u是节点v的祖先，当且仅当在先序序列中u在v之前，且在后续序列中u在v之后。 证明：本题考察学生对先序后续遍历的深一层理解，做这种题时，把特殊节点提取出来，其他节点都抽象为很多大小不同的左子树和右子树　　　　如果u是v的祖先，那么显然先序u在前，后续u在后（省略证明）　　如果先序时u在v前，有两种情况—u是v的祖先；u的祖先是v的祖先的左兄弟（在黑板上画辅助图）。假设是后者，则在后续遍历时，u也应在v的前面，所以假设不成立，原命题得证。 赫夫曼编码 主要用途是实现数据压缩。 设给出一段报文： 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。 赫夫曼编码是一种无 前缀的编码。解码时不会 混淆。 赫夫曼编码树 typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; } HTNode, *HuffmanTree; typedef char **HuffmanCode; void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w, int n) { HuffmanTree p; char *cd; int i,s1,s2,start; unsigned int c,f; if (n=1) return; // n为字符树木，m为结点树木 int m=2*n-1; HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用 建立赫夫曼树及求赫夫曼编码的算法 (p147算法6.12) for (p=HT, i=1; i=n; ++i,++p,++w) { p-weight = *w; p-parent=0; p-lchild=0;p-rchild=0; } // *p = { *w,0,0,0 }; for (; i=m;++i,++p) { p-weight = 0; p-parent=0; p-lchild=0; p-rchild=0; } //*p={ 0,0,0,0 }; for (i=n+1; i=m;++i) // 建赫夫曼树 { Select(HT,i-1,s1,s2); HT[s1].parent=i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; } //从叶子到根逆向求赫夫曼编码 HC= (HuffmanCode)malloc((n+1)*sizeof(char *)); cd = (char*)malloc(n*sizeof(char)); cd[n-1]=\0; for (i=1;i=n;++i) { start = n-1; for (c=i,f=HT[c].parent; f!=0; c=f,f=HT[f].parent) if (HT[f].lchild ==c) cd[--start]=0; else cd[--st