二叉树的基本操作完整版,包含二叉树的所有操作,凡是你想要的都在里面--数据结构版

#include "stdio.h"

#include "stdlib.h"

#include "string.h"

#include "math.h"

typedef char TElemType; //定义结点数据为字符型

typedef int Status; //定义函数类型为int型

#define ERROR 0

#define OK 1

typedef struct BiTNode{ //定义结构体

TElemType data; //结点数值 struct BiTNode *lchild; //左孩子指针 struct BiTNode *rchild; //右孩子指针 struct BiTNode *next; //下一结点指针

}BiTNode, *BiTree;

Status NumJudge(char ch[20]){

//限制输入数据必须为大于零的整形

char ch1[20]; int num; while(1){ } scanf("%s",ch); num=atoi(ch); //将字符串转换为整型 itoa(num,ch1,10); //将整型转换为字符串型 if(strcmp(ch,ch1)==0&&num>0)break; else{printf("请输入一个大于零的整数: ");}

return num;

}//NumJudge

Status InitBiTree(BiTree &T){

//构造空二叉树T

if(!(T=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR); //若申请空间失败则退出 T->next=NULL; printf("\n\t空二叉树构建成功!\n\n"); return OK;

}//InitBiTree

Status DestroyTree(BiTree &T,BiTree t){

//销毁二叉树

if(T){ } free(T);T=NULL; printf("\t二叉树销毁成功!\n");

if(t){

DestroyTree(T,t->lchild);

DestroyTree(T,t->rchild);

free(t);

}

return OK;

}//DestroyTree

Status ClearBiTree(BiTree &T,int sum,int &i){

//清空二叉树

if(T){

ClearBiTree(T->lchild,sum,i);

ClearBiTree(T->rchild,sum,i); free(T); i++; } if(i==sum){printf("\t二叉树清空成功!\n");T=NULL;}

return OK;

}//ClearBiTree

Status CreateBiTree(BiTree &T,int i,int j,TElemType ch){

//按先序次序输入二叉树中结点的值(一个字符),空格字符表示该结点为空

//构造二叉链表示的二叉树T

TElemType ch1; int k; char str[20]; if(i==0){printf("\n 按先序顺序建立二叉树:请按提示输入相应的数据(一个字符)，若提示结点数值为空，\n 请输入空格\n\n");

printf("%5s请输入树根: "," ");}

if(i!=0&&i>=j){printf("%5s请输入%c的左孩子: "," ",ch);}

if(j!=0&&j>i){printf("%5s请输入%c的右孩子: "," ",ch);}

while(1){ //限制输入数据必须为字符型,否则重新输入

fflush(stdin); for(k=0;k<20;k++){ str[k]=getchar(); if(str[k]=='\n')break; } if(k==0)printf("%5s请输入一个字符后再按Enter键: "," "); if(k==1)break; if(k>1)printf("%5s您只能输入一个字符: "," "); } ch1=str[0]; //获取输入的准确字符型数据 if(ch1==' '){T=NULL;return ERROR;} //输入空格则为根结点为空 if(ch1!=' '){

if(!(T=(BiTree)malloc(sizeof(BiTNode)))) exit(ERROR); T->data=ch1; //生成根结点 ch=T->data; i++; CreateBiTree(T->lchild,i,j,ch); //构造左子树 j=i;j++; CreateBiTree(T->rchild,i,j,ch); //构造右子树 } i=0;j=0; return OK;

}//CreateBitree

Status TreeDepth(BiTree T,int l,int &h){

//若二叉树存在,返回其深度

if(T){ l=l+1; } return h; if(l>h)h=l; TreeDepth(T->lchild,l,h); TreeDepth(T->rchild,l,h);

}//TreeDepth

Status GetRootElem(BiTree T){

//获取根结点值

printf("该二叉树的根结点值为: %c\n\n",T->data); return OK;

}//GetRootElem

Status SaveElem(BiTree T,BiTree *Q,int i){

//根据完全二叉树中，若本节点位置序号为i,则其左孩子结点为2i,右孩子为2i+1的方法 //保存二叉树的有效结点至指针数组Q特定的位置

if(T){ Q[i]=T;

SaveElem(T->lchild,Q,2*i);

SaveElem(T->rchild,Q,2*i+1);

}

return OK;

}//SaveElem

Status Lev_Traverse(BiTree T,int h){

//按层次从上到下,每层从左到右的顺序显示树状二叉树

if(T==NULL){printf("\n\t\t二叉树目前为空树\n\n");return ERROR;}

BiTree *Q;

if(!(Q=(BiTree *)malloc(int(pow(2,h)+1) * sizeof(BiTNode))))exit(ERROR);

int i,j,n=1,k=h;

for(i=1;i<=int(pow(2,h)+1);i++){

Q[i]=NULL;}

SaveElem(T,Q,n); //将目前有效结点按照满二叉树的序号存储

printf(" 提示:规定下图中的有效结点的位置序号从1开始按从上到下,从左到右的顺序依次递增\n");

for(i=1;i<=(pow(2,h)+1);i++){ //树形显示二叉树 if(int(pow(2,h))%i==0){ } } printf("\n"); printf("\t\t"); for(j=0;j<pow(2,k-1)-1;j++){ } k--; printf(" "); if(Q[i])printf("%c",Q[i]->data); if(!Q[i])printf(" "); for(j=0;j<pow(2,k+1)-1;j++){ printf(" ");}

printf("\n\n");

i=0;j=0;

return OK;

}//Lev_Traverse

Status FirstPrint(BiTree T,int i){

//按先序次序(递归)访问二叉树

if(i==0)printf("\n先序(递归)遍历结果如下:\n");

if(T){ i++;printf("%-5c",T->data); //访问T } i=0; return OK; FirstPrint(T->lchild,i); //递归遍历左子树 FirstPrint(T->rchild,i); //递归遍历右子树

}//FirstPrintBiTree

Status MiddlePrint(BiTree T,int i){

//按中序次序(递归)访问二叉树

if(i==0)printf("\n中序(递归)遍历结果如下:\n"); if(T){ i++;

} i=0; MiddlePrint(T->lchild,i); //递归遍历左子树 printf("%-5c",T->data); //访问T MiddlePrint(T->rchild,i); //递归遍历右子树 return OK;

}//MiddlePrint

Status LastPrint(BiTree T,int i){

//按后序次序(递归)访问二叉树

Status PreOrderTraverse(BiTree T){

//按先序(非递归)遍历二叉树T

BiTree p,S,q; int flag=0; if(!(S=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR); S->next=NULL; //建立空栈S if(i==0)printf("\n后序(递归)遍历结果如下:\n"); if(T){ i++; LastPrint(T->lchild,i); //递归遍历左子树 LastPrint(T->rchild,i); //递归遍历右子树 printf("%-5c",T->data); //访问T } i=0; return OK; }//LastPrint

p=T;

printf("\n先序(非递归)遍历结果如下:\n");

while(1){ while(1){ //遍历存储并访问左子树直到根结点左孩子不存在 printf("%-5c",p->data); q=S->next;S->next=p;p->next=q; //当前结点进栈 if(p->lchild)p=p->lchild; else{break;} } while(1){ //栈顶指针出栈,如果当前栈顶指针的右孩子存在则跳出循环

p=S->next;S->next=p->next;

if(!S->next&&!p->rchild){flag=1;break;} //如果栈空并且当前结点右孩子不存在则遍历结束

if(p->rchild){p=p->rchild;break;} } if(flag==1)break;

}

printf("\n\n");

return OK;

}//PreOrderTraverse

Status InOrderTraverse(BiTree T){

// 中序遍历(非递归)二叉树T

BiTree p,S,q; if(!(S=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR); S->next=NULL; //建立空栈S

p=T;

printf("\n中序(非递归)遍历结果如下:\n");

while(p||S->next){ if(p){q=S->next;S->next=p;p->next=q;p=p->lchild;} //左孩子进栈

else{

p=S->next;S->next=p->next;

if(p)printf("%-5c",p->data); //输出栈中元素

else{return ERROR;}

p=p->rchild;

} }

printf("\n\n");

return OK;

}//InOrderTraverse

Status PostOrderTraverse(BiTree T){

//后序遍历(非递归)二叉树T

BiTree p,S,q; if(!(S=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR); S->next=NULL; //建立空栈S

p=T;

printf("\n后序(非递归)遍历结果如下:\n");

while(1){ while(1){ //遍历左子树,若当前结点左右孩子都不存在则跳出 } while(S->next){ p=S->next;S->next=p->next; //栈顶指针出栈并访问 printf("%-5c",p->data); q=S->next;S->next=p;p->next=q; //当前结点进栈 if(p->lchild)p=p->lchild; else{ } if(p->rchild)p=p->rchild; else{break;}

if(!S->next)break; //若栈空则跳出

if(p==S->next->rchild)p=S->next; //若当前结点为栈顶指针的右孩子,则继

else{

if(S->next->rchild){ //栈顶指针右孩存在,指针移至栈顶指针的

} } p=S->next->rchild;break; 续出栈

} 右孩子后跳出循环 } if(!S->next)break; //若栈空则跳出循环 printf("\n\n"); return OK;

}//PostOrderTraverse

Status GetElemSum(BiTree T){

//计算二叉树中总结点的个数

BiTree p,*q; int l=0,h=0; if(!(q=(BiTree *)malloc(int(pow(2,TreeDepth(T,l,h))+1) * sizeof(BiTNode))))exit(ERROR); int head=1,tail=2; q[1]=T; while(head<tail){ p=q[head++];

if(p->lchild)q[tail++]=p->lchild;

if(p->rchild)q[tail++]=p->rchild;

}

return head-1;

}//GetElemSum

Status LevelOrderPrint(BiTree T){

//二叉树T存在,层序遍历二叉树

//将二叉树中的结点按从上到下,从左到右的顺序存至指针数组q,然后按次序输出

BiTree p,*q; if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR); int head=1,tail=2;

q[1]=T;

printf("\n层序(非递归)遍历结果如下:\n");

while(head<tail){ p=q[head++]; printf("%-5c",p->data); if(p->lchild)q[tail++]=p->lchild; if(p->rchild)q[tail++]=p->rchild;

}

printf("\n\n");

return OK;

}//LevelOrderPrint

Status GetElemNum(BiTree T,TElemType e){

//查找元素e在二叉树T中的个数及位置

int j,i=0,num=0,*a;

BiTree p,*q; if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR); if(!(a=(int *)malloc(GetElemSum(T) * sizeof(int))))exit(ERROR); int head=1,tail=2; q[1]=T; while(head<tail){ p=q[head++]; if(p->data==e){num++; a[i]=head-1;i++;} if(p->lchild)q[tail++]=p->lchild; if(p->rchild)q[tail++]=p->rchild; } printf("\n元素%c在二叉树中的个数为: %d\n",e,num); printf("元素%c在二叉树中的位置序号为:",e); for(j=0;j<i;j++){ printf("%-4d",a[j]); } printf("\n");

return num;

}//GetElemNum

Status GetLeafNum(BiTree T){

//计算二叉树T中叶子个数

BiTree p,*q;

if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR); int num=0,head=1,tail=2; q[1]=T; while(head<tail){ p=q[head++]; if(!p->lchild&&!p->rchild)num++; if(p->lchild)q[tail++]=p->lchild;

if(p->rchild)q[tail++]=p->rchild;

}

return num;

}//GetLeafNum

Status LBrother(BiTree T,int sum){

//求第num个结点的左兄弟

BiTree p,*q; if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR); int i,num,head=1,tail=2; char str[20]; q[1]=T; printf("请输入要查找的位置序号: "); num=NumJudge(str); if(num>sum){printf("您输入的位置序号大于有效结点个数\n");return ERROR;}; while(head<tail){ p=q[head++];

if(num==tail-2)break;

if(p->lchild)q[tail++]=p->lchild;

if(p->rchild)q[tail++]=p->rchild;

}

if(num==1)printf("位置%d的%c没有左兄弟\n",num,q[num]->data);

else{

} for(i=1;i<num;i++){ if(q[i]->lchild==q[num]||q[i]->rchild==q[num])break; } if(q[i]->lchild==q[num])printf("位置%d的%c没有左兄弟\n",num,q[num]->data); if(q[i]->rchild==q[num])printf("位置%d的%c的左兄弟为: %c\n",num,q[num]->data,q[i]->lchild->data);

return OK;

}//LBrother

Status RBrother(BiTree T,int sum){

//求第num个结点的右兄弟

BiTree p,*q; if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR); int i,num,head=1,tail=2; char str[20]; q[1]=T; printf("请输入要查找的位置序号: "); num=NumJudge(str); if(num>sum){printf("您输入的位置序号大于有效结点个数\n");return ERROR;}; while(head<tail){

p=q[head++];

if(num==tail-2)break;

if(p->lchild)q[tail++]=p->lchild;

if(p->rchild)q[tail++]=p->rchild;

} if(num==1)printf("位置%d的%c没有右兄弟\n",num,q[num]->data);

for(i=1;i<num;i++){

if(q[i]->lchild==q[num]||q[i]->rchild==q[num])break; else{

}

if(!q[i]->rchild||q[i]->rchild==q[num])printf("位置%d的%c没有右兄弟\n",num,q[num]->data);

if(q[i]->rchild&&q[i]->lchild==q[num])printf("位置%d的%c的右兄弟为: %c\n",num,q[num]->data,q[i]->rchild->data);

}

return OK;

}//RBrother

Status Lchild(BiTree T,int sum){

//求第num个结点的左孩子

BiTree p,*q; if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR); int num,head=1,tail=2; char str[20]; q[1]=T; printf("请输入要查找的位置序号: "); num=NumJudge(str); if(num>sum){printf("您输入的位置序号大于有效结点个数\n");return ERROR;} while(head<tail){ p=q[head++];

if(num==tail-2)break;

if(p->lchild)q[tail++]=p->lchild;

if(p->rchild)q[tail++]=p->rchild;

} if(q[num]->lchild)printf("位置%d的%c的左孩子为: %c\n",num,q[num]->data,q[num]->lchild->data);

else{printf("位置%d的%c的左孩子不存在\n",num,q[num]->data);}

return OK;

}//Lchild

Status Rchild(BiTree T,int sum){

//求第num个结点的右孩子

BiTree p,*q; if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR); int num,head=1,tail=2; char str[20]; q[1]=T;

printf("请输入要查找的位置序号: "); num=NumJudge(str);

if(num>sum){printf("您输入的位置序号大于有效结点个数\n");return ERROR;} while(head<tail){

p=q[head++];

if(num==tail-2)break;

if(p->lchild)q[tail++]=p->lchild;

if(p->rchild)q[tail++]=p->rchild;

}

if(q[num]->rchild)printf("位置%d的%c的右孩为: %c\n",num,q[num]->data,q[num]->rchild->data);

else{printf("位置%d的%c的右孩子不存在\n",num,q[num]->data);}

return OK;

}//Rchild

