杨开成数据结构C语言cha

第5章树和二叉树北京师范大学教育技术学院杨开城杨开成数据结构C语言cha共55页，您现在浏览的是第1页!一、树的基本概念树的定义任何一个非空树是这样一个包含n个结点的有限集合：⑴唯一存在一个结点R，它没有前驱，被称为根；⑵当n>1时，除了根之外，其他结点可分为m(m>0)个不相交的子集T1,T2,…,Tm，其中每一个子集都是一棵树，它们的根的前驱是R，这些子集被称为R的子树。基本术语根叶子分枝结点内部结点双亲孩子祖先子孙兄弟堂兄弟度层次深度(高度)有序树无序树森林杨开成数据结构C语言cha共55页，您现在浏览的是第2页!二、二叉树——定义和基本性质(1)定义：二叉树（BinaryTree）是一种特殊的树形结构。它的特点是每个结点最多有两个子树，而且子树分左右，不能任意颠倒，我们通常称之为左子树和右子树。杨开成数据结构C语言cha共55页，您现在浏览的是第3页!二、二叉树——定义和基本性质(2)基本性质：⑴二叉树的第i层最多有2i-1（i≥1）个结点。⑵深度是k的二叉树，最多有2k－1个结点。⑶设任意一棵二叉树中，叶子结点数为n0，度是1的结点(即单枝结点)数为n1，度为2的结点(即双枝结点)数为n2，则有：n0=n2+1。⑷具有n个结点的完全二叉树的深度是⑸对于一个n个结点的完全二叉树，自上而下、自左向右给结点编号，根结点编号为1。如果已知某结点编号是i，那么①如果i=1，那么结点是根，如果i＞1，那么它的双亲是i/2,即②如果2i＞n，那么该结点没有左孩子，否则它的左孩子是2i；③如果2i+1＞n，那么该结点没有右孩子，否则它的右孩子是2i+1。杨开成数据结构C语言cha共55页，您现在浏览的是第4页!二、二叉树——存储结构(2)2．二叉树的链式存储二叉链表类型定义：typedefstructbtreenode{chardata;/*数据域可以是任意类型*/structbtreenode*lchild,*rchild;/*指向左右孩子的指针*/}BTREENODE,*BTREENODEPTR,*BTREE;三叉链表类型定义：typedefstructbtreenode{chardata;structbtreenode*lchild,*rchild;structbtreenode*parent;/*指向双亲的指针*/}PBTREENODE,*PBTREENODEPTR,*PBTREE;杨开成数据结构C语言cha共55页，您现在浏览的是第5页!二、二叉树——建立与销毁(2)typedefBTREENODEPTRelemtype;BTREECreateBtree1(char*str){/*字符串str是广义表字符串，以它作为输入数据，返回建立的二叉树*/BTREEroot=NULL;/*二叉树根结点指针*/BTREENODEPTRp;inttag,i,len;intmark;/*记录扫描到的字符类型，1代表字母,2代表(,3代表逗号,4代表)*/SQSTACKs;/*栈中存放左右孩子为生成完毕的结点*/if(str[0]==0)returnroot;/*广义表是空，返回NULL*/root=(BTREENODEPTR)malloc(sizeof(BTREENODE));/*生成根结点*/if(root==NULL)returnroot;/*假设str[0]是字母*/root->data=str[0];root->lchild=root->rchild=NULL;len=strlen(str);/*初始化栈，容量是字符串的长度*/InitSqstack(&s,len);杨开成数据结构C语言cha共55页，您现在浏览的是第6页!二、二叉树——建立与销毁(4)case',': if(mark==3)returnNULL;/*连续出现逗号，广义表非法*/ mark=3;/*扫描到逗号*/ tag=1;/*准备生成栈顶结点的右孩子*/ break;default:if(mark==1)returnNULL;/*连续出现两个字母，广义表非法*/mark=1;/*扫描到字母*/

/*如果栈空，找不到当前结点的双亲，广义表非法*/ if(IsSqstackEmpty(s))returnNULL;

/*生成当前结点，并与栈顶结点建立孩子关系*/ p=(BTREENODEPTR)malloc(sizeof(BTREENODE)); if(p==NULL) returnNULL; p->data=str[i];p->lchild=p->rchild=NULL; if(tag==0)s.elem[s.top]->lchild=p;/*当前结点是栈顶结点的左孩子*/ elses.elem[s.top]->rchild=p;/*当前结点是栈顶结点的左孩子*/ break; }returnroot;}杨开成数据结构C语言cha共55页，您现在浏览的是第7页!三、二叉树的遍历——算法(1)遍历的规则：先序遍历：ABDHJEICFG中序遍历：DJHBEIAFCG后序遍历：JHDIEBFGCA层序遍历：ABCDEFGHIJ遍历的递归算法⑴先序遍历voidPreOrder(BTREEroot,char*str){/*先序遍历二叉树root，将遍历结果存放在str中，str一开始为空*/chartmpstr[10];if(root==NULL)return;sprintf(tmpstr,"%c",root->data);/*将数据域数据转化为字符串tmpstr*/strcat(str,tmpstr);/*将tmpstr续接到str后*/PreOrder(root->lchild,str);/*遍历左子树*/PreOrder(root->rchild,str);/*遍历右子树*/}杨开成数据结构C语言cha共55页，您现在浏览的是第8页!三、二叉树的遍历——算法(3)遍历的递归算法⑶后序遍历voidPostOrder(BTREEroot,char*str){/*后序遍历二叉树root，将遍历结果存放在str中，str一开始为空*/chartmpstr[10];if(root==NULL)return;PostOrder(root->lchild,str);/*遍历左子树*/PostOrder(root->rchild,str);/*遍历右子树*//*开始访问根结点*/sprintf(tmpstr,"%c",root->data);strcat(str,tmpstr);}调用方法charstr[80];str[0]=0;PreOrder(root,str);printf("%s",str);杨开成数据结构C语言cha共55页，您现在浏览的是第9页!三、二叉树的遍历——算法(5)遍历的非递归算法⑵中序遍历voidInOrder1(BTREEroot,char*str){chartmpstr[20];SQSTACKs;BTREENODEPTRp;InitSqstack(&s,MAXCOUNT);p=root;Push(&s,p);/*将初始问题（根结点）入栈*/while(1)/*无限循环，栈空退出*/{p=s.elem[s.top];/*取栈顶问题p*/while(p->lchild!=NULL)/*只要当前问题p的左孩子不空，就继续向左递归分解*/{p=p->lchild;/*p被递归分解为它的左孩子*/Push(&s,p);/*问题p入栈，为了找到p的右孩子，生成第二个问题*/ }while(!IsSqstackEmpty(s))/*栈中可能会连续存放递归终点的问题*/{Pop(&s,&p);/*栈顶问题p出栈*/sprintf(tmpstr,"%c",p->data);strcat(str,tmpstr);/*无论p是否是递归终点，都要访问p结点自身*/杨开成数据结构C语言cha共55页，您现在浏览的是第10页!三、二叉树的遍历——算法(7)遍历的非递归算法⑶后序遍历voidPostOrder1(BTREEroot,char*str){chartmpstr[20];SQSTACKs;BTREENODEPTRp;InitSqstack(&s,MAXCOUNT);p=root;Push(&s,p);/*将问题p入栈*/while(1){p=s.elem[s.top];/*取栈顶问题p*/while(p->lchild!=NULL)/*当前问题p左孩子不空，需要递归分解*/{p=p->lchild;/*p递归分解为它的左孩子*/Push(&s,p);/*将问题p入栈，为了找到它的右孩子，即第二个问题*/ }杨开成数据结构C语言cha共55页，您现在浏览的是第11页!三、二叉树的遍历——算法(9) if(IsSqstackEmpty(s)) {/*栈空，则遍历结束*/ DestroySqstack(&s); return; } }//出栈处理while(1)}}杨开成数据结构C语言cha共55页，您现在浏览的是第12页!三、二叉树的遍历——算法的应用(1)1．求二叉树的深度intGetHeight(BTREEroot){/*返回二叉树root的深度值*/intlh,rh;if(root==NULL)return0;/*空树，深度是0*/lh=GetHeight(root->lchild);/*递归调用获得左子树的深度*/rh=GetHeight(root->rchild);/*递归调用获得右子树的深度*//*取左右子树深度值大者，作为子树的深度，这个树的深度是子树深度加1*/if(lh>=rh)returnlh+1;elsereturnrh+1;}杨开成数据结构C语言cha共55页，您现在浏览的是第13页!三、二叉树的遍历——算法的应用(3)3．利用层序遍历序列建立二叉树输入数据的例子：“ABC@DE@”和“ABCDE@”BTREECreateBtree2(char*str){/*字符串str中是二叉树的层序输入序列字符串，返回所建立的二叉树*/BTREEroot=NULL;BTREENODEPTRp1,p2;SQQUEUEq;intk;if(str[0]==0)returnroot;/*生成根结点，数据域是str[0]*/root=(BTREE)malloc(sizeof(BTREENODE));if(root==NULL)returnNULL;root->data=str[0];root->lchild=root->rchild=NULL;/*左右孩子默认为空*/InitSqqueue(&q,100);/*初始化队列*/EnSqqueue(&q,root);/*将根结点入队*/杨开成数据结构C语言cha共55页，您现在浏览的是第14页!三、二叉树的遍历——算法的应用(5)if(str[k]!=0)/*未到字符串末尾，可以为结点p1生成右孩子*/{if(str[k]!='@'){p2=(BTREENODEPTR)malloc(sizeof(BTREENODE)); if(p2==NULL) {DestroyBtree(root);returnNULL; } p2->data=str[k];p2->lchild=p2->rchild=NULL; p1->rchild=p2; EnSqqueue(&q,p2); } k++; } }//whileDestroySqqueue(&q);returnroot;}杨开成数据结构C语言cha共55页，您现在浏览的是第15页!四、线索化二叉树(2)线索化的二叉树的数据类型typedefstructthrbtreenode{chardata;intltag,rtag;/*ltag是0时，lchild指向左孩子，ltag是1时，lchild指向前驱；rtag是0时，rchild指向右孩子，rtag是1时，rchild指向后继*/structthrbtreenode*lchild,*rchild;}THRBTREENODE,*THRBTREENODEPTR,*THRBTREE;算法思想在中序遍历过程中建立线索；设置一个全局变量保存在遍历过程中当前结点的前驱；为了方便使用，我们为线索化了的二叉树设定另一个头结点head，head的左孩子指向真正二叉树的根结点，右孩子最终指向中序序列的最后一个结点（为了方便逆序遍历二叉树时很容易找到最后一个结点）。

杨开成数据结构C语言cha共55页，您现在浏览的是第16页!四、线索化二叉树(4)voidInOrderThr(THRBTREEp)/*为二叉树建立线索*/{if(p==NULL)return;/*递归终点*/InOrderThr(p->lchild);/*为左子树建立线索*/

/*这时pre是p的前驱*/if(pre!=NULL&&pre->rchild==NULL){/*如果pre不空，并且pre的右孩子是NULL，将pre的右孩子指向p*/ pre->rtag=1;/*表明pre->rchild是线索指针*/ pre->rchild=p; }if(p->lchild==NULL){/*如果p的左孩子是NULL，将p的左孩子指向pre*/ p->ltag=1;/*表明p->lchild是线索指针*/ p->lchild=pre; }pre=p;/*在遍历其他结点之前，pre指向p*/InOrderThr(p->rchild);/*为右子树建立线索*/}杨开成数据结构C语言cha共55页，您现在浏览的是第17页!四、线索化二叉树(6)先序线索化算法voidPreOrderThr(THRBTREEp)/*先序遍历的线索化操作*/{if(p==NULL)return;

/*建立pre与p之间的前驱后继关系*/if(pre!=NULL&&pre->rchild==NULL){pre->rtag=1;pre->rchild=p; }if(p->lchild==NULL){p->ltag=1;p->lchild=pre; }pre=p;/*pre指向p*/if(p->ltag==0)PreOrderThr(p->lchild);/*建立左子树的线索*/if(p->rtag==0)PreOrderThr(p->rchild);/*建立右子树的线索*/}杨开成数据结构C语言cha共55页，您现在浏览的是第18页!五、哈夫曼树(1)哈夫曼树，又称最优树，是一种带权路径长度最短的树。路径长度：树中某结点到其子树另一结点之间的分枝个数。树的路径长度：从根到每一个结点的路径长度之和。树的带权路径长度：所有叶子结点带权路径长度之和。假设一个二叉树有n个叶子结点，每个叶子结点的路径长度是lk

，权值是Wk

，那么整个二叉树的带权路径长度记为：哈夫曼树可以分为二叉哈夫曼树和多叉哈夫曼树。杨开成数据结构C语言cha共55页，您现在浏览的是第19页!五、哈夫曼树(3)哈夫曼树的构造将n个带权结点自成n个子树，每个子树只有一个根结点，这样我们就得到一个n棵二叉树的集合F={T1,T2,…,Tn}。执行循环：选取F中权值最小的两棵树Ti和Tj，生成一棵以这两棵树为左右子树的新二叉树Tk，Tk根结点的权值是Ti和Tj根结点权值之和。将Ti,和Tj从F集合中删除，将Tk加入到F集合中。直到F集合中只有一棵二叉树为止。杨开成数据结构C语言cha共55页，您现在浏览的是第20页!五、哈夫曼树(5)for(i=1;str[i]!=0;i++)/*扫描字符串，计算有多少种字符*/{for(j=i-1;j>=0;j--)/*检查str[0..i-1]中有无str[i]*/ if(str[i]==str[j])break;if(j==-1)num++;/*str[i]次出现，num增1*/ }/*n个叶子结点的哈夫曼树，其他结点个数是n-1。还需要1个单元存放叶子结点个数*/num=2*num;ht=(HUFFMANTREE)malloc(num*sizeof(HUFFMANNODE));if(ht==NULL)returnNULL;for(i=0;i<num;i++)/*初始化所有的数组单元，每个单元自成一棵树*/{ht[i].w=0;/*权值归零*/ht[i].lchild=ht[i].rchild=-1;/*左右孩子为空，用-1表示NULL*/ }

杨开成数据结构C语言cha共55页，您现在浏览的是第21页!五、哈夫曼树(7)for(i=0;i<num-1;i++)/*对叶子结点按照权值升序排序*/{k=i;for(j=i+1;j<num;j++)if(ht[j+1].w<ht[k+1].w) k=j;if(k!=i){tmpht=ht[i+1]; ht[i+1]=ht[k+1];ht[k+1]=tmpht;}}ht[0].w=num;/*用ht的首单元存放叶子结点个数*/returnht;/*返回数组*/}杨开成数据结构C语言cha共55页，您现在浏览的是第22页!五、哈夫曼树(9)for(j=num+i-1;j>=k+2;j--)/*将新结点hfnode有序插入到数组中*/if(ht[j].w>hfnode.w) ht[j+1]=ht[j];elsebreak;ht[j+1]=hfnode;root=j+1;/*root一直跟随新生成的结点,最后一个新生成的结点是根*/}returnroot;}杨开成数据结构C语言cha共55页，您现在浏览的是第23页!五、哈夫曼树(11)else{/*不是递归终点，继续递归调用*/ len=strlen(codestr); codestr[len]='0';/*左分支编码是0*/

/*向左孩子递归之前，调整路径上的编码序列，末尾增加0*/ codestr[len+1]=0; GetHuffmanCode(ht,ht[root].lchild,codestr);/*向左递归*/ len=strlen(codestr);/*右分支编码是1，向右孩子递归之前，将原编码末尾0改为1*/ codestr[len-1]='1'; GetHuffmanCode(ht,ht[root].rchild,codestr);/*向右递归*//*左右孩子递归返回后，向上返回之前，删掉编码末尾的一位*/ len=strlen(codestr); codestr[len-1]=0; }}杨开成数据结构C语言cha共55页，您现在浏览的是第24页!六、树和森林——树的存储(2)2．孩子－双亲表示法typedefstruct{chardata;/*假定树结点的数据域是char型*/intparent;/*结点的双亲，-1表示NULL*/CHILDNODEchildlink;/*孩子链表的头结点*/}CPTREENODE;杨开成数据结构C语言cha共55页，您现在浏览的是第25页!六、树和森林——森林与二叉树的转换杨开成数据结构C语言cha共55页，您现在浏览的是第26页!导航图(1)杨开成数据结构C语言cha共55页，您现在浏览的是第27页!导航图(3)杨开成数据结构C语言cha共55页，您现在浏览的是第28页!导航图(5)杨开成数据结构C语言cha共55页，您现在浏览的是第29页!二、二叉树——存储结构(1)1．二叉树的顺序存储#defineN50/*最大结点数*/typedefelemtypeSQBTREE[N+1];/*数组0号单元空闲，不存放结点*/杨开成数据结构C语言cha共55页，您现在浏览的是第30页!二、二叉树——建立与销毁(1)1．二叉树的建立——以广义表字符串作为输入例子：

