#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}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; }//NumJudgeStatus InitBiTree(BiTree &T){//构造空二叉树 T if(!(T=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR);T->next=NULL;printf("\n\t 空二叉树构建成功 !\n\n");return OK;}//InitBiTreeStatus 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;}//DestroyTreeStatus ClearBiTree(BiTree &T,int sum,int &i){//清空二叉树 if(T){typedef struct BiTNode{ //定义结构体 TElemType data; // 结点数值 struct BiTNode *lchild; // 左孩子指针 struct BiTNode*rchild; // 右孩子指针 struct BiTNode *next;//下一结点指针//若申请空间失败则退出ClearBiTree(T->lchild,sum,i);ClearBiTree(T->rchild,sum,i);free(T);i++;} if(i==sum){printf("\t 二叉树清空成功!\n");T=NULL;} return OK;}//ClearBiTreeStatus 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;}//CreateBitreeStatus TreeDepth(BiTree T,int l,int &h){//若二叉树存在,返回其深度if(T){l=l+1;if(l>h)h=l;TreeDepth(T->lchild,l,h);TreeDepth(T->rchild,l,h);}return h;}//TreeDepthStatus GetRootElem(BiTree T){//获取根结点值printf(" 该二叉树的根结点值为: %c\n\n",T->data);return OK;}//GetRootElemStatus 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;}//SaveElemStatus 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++){ printf(" ");} k--;} 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;returnOK; }//Lev_TraverseStatus FirstPrint(BiTree T,int i){//按先序次序(递归)访问二叉树if(i==0)printf("\n 先序(递归)遍历结果如下:\n"); if(T){ i++;printf("%-5c",T->data); // 访问TFirstPrint(T->lchild,i); // 递归遍历左子树FirstPrint(T->rchild,i); // 递归遍历右子树} i=0;return OK;}//FirstPrintBiTreeStatus MiddlePrint(BiTree T,int i){//按中序次序(递归)访问二叉树if(i==0)printf("\n 中序(递归)遍历结果如下:\n"); if(T){i++;MiddlePrint(T->lchild,i); //递归遍历左子树printf("%-5c",T->data); // 访问TMiddlePrint(T->rchild,i); //递归遍历右子树}i=0;return OK;}//MiddlePrintStatus LastPrint(BiTree T,int i){//按后序次序(递归)访问二叉树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;}//LastPrintStatus PreOrderTraverse(BiTree T){//按先序(非递归)遍历二叉树TBiTree p,S,q;int flag=0; if(!(S=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR);S->next=NULL; //建立空栈Sp=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; }//PreOrderTraverseStatus InOrderTraverse(BiTree T){// 中序遍历(非递归) 二叉树TBiTree p,S,q; if(!(S=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR);S->next=NULL; //建立空栈Sp=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;}//InOrderTraverseStatus PostOrderTraverse(BiTree T){//后序遍历(非递归)二叉树TBiTree p,S,q; if(!(S=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR);S->next=NULL; // 建立空栈Sp=T;printf("\n 后序(非递归) 遍历结果如下:\n");while(1){while(1){ //遍历左子树,若当前结点左右孩子都不存在则跳出q=S->next;S->next=p;p->next=q; //当前结点进栈if(p->lchild)p=p->lchild;else{if(p->rchild)p=p->rchild; else{break;}}}while(S->next){ p=S->next;S->next=p->next; printf("%-5c",p->data); 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; }//PostOrderTraverseStatus 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;}//GetElemSumStatus 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;}//LevelOrderPrintStatus 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;}//GetElemNumStatus 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;}//GetLeafNumStatus 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); 为: %c\n",num,q[num]->data,q[i]->lchild->data);if(q[i]->rchild==q[num])printf(" 位置%d 的%c 的左兄弟}return OK;}//LBrotherStatus 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);else{for(i=1;i<num;i++){ if(q[i]->lchild==q[num]||q[i]->rchild==q[num])break;} 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;}//RBrotherStatus 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;}//LchildStatus 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;}//RchildStatus 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;}//PartentsStatus TreeDelete(BiTree &T,int sum){//删除第num 个结点BiTree p,p1,*q;if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);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;}//TreeDeleteStatus 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;} if(q[num]->lchild&&q[num]->rchild){ printf(" 您输入的位置序号已有左子树和右子树, 无法再此位置插入\n\n");returnERROR;}if(q[num]->lchild&&!q[num]->rchild){printf(" 位置%d 的%c 处只能生成右子树,确定插入/退出(y/n):",num,q[num]->data);while(1){scanf("%s",str); 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;}} 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){scanf("%s",str); 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;} 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;}//TreeInsertStatus 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){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 您只能输入一个字符: "," ");}q[num]->data=str[0];printf("\n 修改成功\n");n=1;return OK;}//Modifyint MainMenu(){ // 主菜单函数system("cls");int choose;char str[20];n； r-t4"F/H\ 次一次一次一次一次一次一次一次次一次一次一次次一次一次一次次一次一次一次次一次一次一次”'printf("\n\t\t\t 计本102 卢荣盼1018014052");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] 退出程序 "）;n ； r-t4"F/H \ 次一次一次一次一次一次一次一次次一次一次一次次一次一次一次次一次一次一次次一次一次一次”\・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];n ； r-t4"F/H \ 次一次一次一次一次一次一次一次次一次一次一次次一次一次一次次一次一次一次次一次一次一次”'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"); 按先序 （非递归 ）遍历二叉树 \n"）; 按中序 （非递归 ）遍历二叉树 \n"）; 按后序 （非递归 ）遍历二叉树 \n"）;按层次 （非递归 ）遍历二叉树 \n"）;printf("\n\t\t\t\t[0] 返回主菜单 ");printf("\t\t\t 请输入你的选择 : "); while(1){printf("\n\t\t\t* *一*一*一*一*一*一**一*一*一**一*一*一**一*一*一**一*一*, *n );printf("\n\t\t\t\t[4]printf("\n\t\t\t\t[5]printf("\n\t\t\printf("\n\t\t\t**一*一*一*一*一*一**一*一*一**一*一*一**一*一*一**一*一*, *\n");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||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]; * 一* 一* 一* 一* 一* 一** 一* 一* 一** 一* 一* 一** 一* 一* 一** 一* 一* 一** 一* 一* 一** 一* 一* 一** 一*、* 一* 一* 一* 一* 一* 一** 一* 一* 一** 一* 一* 一** 一* 一* 一** 一* 一* 一** 一* 一* 一** 一* 一* 一** 一* 一*伙一*一*一*・ 111 /Jprintf("\n\t [1] 返回根结点值printf("\n\t [3] 二叉树的总结点个数printf("\n\t [5] 二叉树中度为 1 的结点个数printf("\n\t [7] 某一值的结点个数及位置printf("\n\t [9] 二叉树中某结点的右孩子printf("\n\t [11] 二叉树中某结点的右兄弟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 选择错误请重新输入 : ");}printf("\n\t**一*“ );printf("\n\t请选择对应的选项查看当前二叉树的信息 "); [2] 二叉树的深度 \n"); [4]二叉树中度为 2 的结点个数 \n"); [6] 二叉树中叶子结点个数 \n");[8] 二叉树中某结点的左孩子 \n"); [10] 二叉树中某结点的左兄弟 \n"); [12] 二叉树中某结点的双亲 \n");} 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 *=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=*");printf("\n\t\t\t\t[1] printf("\n\t\t\t\t[2] printf("\n\t\t\t\t[3] printf("\n\t\t\t\t[4]删除某一结点\n"); 对某一结点生成子树\n"); 修改某一结点值\n"); 清空二叉树\n"); 销毁二叉树\n");返回主菜单");*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=*");printf("\n\t\t\t\t[5] printf("\n\t\t\t\t[0] printf("\n\t\t\tprintf("\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");}Lev_Traverse(T->next,TreeDepth(T->next,l,h));}system("pause");break;case 4:if(!T){printf(" 您还没有建树，请先建树!\n\n");system("pause");}else{if(!T->next){printf(" 二叉树目前为空树，请创建非空树后再遍历!\n\n");system("pause");}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);}}}}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 二叉树中度为 2 的结点个数为: %d\n\n",GetLeafNum(T->next)-1);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");Lev_Traverse(T->next,TreeDepth(T->next,l,h));printf("\n 二叉树中有效结点的个数为: %d\n\n",GetElemSum(T->next));printf(" 当前二叉树的深度为: %d\n\n",h);}system("pause");break;case 2:num=GetElemSum(T->next);TreeInsert(T->next,GetElemSum(T->next));if(num!=GetElemSum(T->next)){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);}system("pause");break;case 3:Modify(T->next,GetElemSum(T->next),n);if(n==1){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);}system("pause");break;case 4:h=0;ClearBiTree(T->next,GetElemSum(T->next),h);flag=2;break;case 5:DestroyTree(T,T->next);flag=0;break; default:exit(ERROR);}if(choose==4){printf("\n\t 您已清空了当前的二叉树,程序将退回到主菜单,请重新建树后再回本菜单操作!\n\n");system("pause");break;} if(choose==5){printf("\n\t 您已销毁了当前的二叉树,程序将退回到主菜单,请重新建树后再回本菜单操作!\n\n");system("pause");break;}}}}break;default:exit(ERROR);}。