Status Partents(BiTree T,int sum){

//求第num个结点的双亲

BiTree p,*q;

if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);

int i,num,head=1,tail=2;

char str[20];

q[1]=T;

printf("请输入要查找的位置序号: ");

num=NumJudge(str);

if(num>sum){printf("您输入的位置序号大于有效结点个数\n");return ERROR;} while(head<tail){

p=q[head++];

if(num==tail-2)break;

if(p->lchild)q[tail++]=p->lchild;

if(p->rchild)q[tail++]=p->rchild;

}

if(num==1)printf("位置%d的%c没有双亲\n",num,q[num]->data);

else{

for(i=1;i<num;i++){

if(q[i]->lchild==q[num]||q[i]->rchild==q[num])break;

}

printf("位置%d的%c的双亲为: %c\n",num,q[num]->data,q[i]->data); }

return OK;

}//Partents

Status TreeDelete(BiTree &T,int sum){

//删除第num个结点

BiTree p,p1,*q; 子

int i,num,head=1,tail=2,a=0,b=0; char str[20]; q[1]=T; printf("请输入要删除结点的位置序号: "); num=NumJudge(str); if(num>sum){printf("\n您输入的位置序号大于有效结点个数\n\n");return ERROR;}

if(num==1){printf("\t对不起,您不能删除根结点,若想删除根结点,请选择销毁树\n\n");return ERROR;};

while(head<tail){ p=q[head++]; if(num==tail-2)break;

if(p->lchild)q[tail++]=p->lchild;

if(p->rchild)q[tail++]=p->rchild;

} for(i=1;i<num;i++){

if(q[i]->lchild==q[num]||q[i]->rchild==q[num])break;

}

printf("\n您删除了如下子树:\n\n");

Lev_Traverse(q[num],TreeDepth(q[num],a,b)); if(q[i]->lchild==q[num])q[i]->lchild=NULL; if(q[i]->rchild==q[num])q[i]->rchild=NULL; p1=NULL; DestroyTree(p1,q[num]); printf("\n删除结点成功\n");

return OK;

}//TreeDelete

