济南大学数据结构课件 第六章.pptVIP

6.3遍历二叉树和线索二叉树 6.3.1遍历二叉树 如果按某条有哪些信誉好的足球投注网站路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。 构造二叉链表表示的二叉树的递归算法 Status CreateBiTree(BiTree T) { scanf(“%c”,ch); if (ch==‘#’) T=NULL; else { if (!(T=(BiTNode *) malloc(sizeof (BiTNode)))) exit(OVERFLOW); T-data = ch ; CreateBiTree(T-lchild); CreateBiTree(T-rchild); } return OK;}//CreateBiTree 构造二叉链表 例： 已知结点的先序序列和中序序列，求整棵二叉树。 先序序列：A B C D E F G 中序序列：C B E D A F G 中序线索二叉树 中序线索二叉树 6.6.1最优二叉树(赫夫曼树) 路径长度: 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称做路径长度。 树的路径长度: 树的路径长度是从树根到每一结点的路径长度之和。 树的带权路径长度: 树的带权路径长度为树中所有叶子结点(k)的带权路径长度ωkιk之和, 通常记作： n WPL= ∑ωkιk。 k=1 例2 最佳判定方法(p.144)(a)WPL=10x4+30x4+40x3+15x2+5x1=315(b)WPL=5x3+15x3+40x2+30x2+10x2=220 6.6.2 赫夫曼编码赫夫曼树中没有度为1的结点---严格的二叉树 //-----夫曼树和赫夫曼编码的存储表示------- 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){ //w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC. if(n=1) return; m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单未用 for(p=HT,i=1;i=n;++i,++p,++w) *p={*w,0,0,0}; for(;i=m;++i,++p) *p={0,0,0,0}; 求赫夫曼编码的算法（续一）: for(i=n+1;i=m;++i){ //建赫夫曼树 //在HT[1..i-1]选择parent为0且weight最小的两个结点, // 其序号分别为s1和s2. 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=(HffmanCode)malloc((n+1*sizeof(char *)); //分配n个字符编码的头指针向量 cd=(char *)malloc(n*sizeof(char));//分配求编码的工作空间 cd[n-1]=/0; //编码结束符. 求赫夫曼编码的算法（续二）: for(i=1;i=n;++i){ //逐个字符求赫夫曼编码 start=n-1; //编码结束符位置 for(c=i,f=HT[i];f!=0;c=f,f=Ht[