A（B（D（,H（J,））,E（,I））,C（F,G））【算法思想】从左向右扫描广义表字符串，我们会遇到这样几种字符：①字母，字母代表结点，遇到字母时，当然要建立结点。需要设定一个栈，将所有左右孩子没有生成完毕的结点保存起来。当前结点的双亲必然是栈顶结点。②左括号，左括号前面一定是一个字母。因此遇到左括号时，意味着要生成前面字母结点的左右孩子，这时要将前面字母的结点入栈。③逗号，逗号的前面是某个结点的左孩子，后面是某个结点的右孩子。④右括号，右括号意味着某个结点的左右孩子都生成完毕，这个结点一定位于栈顶。这时需要出栈操作。杨开成数据结构C语言cha共55页，您现在浏览的是第31页!二、二叉树——建立与销毁(3)p=root;/*p指向当前生成的结点*/mark=1;/*标明扫描到字母*/for(i=1;str[i]!=0;i++)/*开始从左向右扫描字符串*/switch(str[i]){case'(': if(mark==2)returnNULL;/*连续出现（,非法*/ mark=2;/*扫描到左括号*/ Push(&s,p);/*将当前结点入栈*/ tag=0;/*标明准备生成左孩子*/ break;case')': mark=4;/*扫描到右括号*/

/*栈顶结点左右孩子生成完毕，出栈*/ if(!Pop(&s,&p))/*括号不配对*/ returnNULL; break;杨开成数据结构C语言cha共55页，您现在浏览的是第32页!二、二叉树——建立与销毁(4)2．二叉树的销毁voidDestroyBtree(BTREEroot){/*销毁二叉树的递归算法*/if(root==NULL)return;/*销毁左子树*/DestroyBtree(root->lchild);/*销毁右子树*/DestroyBtree(root->rchild);root->lchild=NULL;root->rchild=NULL;free(root);/*释放结点内存*/}ABCDE杨开成数据结构C语言cha共55页，您现在浏览的是第33页!三、二叉树的遍历——算法(2)遍历的递归算法⑵中序遍历voidInOrder(BTREEroot,char*str){/*中序遍历二叉树root，将遍历结果存放在str中，str一开始为空*/chartmpstr[10];if(root==NULL)return;InOrder(root->lchild,str);/*遍历左子树*/

/*开始访问根结点*/sprintf(tmpstr,"%c",root->data);/*将数据域数据转化为字符串tmpstr*/strcat(str,tmpstr);/*将tmpstr续接到str后*/InOrder(root->rchild,str);/*遍历右子树*/}杨开成数据结构C语言cha共55页，您现在浏览的是第34页!三、二叉树的遍历——算法(4)遍历的非递归算法⑴先序遍历voidPreOrder1(BTREEroot,char*str){chartmpstr[20];SQSTACKs;BTREENODEPTRp;InitSqstack(&s,MAXCOUNT);/*初始化栈,MAXCOUNT根据需要定义*/p=root;/*p指向根结点*/Push(&s,p);/*将当前结点入栈*/while(!IsSqstackEmpty(s))/*栈中有未遍历的子树*/{Pop(&s,&p);/*弹出栈顶问题（子树p）*/sprintf(tmpstr,"%c",p->data);strcat(str,tmpstr);/*访问这颗子树的根结点*/

/*将p递归分解为它的左右子树，先将右子树入栈，再将左子树入栈*/if(p->rchild!=NULL)Push(&s,p->rchild);if(p->lchild!=NULL)Push(&s,p->lchild);}DestroySqstack(&s);}杨开成数据结构C语言cha共55页，您现在浏览的是第35页!三、二叉树的遍历——算法(6)if(p->rchild!=NULL){/*如果p的右孩子不空，将p的右孩子入栈，即将第二个问题入栈*/ Push(&s,p->rchild); break;/*转去继续递归分解*/ } }if(IsSqstackEmpty(s)){/*如果发现栈空，遍历结束*/DestroySqstack(&s);return; }}}杨开成数据结构C语言cha共55页，您现在浏览的是第36页!三、二叉树的遍历——算法(8)while(1)/*出栈处理循环*/{if(s.elem[s.top]->rchild!=NULL) {/*如果栈顶结点右孩子不空，栈顶问题需要继续递归分解*/ p=s.elem[s.top]->rchild;/*p指向栈顶结点的右孩子*/ Push(&s,p);/*问题p入栈*/ break;/*转去递归分解*/}/*栈顶结点右孩子为空，才可以进行出栈处理，可能会将递归终点连续出栈*/ while(!IsSqstackEmpty(s)) {if(s.elem[s.top]->rchild==NULL||s.elem[s.top]->rchild==p) {/*栈顶问题是递归终点的条件：右孩子是空(一般首先遇到)或者它的右孩子是原栈顶结点p（这个条件只有在出栈处理时才是递归终点的条件）*/ Pop(&s,&p);/*栈顶问题p出栈*/ sprintf(tmpstr,"%c",p->data);/*访问结点p*/ strcat(str,tmpstr);} else break;/*否则跳出弹出递归终点的循环*/ }杨开成数据结构C语言cha共55页，您现在浏览的是第37页!三、二叉树的遍历——算法(10)层序遍历

voidLayerOrder(BTREEroot,char*str){/*层序遍历二叉树root,遍历结果放在str中，str一开始为空*/chartmpstr[20];SQQUEUEqu;BTREENODEPTRp;InitSqqueue(&qu,MAXCOUNT);EnSqqueue(&qu,root);/*将根结点入队*/while(!IsSqqueueEmpty(qu))/*只要队列不空就循环，队列空则遍历完毕*/{DeSqqueue(&qu,&p);/*出队一个结点p*/sprintf(tmpstr,"%c",p->data);strcat(str,tmpstr);/*访问结点p*/if(p->lchild!=NULL)/*将左孩子入队*/EnSqqueue(&qu,p->lchild);if(p->rchild!=NULL)/*将左孩子入队*/EnSqqueue(&qu,p->rchild);}}杨开成数据结构C语言cha共55页，您现在浏览的是第38页!三、二叉树的遍历——算法的应用(2)2．计算叶子结点的总数intCountLeaf(BTREEroot){/*返回二叉树root中叶子结点总数*/intlnum,rnum;if(root==NULL)return0;/*空树，叶子结点个数是0*/lnum=CountLeaf(root->lchild);/*递归调用求左子树叶子结点个数*/rnum=CountLeaf(root->rchild);/*递归调用求右子树叶子结点个数*//*如果左右子树叶子的和是0，说明当前结点是叶子，返回1；否则返回左右子树叶子结点的和*/if((lnum+rnum)==0)return1;elsereturnlnum+rnum;}杨开成数据结构C语言cha共55页，您现在浏览的是第39页!三、二叉树的遍历——算法的应用(4)k=1;/*k是字符串str的下标，从1开始向后扫描*/while(!IsSqqueueEmpty(q)){/*队列不空，意味着还有结点的左右孩子没有建立*/DeSqqueue(&q,&p1);/*出队一个结点p1*/if(str[k]!=0)/*如果字符串没有到末尾，可以为p1生成左孩子结点*/{if(str[k]!='@')/*左孩子结点不是空，生成结点*/{ p2=(BTREENODEPTR)malloc(sizeof(BTREENODE)); if(p2==NULL)/*生成结点失败，销毁已经建立的二叉树，返回NULL*/ {DestroyBtree(root);returnNULL;} p2->data=str[k];p2->lchild=p2->rchild=NULL; p1->lchild=p2;/*p2成为p1的左孩子*/ EnSqqueue(&q,p2);/*将p2入队*/ }/*如果str[k]是@，什么都不做*/ k++;/*下标先后移动*/ }杨开成数据结构C语言cha共55页，您现在浏览的是第40页!四、线索化二叉树(1)由于任何一个二叉树的结点都有两个指针域，当指针域是NULL时，它是空闲的。如果这种情况下，将指针域分别指向前驱和后继，对于查找结点的前驱后继是非常方便的。用于这个目的的lchild和rchild指针被称为线索。将lchild和rchild分别指向前驱和后继的操作被称为线索化。【问题】已知一棵二叉树，如何在中序遍历序列中确定结点B和结点I的前驱后继结点呢？【结论】如果结点具有左右子树，我们很容易确定它的前驱和后继。如果结点的左右孩子是NULL，确定起来就非常繁琐。杨开成数据结构C语言cha共55页，您现在浏览的是第41页!四、线索化二叉树(3)线索化算法THRBTREENODEPTRpre;/*全局变量pre*/THRBTREEInOrderThread(THRBTREEroot){/*为root建立线索，返回线索化了的二叉树的头结点指针*/THRBTREEhead;/*线索化二叉树的头结点*/head=(THRBTREENODEPTR)malloc(sizeof(THRBTREENODE));if(head==NULL)returnNULL;pre=NULL;/*pre初始值是NULL*/head->lchild=root;/*头结点左孩子指向二叉树的根*/head->rchild=NULL;/*头结点右孩子初始化为NULL*/InOrderThr(root);/*为二叉树建立线索*/head->rchild=pre;/*这时，pre指向中序遍历最后一个结点*/returnhead;/*返回头结点指针*/}杨开成数据结构C语言cha共55页，您现在浏览的是第42页!四、线索化二叉树(5)利用中序线索遍历二叉树voidTraverseInOrderThr(THRBTREEroot,char*str){/*遍历线索化了的二叉树，将遍历结果存放在str中*/chartmpstr[20];THRBTREENODEPTRp;p=root;/*p指向根结点*/while(1)/*遍历循环*/{while(p->ltag==0)/*寻找p的最左端结点*/p=p->lchild;sprintf(tmpstr,"%c",p->data);strcat(str,tmpstr);/*访问结点p*/while(p->rtag==1&&p->rchild!=NULL)/*沿着线索指针遍历后继结点*/{p=p->rchild;sprintf(tmpstr,"%c",p->data);strcat(str,tmpstr);}if(p->rchild==NULL)return;/*遇到最后一个结点，返回*/elsep=p->rchild;/*p有右孩子，跳到右分枝*/}}杨开成数据结构C语言cha共55页，您现在浏览的是第43页!四、线索化二叉树(7)后序线索化算法voidPostOrderThr(THRBTREEp)/*后序遍历的线索化*/{if(p==NULL)return;PostOrderThr(p->lchild);/*建立左子树的线索*/PostOrderThr(p->rchild);/*建立右子树的线索*/

/*建立pre和p之间的前驱后继关系*/if(pre!=NULL&&pre->rchild==NULL){pre->rtag=1;pre->rchild=p; }if(p->lchild==NULL){p->ltag=1;p->lchild=pre; }pre=p;/*将p指向pre*/}杨开成数据结构C语言cha共55页，您现在浏览的是第44页!五、哈夫曼树(2)【问题】在某两地之间的一次网络通讯业务中，发送的字符串是“ACCEEBBBEECCDDDDCDDEEEE”，并且已知这类通讯业务只发送ABCDE这5种字符。问如何对ABCDE这5种字符进行编码，才使得通讯时发送的数据总量最小（成本最低）？【解决方案】方案1：直接发送字符的ASCII码发送的数据量：(1+3+5+6+8)×8=184(比特)。方案2：A：000B：001C：010D：011E：100发送的数据量：(1+3+5+6+8)×3=69(比特)方案3：A：0B：1C：00D：01E：001发送的数据量：1+3+5*2+6*2+8*3=50(比特)方案4：A：000B：001C：01D：10E：11发送的数据量：(1+3)*3+(5+6+8)*2=50(比特)杨开成数据结构C语言cha共55页，您现在浏览的是第45页!五、哈夫曼树(4)typedefstruct{charch;/*结点字符*/intw;/*结点权值*/intlchild,rchild;/*左右孩子，是数组下标*/}HUFFMANNODE,*HUFFMANTREE;初始化存放哈夫曼树的数组HUFFMANTREEInitHuffman(void){/*接受字符串输入，将字符出现的个数作为权值，返回只包含叶子结点的HUFFMANNODE数组，这个数组的首单元存放叶子结点的个数*/charstr[80];intnum;inti,j,k;HUFFMANTREEht;HUFFMANNODEtmpht;printf("pleaseinputthestringforhuffmancoding:\n");gets(str);/*输入字符串*/if(str[0]==0)returnNULL;num=1;/*出现的字符个数，即叶子结点个数*/杨开成数据结构C语言cha共55页，您现在浏览的是第46页!五、哈夫曼树(6)num=0;/*叶子结点总量*/for(i=0;str[i]!=0;i++)/*重新扫描字符串，将计数信息作为结点的权值*/{for(j=0;j<num;j++)/*寻找与字符str[i]相同的叶子结点*/if(ht[j+1].ch==str[i])break;if(j==num)/*未找到，即发现新字符*/{ ht[num+1].ch=str[i];/*新叶子结点，记录字符信息*/ ht[num+1].w++;/*权值增1，最初是0*/ num++;/*叶子结点个数增1*/

}elseht[j+1].w++;/*找到了，相应的叶子结点权值增1*/}杨开成数据结构C语言cha共55页，您现在浏览的是第47页!五、哈夫曼树(8)生成哈夫曼树intCreateHuffman(HUFFMANTREEht){/*在数组ht中生成哈夫曼树，返回哈夫曼树的根结点下标*/inti,num,k,j,root;HUFFMANNODEhfnode;num=ht[0].w;f