Status TreeInsert(BiTree &T,int sum){

//在第num个生成子树

BiTree p,p1,*q; if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR); int num,head=1,tail=2,a=0,b=0; char ch=' ',str[20]; q[1]=T; printf("请输入要插入结点的位置序号: "); num=NumJudge(str); if(num>sum){printf("\n您输入的位置序号大于有效结点个数\n\n");return ERROR;} while(head<tail){ p=q[head++]; if(num==tail-2)break;

if(p->lchild)q[tail++]=p->lchild;

if(p->rchild)q[tail++]=p->rchild;

}

printf("您输入的位置序号已有左子树和右子树,无法再此位置插入\n\n");return ERROR;}

if(q[num]->lchild&&!q[num]->rchild){

printf("位置%d的%c处只能生成右子树,确定插入/退出(y/n): ",num,q[num]->data);

while(1){ if(strcmp(str,"y")==0||strcmp(str,"n")==0)break; else{printf("选择错误,请重新输入: ");} } if(strcmp(str,"y")==0){ printf("请输入插入子树的信息: \n"); CreateBiTree(p1,a,b,ch); if(p1){q[num]->rchild=p1;} scanf("%s",str); } if(strcmp(str,"n")==0)return ERROR; } if(!q[num]->lchild&&q[num]->rchild){ printf("位置%d的%c处只能生成左子树,确定插入/退出(y/n): ",num,q[num]->data); while(1){ if(strcmp(str,"y")==0||strcmp(str,"n")==0)break; else{printf("选择错误,请重新输入: ");} } if(strcmp(str,"y")==0){ printf("请输入插入子树的信息: \n"); CreateBiTree(p1,a,b,ch); if(p1){q[num]->lchild=p1;} } if(strcmp(str,"n")==0)return ERROR; scanf("%s",str);

}

