C语言C实现二叉树构造与查找删除节点.docx
- 文档编号:2938785
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:8
- 大小:15.59KB
C语言C实现二叉树构造与查找删除节点.docx
《C语言C实现二叉树构造与查找删除节点.docx》由会员分享,可在线阅读,更多相关《C语言C实现二叉树构造与查找删除节点.docx(8页珍藏版)》请在冰点文库上搜索。
C语言C实现二叉树构造与查找删除节点
#include
#include
#include
typedefintEtype;
typedefstructBiTNode
{Etypedata;
structBiTNode*lch,*rch;
}BiTNode,*pointer;
BiTNode*creat_bt1();
BiTNode*creat_bt2();
voidinorder(BiTNode*p);
voidnumb(BiTNode*p);
BiTNode*t;intn,n0,n1,n2;
pointerpoint=NULL;
intsearchbst(pointerp,Etypekey,pointerparent,pointer&q);
intinsertbst(pointer&p,Etypekey);
voiddeletedata(pointer&p);
intdeletebst(pointer&p,Etypekey);
voidmain()
{
system("color6e");
charch;intk;
intcp,num,sk;
do{printf("\n\n\n");
printf("\n\n1.建立二叉排序树并中序遍历");
printf("\n\n2.二叉链表建立二叉树");
printf("\n\n3.顺序数组建立二叉树");
printf("\n\n4.计算树中结点个数");
printf("\n\n5.中序遍历二叉树");
printf("\n\n6.二叉排序树查询删除节点");
printf("\n\n7.结束程序运行");
printf("\n======================================");
printf("\n请输入您的选择(1,2,3,4,5,6,7)");scanf("%d",&k);
switch(k)
{case1:
printf("请输入结点的个数:
");
scanf("%d",&num);
for(cp=0;cp { printf("请输入第%d个数: ",cp+1); scanf("%d",&sk); insertbst(point,sk); } printf("\n中序遍历结果是: \n"); inorder(point); break; case2: t=creat_bt2();system("cls");break; case3: {t=creat_bt1();system("cls");break; case4: {n=0;n0=0;n1=0;n2=0;/*全局变量置0*/ numb(t); printf("\n二叉树结点总数n=%d",n); printf("\n二叉树叶子结点数n0=%d",n0); printf("\n度为1的结点数n1=%d",n1); printf("\n度为2的结点数n2=%d",n2); printf("\n\n敲回车键,继续。 ");ch=getch(); }system("cls");break; case5: printf("\n\n中序遍历结果是: ");inorder(t); printf("\n\n敲回车键,继续。 ");ch=getch(); }system("cls");break; case6: printf("请输入查询的节点: "); scanf("%d",&cp); deletebst(point,cp); printf("\n中序遍历结果是: "); inorder(point); break; case7: exit(0); } }while(k>=1&&k<7); printf("\n再见! "); printf("\n敲回车键,返回。 ");ch=getch(); } intsearchbst(pointerp,Etypekey,pointerparent,pointer&q) { if(! p){q=parent;return0;} elseif(key==p->data){q=p;return1;} elseif(key else{returnsearchbst(p->rch,key,p,q);} } intinsertbst(pointer&p,Etypekey) { pointerq,s; if(! searchbst(p,key,NULL,q)) s=(pointer)malloc(sizeof(BiTNode)); s->data=key; s->lch=s->rch=NULL; if(! q)p=s; elseif(s->data elseq->rch=s; printf("插入成功! \n"); return1; } else{printf("插入失败! \n");return0;} } intdeletebst(pointer&p,Etypekey) { if(! p){return0;} elseif(p->data==key){deletedata(p);return1;} elseif(key elsereturndeletebst(p->rch,key); } voiddeletedata(pointer&p) { pointerq,s; if(! p->rch) { q=p;p=p->lch;free(q); printf("查找成功,已删除该结点! \n"); return; } elseif(! p->lch) { q=p;p=p->rch;free(q); printf("查找成功,已删除该结点! \n"); return; } else { q=p;s=p->lch; while(s->rch){q=s;s=s->rch;} p->data=s->data; if(q! =p)q->rch=s->lch; elseq->lch=s->lch; deletes; printf("查找成功,已删除该结点! \n"); return; } printf("无此结点! \n"); } BiTNode*creat_bt1()//利用数组建立 {BiTNode*t,*p,*v[20];inti,j;Etypee; printf("\n输入结点的序号i,结点的数据? ");scanf("%d,%d",&i,&e); while(i! =0&&e! =0) {p=(BiTNode*)malloc(sizeof(BiTNode)); p->data=e;p->lch=NULL;p->rch=NULL; v[i]=p; if(i==1)t=p; else{j=i/2; if(i%2==0)v[j]->lch=p; elsev[j]->rch=p ; } printf("\ni,data=? ");scanf("%d,%d",&i,&e); } return(t); } //模仿线序遍历递归建立二叉树 BiTNode*creat_bt2() {BiTNode*t;inte; printf("\ndata=");scanf("%d",&e); if(e==0)t=NULL; else{t=(BiTNode*)malloc(sizeof(BiTNode)); t->data=e; printf("输入其左孩子无左孩子输入0"); t->lch=creat_bt2(); printf("输入最下层未知左孩子结点的左孩子无左孩子弟输入0"); t->rch=creat_bt2(); } return(t); } voidinorder(BiTNode*p) { if(p){inorder(p->lch); printf("%3d",p->data); inorder(p->rch); } } //利用中序递归遍历二叉树的方法,计算树中结点个数 voidnumb(BiTNode*p) {if(p){numb(p->lch); {printf("%3d",p->data); n++; if(p->lch==NULL&&p->rch==NULL)n0++; if((p->lch==NULL&&p->rch! =NULL)|| (p->lch! =NULL&&p->rch==NULL))n1++; if(p->lch! =NULL&&p->rch! =NULL)n2++; } numb(p->rch); } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 实现 二叉 构造 查找 删除 节点