二叉树节点的插入和查找.doc

《二叉树节点的插入和查找.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二叉树节点的插入和查找#include#includetypedefintelemtype;typedefstructNode{elemtypedata;structNode*Lchild;structNode*Rchild;}TreeNode;typedefTreeNode*bt;Search_data(TreeNode*t,TreeNode**p,TreeNode**q,elemtypex)//查找函数{intflag=0;*p=NULL;*q=t;while(*q){

2、if(x>(*q)->data){*p=*q;*q=(*q)->Rchild;}else{if(x<(*q)->data){*p=*q;*q=(*q)->Lchild;}else{flag=1;break;}}}returnflag;}InsertNode(TreeNode**t,elemtypex)//插入函数{intflag=0;TreeNode*q,*s;TreeNode*p=*t;if(!Search_data(*t,&p,&q,x)){s=(TreeNode*)malloc(sizeof(TreeNo

3、de));s->data=x;s->Lchild=NULL;s->Rchild=NULL;flag=1;if(!p)*t=s;else{if(x>p->data)p->Rchild=s;elsep->Lchild=s;}}returnflag;}DeleteNode(TreeNode**t,elemtypex)//删除函数{intflag=0;TreeNode*q,*s,**f;TreeNode*p=*t;if(Search_data(*t,&p,&q,x)){flag=1;if(p==q)f=&(*t);el

4、se{f=&(p->Lchild);if(x>p->data)f=&(p->Rchild);}if(!q->Rchild)*f=q->Lchild;else{if(!q->Lchild)*f=q->Rchild;else{p=q->Rchild;s=p;while(p->Lchild){s=p;p=q->Lchild;}*f=p;p->Lchild=q->Lchild;if(s!=p){s->Lchild=p->Rchild;p->Rchild=q->Rchild;}}}free(q);}returnflag;

5、}voidvisit(btt){printf("%c",t->data);}TreeNode*creat_Tree(){charch;btt;ch=getchar();if(ch=='')return(NULL);else{t=(TreeNode*)malloc(sizeof(TreeNode));t->data=ch;t->Lchild=creat_Tree();t->Rchild=creat_Tree();printf("%x",&t);return(t);}}voidmid_oderTree(btt)

6、{if(t!=NULL){mid_oderTree(t->Lchild);visit(t);mid_oderTree(t->Rchild);}}intcount_leafTree(btt){inti;if(t==NULL)return0;elseif(t->Lchild==NULL&&t->Rchild==NULL)i=1;elsei=count_leafTree(t->Lchild)+count_leafTree(t->Rchild);returni;}voidmain(){TreeNode*t,*p,*q;

7、elemtypex;x='M';printf("creatTree:");//二叉树在遍历最后一个节点之后，遇到结束符结束建立树。t=creat_Tree();printf("中根遍历树:");mid_oderTree(t);printf("中根序插入%c成功输出（是1否0）:%d",x,InsertNode(&t,x));printf("插入%c后的查找成功输出（是1否0）:%d",x,Search_data(t,&p,&q,x));printf("插入后的中根遍历树:");mid_o

8、derTree(t);printf("删除%c成功输出（是1否0）:%d",x,DeleteNode(&t,x));printf("删除后的中根遍历树:");mid_oderTree(t);printf("求树的叶子数:%d",count_leafTree(t));}