if(!q[num]->lchild&&!q[num]->rchild){

printf("请输入插入子树的信息: \n");

CreateBiTree(p1,a,b,ch);

printf("\t\t你想把新建的树作为位置%d的%c处的: \n",num,q[num]->data); printf("\t\t [1]左子树 [2]右子树\n");

printf("\n\t\t请输入你的选择: ");

while(1){

scanf("%s",str);

if(strcmp(str,"1")==0||strcmp(str,"2")==0)break; else{printf("选择错误,请重新输入: ");} } if(strcmp(str,"1")==0){ if(p1){q[num]->lchild=p1;}

}

if(strcmp(str,"2")==0){

if(p1){q[num]->rchild=p1;}

}

}

printf("插入子树成功\n");

return OK;

}//TreeInsert

Status Modify(BiTree T,int sum,int &n){

//修改二叉树第num个结点的值

BiTree p,*q; if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR); int k,num,head=1,tail=2; char str[20]; q[1]=T;n=0; printf("请输入要修改结点的位置序号: "); num=NumJudge(str); if(num>sum){printf("\n您输入的位置序号大于有效结点个数\n\n");return ERROR;} while(head<tail){ p=q[head++];

if(num==tail-2)break;

if(p->lchild)q[tail++]=p->lchild;

if(p->rchild)q[tail++]=p->rchild;

}

