#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; if(l>h)h=l; TreeDepth(T->lchild,l,h); TreeDepth(T->rchild,l,h);
}
return 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++){
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;
return OK;
}//Lev_Traverse
Status FirstPrint(BiTree T,int i){
//按先序次序(递归)访问二叉树
if(i==0)printf("\n先序(递归)遍历结果如下:\n"); if(T){
i++;printf("%-5c",T->data); //访问T FirstPrint(T->lchild,i); //递归遍历左子树 FirstPrint(T->rchild,i); //递归遍历右子树 }
i=0;
return OK;
}//FirstPrintBiTree
Status MiddlePrint(BiTree T,int i){
//按中序次序(递归)访问二叉树
if(i==0)printf("\n中序(递归)遍历结果如下:\n"); if(T){
i++;
MiddlePrint(T->lchild,i); //递归遍历左子树 printf("%-5c",T->data); //访问T
MiddlePrint(T->rchild,i); //递归遍历右子树 }
i=0;
return OK;
}//MiddlePrint
Status 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;
}//LastPrint
Status PreOrderTraverse(BiTree T){
//按先序(非递归)遍历二叉树T
BiTree p,S,q;
int flag=0;
if(!(S=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR); S->next=NULL; //建立空栈S
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){ //遍历左子树,若当前结点左右孩子都不存在则跳出
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;
}//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); 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
\n",num,q[num]->data);
if(q[i]->rchild&&q[i]->lchild==q[num])printf("位置%d
为: %c\n",num,q[num]->data,q[i]->rchild->data);
}
return OK;
}//RBrother 的%c的右兄弟的%c没有右兄弟
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;
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;
}//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;
}
if(q[num]->lchild&&q[num]->rchild){
printf("您输入的位置序号已有左子树和右子树,无法再此位置插入\n\n");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]->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;
}//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){
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;
}//Modify
int MainMenu(){ //主菜单函数
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 [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);
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]; 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*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=*");
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(){
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); } }
}
二叉树的应用一实验目的1使学生熟练掌握二叉树的逻辑结构和存储结构2熟练掌握二叉树的各种遍历算法3熟悉二叉树的应用二实验内容本次实验…
内蒙古科技大学本科生课程设计说明书题目数据结构课程设计二叉树的遍历和应用学生姓名学号专业班级指导教师20xx年5月29日内蒙古科技…
广西工学院计算机学院数据结构课程实验报告书实验六二叉树的基本操作及其应用学生姓名学号班级指导老师专业计算机学院软件学院提交日期20…
数据结构实验报告实验题目树和二叉树的应用实验内容重言式判别实验目的掌握树和二叉树的概念及工作原理运用其原理及概念完成上述实验题中的…
实验报告课程名称数据结构上机实验实验项目二叉树的应用实验仪器PC机系别专业班级学号学生姓名实验日期成绩指导教师实验三二叉树的应用1…
实验报告实验课程数据结构实验项目实验九二叉树遍历的应用实验地点指导教师班级学生姓名金轶洲学号09020xx03教师评分日期浙江传媒…
实验报告课程名称数据结构上机实验实验项目二叉树的应用实验仪器PC机系别专业班级学号学生姓名实验日期成绩指导教师实验三二叉树的应用1…
内蒙古科技大学本科生课程设计说明书题目数据结构课程设计二叉树的遍历和应用学生姓名学号专业班级指导教师20xx年5月29日内蒙古科技…
二叉树的应用一实验目的1使学生熟练掌握二叉树的逻辑结构和存储结构2熟练掌握二叉树的各种遍历算法3熟悉二叉树的应用二实验内容本次实验…
广西工学院计算机学院数据结构课程实验报告书实验六二叉树的基本操作及其应用学生姓名学号班级指导老师专业计算机学院软件学院提交日期20…