C语言C++实现二叉树构造与查找删除节点.doc

# include # include # include typedef int Etype;typedef struct BiTNode Etype data; struct BiTNode *lch,*rch; BiTNode,*pointer;BiTNode *creat_bt1();BiTNode *creat_bt2();void inorder(BiTNode *p);void numb(BiTNode *p);BiTNode *t; int n,n0,n1,n2;pointer point=NULL;int searchbst(pointer p,Etype key,pointer parent,pointer &q);int insertbst(pointer &p,Etype key);void deletedata(pointer &p);int deletebst(pointer &p,Etype key);void main() system (color 6e );char ch; int k;int cp,num,sk; do printf(nnn); printf(nn 1. 建立二叉排序树并中序遍历); printf(nn 2. 二叉链表建立二叉树); printf(nn 3. 顺序数组建立二叉树); printf(nn 4. 计算树中结点个数); printf(nn 5. 中序遍历二叉树); printf(nn 6. 二叉排序树查询删除节点); printf(nn 7. 结束程序运行); printf(n=); printf(n 请输入您的选择 (1,2,3,4,5,6,7); scanf(%d,&k); switch(k) case 1:printf(请输入结点的个数:); scanf(%d,&num); for(cp=0;cp=1 & kdata)q=p;return 1;else if(keydata)return searchbst(p-lch,key,p,q);else return searchbst(p-rch,key,p,q);int insertbst(pointer &p,Etype key)pointer q,s;if(!searchbst(p,key,NULL,q) s=(pointer)malloc(sizeof(BiTNode); s-data=key; s-lch=s-rch=NULL; if(!q)p=s; else if(s-datadata)q-lch=s; else q-rch=s; printf(插入成功!n); return 1;else printf(插入失败!n);return 0;int deletebst(pointer &p,Etype key)if(!p)return 0;else if(p-data=key)deletedata(p);return 1;else if(keydata) return deletebst(p-lch,key);else return deletebst(p-rch,key);void deletedata(pointer &p)pointer q,s; if(!p-rch) q=p;p=p-lch;free(q); printf(查找成功，已删除该结点!n); return;else if(!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; else q-lch=s-lch; delete s; printf(查找成功，已删除该结点!n); return;printf(无此结点!n);BiTNode *creat_bt1()/利用数组建立 BiTNode *t,*p,*v20; int i,j; Etype e; 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; vi=p; if (i=1) t=p; else j=i/2; if(i%2=0) vj-lch=p; else vj-rch=p ; printf(n i,data=?); scanf(%d,%d,&i,&e); return(t); /模仿线序遍历递归建立二叉树 BiTNode *creat_bt2() BiTNode *t; int e; printf(n data=); 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); void inorder(BiTNode *p) if (p) inorder(p-lch); printf( %3d,p-data); inorder(p-rch); /利用中序递归遍历二叉树的方法，计算树中结点个数 void numb(BiTNode *p) if (p) numb(p-lch); printf(%3d,p-data); n+; if(p-lch=NULL &