printf("%5s请输入新的结点值: "," ");

while(1){ } q[num]->data=str[0]; printf("\n 修改成功\n"); n=1; return OK; fflush(stdin); for(k=0;k<20;k++){ str[k]=getchar(); if(str[k]=='\n')break; } if(k==0)printf("%5s请输入一个字符后再按Enter键: "," "); if(k==1)break; if(k>1)printf("%5s您只能输入一个字符: "," ");

}//Modify

int MainMenu(){ //主菜单函数

system("cls");

char str[20]; printf("\n\t\t\t*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=**=*=*=*"); printf("\n\t\t\t 计本102 卢荣盼 1018014052"); printf("\n\t\t\t*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=**=*=*=*"); printf("\n\t\t\t [1]建立空树\n"); printf("\n\t\t\t [2]构造二叉树\n"); printf("\n\t\t\t [3]显示树状二叉树\n"); printf("\n\t\t\t [4]遍历二叉树 ->>进入子菜单\n"); printf("\n\t\t\t [5]查看二叉树信息 ->>进入子菜单\n"); printf("\n\t\t\t [6]对二叉树进行操作 ->>进入子菜单\n"); printf("\n\t\t\t [0]退出程序"); printf("\n\t\t\t*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=**=*=*=*"); printf("\n\t\t\t请输入你的选择: "); while(1){ scanf("%s",str); if(strcmp(str,"0")==0||strcmp(str,"1")==0||strcmp(str,"2")==0||strcmp(str,"3")==0 ||strcmp(str,"4")==0||strcmp(str,"5")==0||strcmp(str,"6")==0){ choose=atoi(str);break;} else{printf("\t\t\t选择错误请重新输入: ");} } if(choose==0){printf("\n\n\t…~~~…~~~谢谢使用本程序~~~…~~~…\n\n");}

return choose;

}//MainMenu()

