资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,5.1,前序,A B E F H I G C J K L D M N O Q P,后序,E H I F G B K L J C N Q O P M D A,层次,A B C D E F G J M H I K L N O P Q,5.2,将二叉树根结点作为有序树林第一棵树的根结点，循环处理,root=,root,-,rchild,，依次将,root,所指结点作为其他树的根结点。,将上述方法施行于各树根结点的左子树。,A,B,D,E,C,F,G,5.3,define MAXN 100,struct,node,int,data;,struct,node*,lchild,*,rchild,;,;,typedef,struct,node,NODE,;,5.3,void,exchange(t,),NODE*t;,NODE*p,*,stackMAXN,;,int,top;,if(t,),stack0=t;,top=1;,while(top,0),t=stack-top;,if(t,-,lchild,!=NULL,|t-,rchild,!=NULL),p=t-,lchild,;,t-,lchild,=t-,rchild,;,t-,rchild,=p;,if(t,-,lchild,!=NULL),stacktop,+=t-,lchild,;,if(t,-,rchild,!=NULL),stacktop,+=t-,rchild,;,5.3,另解：,NODE*,change(t,),NODE*t;,NODE*p;,if(t,=NULL),return(NULL,);,else,p=(NODE*),malloc(sizeof(NODE,);,p-data=t-data;,p-,lchild,=,change(t,-,rchild,);,p-,rchild,=,change(t,-,lchild,);,return(p,);,5.4,void,hinderorder(t,),NODE*t;,NODE*,stackMAXN,*p;,int,flag,top=0;,while(top,0|t!=NULL),while(t,!=NULL),stacktop,+=t;,t=t-,lchild,;,p=NULL;,flag=1;,while(top,0)&(flag),t=stacktop-1;,if(t,-,rchild,!=p),t=t-,rchild,;,flag=0;,else,printf(“%d,“,t-data);,top-;,p=t;,5.5,（,1,）按前序遍历,T,（略）,（,2,）按中序遍历,T,（略）,5.5,（,3,）中序遍历,T,中无左子结点的结点,void,f(t,),NODE*t;,if(t,!=NULL),if(t,-,lchild,=NULL),printf(“%d,”,t-data);,else,f(t,-,lchild,);,f(t,-,rchild,);,5.5,（,4,）求,T,中结点的左子结点本身和它的右下方子结点数的总数的最大值。,int,f1(t),NODE*t;,NODE*p;,int,m,n;,if(t,=NULL),return(0);,n=0;,p=t-,lchild,;,while(p,!=NULL),n+;,p=p-,rchild,;,if(m,=f1(t-,lchild,)n),n=m;,if(m,=f1(t-,rchild,)n),n=m;,return(n,);,5,6,struct,node char data;,struct,node*,lchild,*,rchild,;,typedef,struct,node,NODE,;,NODE*,binatree(a,b,n,),char a,b;,int,n;,NODE*root,*p,*q,*,stackmaxn,;,int,top,i,j,smaxn,;,if(n,=0),return(NULL,);,top=0;,for(i,=0;idata=,ai,;,p-,lchild,=p-,rchild,=NULL;,if(n,=1),return(p,);,else,if(i,=0),root=p;,j=0;,while(bj,!=,ai,),j+;,if(top,0),if(j,lchild,=p;,else,while(j,stop-1)&(top0),q=stack-top;,q-,rchild,=p;,stop,=j;,stacktop,+=p;,return(root,);,5,8,int,fully_tree(t,),node*t;,if(t,-,lchild,=,NULL&t,-,rchild,=NULL),return(1);,if(t,-,lchild,!=,NULL&t,-,rchild,!=NULL),if(fully_tree(t,-,lchild,),return(fully_tree(t,-,rchild,);,return(0);,5.10,#define MAXN 100,typedef,struct,rnode,char data;,char,ltag,;,int,rchild,;,RNODE;,typedef,struct,node char data;,struct,node*,lchild,*,rchild,;,NODE;,RNODE,treeMAXN,;,NODE *,transfer(tree,n,),RNODE tree;,int,n;,NODE*,stackMAXN,*root,*p,*q;,int,top,i;,if(n,=0),return(NULL,);,root=(NODE*),malloc(sizeof(NODE,);,p=root;,top=0;,for(i,=0;idata=,treei.data,;,if(treei.rtag,!=-1),stacktop,+=p;,else,p-,rchild,=NULL;,q=(NODE*),malloc(sizeof(NODE,);,if(treei.ltag,=0),p-,lchild,=q;,else,p-,lchild,=NULL;,p=stack-top;,p-,rchild,=q;,p=q;,p-data=treen-1.data;,p-,lchild,=NULL;,p-,rchild,=NULL;,return(root,);,5.11,#define MAXN 100,struct,node char data;,int,ltag,rtag,;,;,typedef,struct,node,NODE,;,NODE,sMAXN,;,5.11,int,search_parents(s,n,a,),NODE s;,int,n;,char a;,int,i,j,m;,for(i,=0;i=0;j-),if(sj.ltag,=1),m+;,if(sj.rtag,=0),m-;,if(m,=0),return(j,);,5.12,#include“,stdio.h,”,struct,node char data;,struct,node*,lchild,*,rchild,;,int,ltag,rtag,;,;,typedef,struct,node,NODE,;,NODE*root;,5.12,void,preorder(root,),NODE*root;,NODE*p;,if(root,=NULL),return;,p=root;,while(1),printf(“%c”,p,-data);,if(p,-,ltag,=0,&p-,lchild,!=NULL),p=p-,lchild,;,else,while(p,-,rtag,=1),p=p-,rchild,;,if(p,-,rtag,=0,&p-,rchild,=NULL),break;,p=p-,rchild,;,
展开阅读全文