二叉树节点的插入和查找#include #include typedef int elemtype;typedef struct Node{ elemtype data; struct Node *Lchild; struct Node *Rchild;}TreeNode;typedef TreeNode *bt;Search_data(TreeNode *t,TreeNode **p,TreeNode **q, elemtype x) //查找函数{ int flag=0; *p=NULL; *q=t; while(*q) { if (x>(*q)->data) { *p=*q; *q=(*q)->Rchild; } else{ if (x<(*q)->data) { *p=*q; *q=(*q)->Lchild; } else{ flag=1; break; } } } return flag;} InsertNode(TreeNode **t,elemtype x) //插入函数{ int flag=0; TreeNode *q,*s; TreeNode *p=*t; if (!Search_data(*t,&p,&q,x)) { s=(TreeNode *)malloc(sizeof(TreeNode)); s->data=x; s->Lchild=NULL; s->Rchild=NULL; flag=1; if(!p) *t=s; else{ if(x>p->data) p->Rchild=s; else p->Lchild=s; } } return flag;}DeleteNode(TreeNode **t,elemtype x) //删除函数{ int flag=0; TreeNode *q,*s,**f; TreeNode *p=*t; if (Search_data(*t,&p,&q,x)) { flag=1; if(p==q) f=&(*t); else { 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); } return flag;}void visit(bt t){ printf("%c",t->data);}TreeNode *creat_Tree() { char ch; bt t; 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\n",&t); return (t); }}void mid_oderTree(bt t){ if (t!=NULL) { mid_oderTree(t->Lchild); visit(t); mid_oderTree(t->Rchild); }}int count_leafTree(bt t){ int i; if(t==NULL) return 0; else if(t->Lchild==NULL&&t->Rchild==NULL) i=1; else i=count_leafTree(t->Lchild)+count_leafTree(t->Rchild); return i;}void main(){ TreeNode *t,*p,*q; elemtype x; x='M'; printf("creat Tree:\n"); //二叉树在遍历最后一个节点之后，遇到结束符结束建立树。 t=creat_Tree(); printf("中根遍历树:\n"); mid_oderTree(t); printf("\n 中 根 序 插 入 %c 成 功 输 出 （ 是 1 否 0 ） :%d\n",x,InsertNode(&t,x)); printf(" 插 入 %c 后 的 查 找 成 功 输 出 （ 是 1 否 0 ） :%d\n",x,Search_data(t,&p,&q, x)); printf("插入后的中根遍历树:\n"); mid_oderTree(t); printf("\n 删除%c 成功输出（是 1 否 0）:%d \n",x,DeleteNode(&t,x)); printf("删除后的中根遍历树:\n"); mid_oderTree(t); printf("\n 求树的叶子数:%d \n",count_leafTree(t));}