int Menu(){ //主菜单函数

system("cls"); int choose; char str[20]; printf("\n\t\t\t*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=**=*=*=*"); printf("\n\t\t\t 请选择对应的选项按对应的方式遍历二叉树"); printf("\n\t\t\t*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=**=*=*=*"); printf("\n\t\t\t\t[1]按先序(递归)遍历二叉树\n"); printf("\n\t\t\t\t[2]按中序(递归)遍历二叉树\n"); printf("\n\t\t\t\t[3]按后序(递归)遍历二叉树\n"); printf("\n\t\t\t\t[4]按先序(非递归)遍历二叉树\n"); printf("\n\t\t\t\t[5]按中序(非递归)遍历二叉树\n"); printf("\n\t\t\t\t[6]按后序(非递归)遍历二叉树\n"); printf("\n\t\t\t\t[7]按层次(非递归)遍历二叉树\n"); printf("\n\t\t\t\t[0]返回主菜单"); printf("\n\t\t\t*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=**=*=*=*\n"); printf("\t\t\t请输入你的选择: "); while(1){ scanf("%s",str);

||strcmp(str,"4")==0||strcmp(str,"5")==0||strcmp(str,"6")==0||strcmp(str,"7")==0) { choose=atoi(str);break;} else{printf("\t\t\t选择错误请重新输入: ");} } return choose;

}//Menu()

int Menu1(){ //查看二叉树信息菜单

system("cls"); int choose; char str[20],str1[20]; printf("\n\t*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=**=*=*=**=*=*=**=*=*=**=*=*=*=*=*=*");

printf("\n\t 请选择对应的选项查看当前二叉树的信息");

printf("\n\t*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=**=*=*=**=*=*=**=*=*=**=*=*=*=*=*=*");

printf("\n\t [1]返回根结点值 [2]二叉树的深度\n");

printf("\n\t [3]二叉树的总结点个数 [4]二叉树中度为2的结点个数\n"); printf("\n\t [5]二叉树中度为1的结点个数 [6]二叉树中叶子结点个数\n"); printf("\n\t [7]某一值的结点个数及位置 [8]二叉树中某结点的左孩子\n"); printf("\n\t [9]二叉树中某结点的右孩子 [10]二叉树中某结点的左兄弟\n"); printf("\n\t [11]二叉树中某结点的右兄弟 [12]二叉树中某结点的双亲\n"); printf("\n\t [0]返回主菜单\n");

printf("\t*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=**=*=*=**=*=*=**=**=*=*=**=*=*=*=*=*=*\n");

printf("\t\t请输入你的选择: ");

while(1){ scanf("%s",str); choose=atoi(str); itoa(choose,str1,10); if(choose>0&&choose<=12&&strcmp(str,str1)==0||strcmp(str,"0")==0)break; else{printf("\t\t选择错误请重新输入: ");} } return choose;

}//Menu1()

int Menu2(){ //主菜单函数

system("cls"); int choose; char str[20]; printf("\n\t\t\t*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=*");; printf("\n\t\t\t 请选择对应的选项对二叉树进行操作");

printf("\n\t\t\t\t[1]删除某一结点\n"); printf("\n\t\t\t\t[2]对某一结点生成子树\n"); printf("\n\t\t\t\t[3]修改某一结点值\n"); printf("\n\t\t\t\t[4]清空二叉树\n"); printf("\n\t\t\t\t[5]销毁二叉树\n"); printf("\n\t\t\t\t[0]返回主菜单"); printf("\n\t\t\t*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=*"); printf("\n\t\t\t请输入你的选择: "); while(1){ scanf("%s",str); if(strcmp(str,"0")==0||strcmp(str,"1")==0||strcmp(str,"2")==0||strcmp(str,"3")==0 ||strcmp(str,"4")==0||strcmp(str,"5")==0){ choose=atoi(str);break;} else{printf("\t\t\t选择错误请重新输入: ");} }

return choose;

}//Menu2()

void main(){

system("color e0");

BiTree T=NULL;

int num,l,h,choose,flag=0,i=0,j=0,n;

TElemType ch;

while((choose=MainMenu())!=0){

switch(choose){ case 1:if(flag==2){ printf("您已清空了之前的二叉树,目前为空树,无须再建立空树!\n\n");} else{ if(flag==0){InitBiTree(T);flag=1;} else{ printf("您之前已经建过空树,若想重建,请先销毁当前的树!\n\n");}} system("pause");break; case 2:if(!T)printf("您还没有建树，请先建树!\n\n"); else{if(T->next) printf("二叉树已存在，若想重建，请先清空当前的二叉树!\n\n"); else{ system("cls");CreateBiTree(T->next,i,j,ch); printf("\n\n二叉树创建完成!\n\n");} } system("pause");break; case 3:if(!T)printf("您还没有建树，请先建树!\n\n"); else{l=0;h=0; if(T->next){printf("\n 当前二叉树的树状图如下:\n\n");}

system("pause");break; case 4:if(!T){printf("您还没有建树，请先建树!\n\n");system("pause");} else{ if(!T->next){printf("二叉树目前为空树，请创建非空树后再遍 else{ while((choose=Menu())!=0){ l=0;h=0; printf("\n 当前二叉树的树状图如下:\n\n"); Lev_Traverse(T->next,TreeDepth(T->next,l,h)); switch(choose){ case 1:FirstPrint(T->next,i);printf("\n\n"); system("pause");break; case 2:MiddlePrint(T->next,i);printf("\n\n"); system("pause");break; case 3:LastPrint(T->next,i);printf("\n\n"); system("pause");break; case 4:PreOrderTraverse(T->next); system("pause");break; case 5:InOrderTraverse(T->next); system("pause");break; case 6:PostOrderTraverse(T->next); system("pause");break; case 7:LevelOrderPrint(T->next);printf("\n\n"); system("pause");break; default:exit(ERROR); 历!\n\n");system("pause");}

}}}}break; case 5:if(!T){printf("您还没有建树，请先建树!\n\n");system("pause");}

else{

if(!T->next){printf("二叉树目前为空树，请创建非空树后再查看信息!\n\n");system("pause");}

else{ while((choose=Menu1())!=0){ l=0;h=0; printf("\n 当前二叉树的树状图如下:\n\n"); Lev_Traverse(T->next,TreeDepth(T->next,l,h)); switch(choose){ case 1:GetRootElem(T->next); system("pause");break; case 2:printf("当前二叉树的深度为: %d\n\n",TreeDepth(T->next,l,h));

中有效结点的个数 system("pause");break; case 3:printf("\n二叉树

为: %d\n\n",GetElemSum(T->next));

system("pause");break;

case 4:printf("\n二叉树中度为

为: %d\n\n",GetLeafNum(T->next)-1);

2的结点个数 system("pause");break; case 5:printf("\n二叉树中度为1的结点个数为: %d\n\n", GetElemSum(T->next)-2*GetLeafNum(T->next)+1);

中叶子结点个数 system("pause");break; case 6:printf("\n二叉树

为: %d\n\n",GetLeafNum(T->next));

system("pause");break; case 7:printf("请输入要统计的元素: "); fflush(stdin);scanf("%c",&ch);

GetElemNum(T->next,ch);

system("pause");break;

case 8:Lchild(T->next,GetElemSum(T->next)); system("pause");break; case 9:Rchild(T->next,GetElemSum(T->next)); system("pause");break; case 10:LBrother(T->next,GetElemSum(T->next)); system("pause");break; case 11:RBrother(T->next,GetElemSum(T->next)); system("pause");break; case 12:Partents(T->next,GetElemSum(T->next)); system("pause");break; default:exit(ERROR); }}}}break; case 6:if(!T){printf("您还没有建树，请先建树!\n\n");system("pause");}

else{

if(!T->next){printf("二叉树目前为空树，请创建非空树后再对树进行操作!\n\n");system("pause");}

else{ while((choose=Menu2())!=0){ if(choose!=4&&choose!=5){ system("cls");l=0;h=0; printf("\n 当前二叉树的树状图如下:\n\n"); Lev_Traverse(T->next,TreeDepth(T->next,l,h)); printf("\n二叉树中有效结点的个数为: %d\n\n",GetElemSum(T->next)); printf("当前二叉树的深度为: %d\n\n",h);} switch(choose){ case 1:num=GetElemSum(T->next); TreeDelete(T->next,GetElemSum(T->next)); if(num!=GetElemSum(T->next)){ l=0;h=0; printf("\n 删除后二叉树的树状图如下:\n\n");

本文来源：https://www.bwwdw.com/article/ismi.html