#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASTABLE -1
#define OVERFLOW -2
#define NODE_SIZE 100 //单个二叉树中包含的最大节点数(包括空结点)
#define NUMOFSHU 10 //同时管理二叉树的个数
#define STACKINCREMENT 10
typedef char TElemType;//二叉树结点关键字
typedef int ElemType;//二叉树结点值
typedef int status;//定义函数类型
typedef struct BiTreeData{
TElemType da;
ElemType ta;
}BiTreeData;//二叉树数据域
typedef struct BiTNode{
struct BiTNode *lchild,*rchild;
BiTreeData data;
}BiTNode,*BiTree;//二叉树结点
typedef struct BiTHead{
BiTree head;
}BiTHead;//二叉树头节点
typedef struct QNode{
BiTNode quedata;
struct QNode *next;
}QNode,*QueuePtr;//队列结点
typedef struct{
QueuePtr front;//队头指针
QueuePtr rear;//队尾指针
}LinkQueue;
status InitBiTree(BiTree *T);
status CreateBiTree(BiTree *T,TElemType definition[],ElemType number[]);
status DestroyBiTree(BiTree *T);
status ClearBiTree(BiTree *T);
status BiTreeEmpty(BiTree T);
status BiTreeDepth(BiTree T);
BiTree LocateNode(BiTree T,TElemType e);
status Assign(BiTree T,TElemType e,ElemType value);
BiTree GetParent(BiTree T,TElemType e,int *m);
BiTree GetSibling(BiTree T,TElemType e);
status InsertNode(BiTree T,TElemType e,int LR,BiTree *c);
status DeleteNode(BiTree *T,TElemType e);
status PreOrderTraverse(BiTree T,status(*visit)(TElemType,ElemType));
status InOrderTraverse(BiTree T,status(*visit)(TElemType,ElemType));
status PostOrderTraverse(BiTree T,status(*visit)(TElemType,ElemType));
status LevelOrderTraverse(BiTree T,status(*visit)(TElemType,ElemType));
status OpenFile(BiTree *T);
status ReadFile(BiTree *T);
status InitQueue(LinkQueue *Q);
status DestroyQueue(LinkQueue Q);
status QueueEmpty(LinkQueue Q);
status EnQueue(LinkQueue *Q,BiTree T);
status DeQueue(LinkQueue *Q,BiTree T);
BiTree* LoadToArray(BiTree T,BiTree* nodes);
status visit(TElemType c,ElemType b);
int TreeNodes(BiTree T);
int i=0;
int num;
int k=0;
int numofnodes=0;
int nodenum=0;
int flag[NUMOFSHU];//二叉树是否存在的标记
int main()
{
BiTHead erchashu[NUMOFSHU];
int j,LR;
for(j=0;j<NUMOFSHU;j++){
flag[j]=0;
erchashu[j].head=NULL;
}
BiTree *T;
BiTree ptree=NULL,ptr=NULL;
ptr=(BiTree)malloc(sizeof(BiTNode));
TElemType e,E;
ElemType shu;
TElemType definition[NODE_SIZE];
ElemType number[NODE_SIZE];
int op=1;
while (op)
{
system("cls");
printf("\n\n");
printf(" Menu for Binary Tree\n");
printf("-------------------------------------------------------\n");
printf(" 1.InitBiTree 2.DestroyBiTree\n");
printf(" 3.CreateBiTree 4.ClearBiTree\n");
printf(" 5.BiTreeEmpty 6.BiTreeDepth\n");
printf(" 7.LocateNode 8.Assign\n");
printf(" 9.GetSibling 10.InsertNode\n");
printf(" 11.DeleteNode 12.PreOrderTraverse\n");
printf(" 13.InOrderTraverse 14.PostOrderTraverse\n");
printf(" 15.LevelOrderTraverse 16.OpenFile\n");
printf(" 17.ReadFile 0.Exit\n");
printf("--------------------------------------------------------\n");
printf(" \n请输入你将要操作第几个二叉树[1~%d](输入0退出):",NUMOFSHU);
scanf("%d",&num);
if(!num){
printf("欢迎下次再使用本系统!\n");
return 0;
}
else if(num>NUMOFSHU) num=num%NUMOFSHU;
T=&erchashu[num].head;
printf("请选择操作:");
scanf("%d",&op);
switch(op)
{
case 1:
if(InitBiTree(T)==OK)
printf("二叉树初始化成功!\n");
else
printf("二叉树初始化失败!\n");
getchar();getchar();break;
case 2:
if(DestroyBiTree(T)==OK)
printf("二叉树删除成功!\n");
else printf("二叉树删除失败!\n");
flag[num]=0;//标记序号为num的二叉树不存在
getchar();getchar();break;
case 3:
k=0;i=0;
printf("请输入各结点的关键字(#代表空):\n");
scanf("%s",definition);
printf("请输入各结点的值(-1代表结束):\n");
int a;scanf("%d",&a);
while(a!=-1){
number[k]=a;
k++;
scanf("%d",&a);
}
if(2*k+1!=strlen(definition)){ //判断输入是否合法
printf("二叉树创建失败!\n");
getchar();getchar();break;
}
k=0;i=0;
if (CreateBiTree(T,definition,number)==OK)
printf("二叉树创建成功!\n");
else printf("二叉树创建失败!\n");
i=0;k=0;getchar();getchar();break;
case 4:
if(ClearBiTree(T)==OK) printf("二叉树清空成功!\n");
else printf("二叉树清空失败!\n");
getchar();getchar();break;
case 5:
if(BiTreeEmpty(*T)==TRUE) printf("二叉树为空!\n");
else printf("二叉树不为空!\n");
getchar();getchar();break;
case 6:
if(BiTreeDepth(*T)==0) printf("求深度失败!\n");
else printf("二叉树深度为%d\n",BiTreeDepth(*T));
getchar();getchar();break;
case 7:
printf("\n----LocateNode功能待实现!\n");
printf("请输入要寻找的结点:");
getchar();
scanf("%c",&e);
ptree=LocateNode(*T,e);
if(ptree) printf("结点存在,值为:%d\n",ptree->data.ta);
else printf("结点不存在!\n");
ptree=NULL;getchar();getchar();break;
case 8:
printf("\n----Assign功能待实现!\n");
printf("请输入要赋值的结点和值:");
getchar();scanf("%c",&e);scanf("%d",&shu);
if(Assign(*T,e,shu)) printf("结点已赋值!\n");
else printf("结点赋值失败!\n");
getchar();getchar();break;
case 9:
printf("\n----GetSibling功能待实现!\n");
printf("请输入需要得到兄弟的结点:");
getchar();scanf("%c",&e);
ptree=GetSibling(*T,e);
if(ptree) printf("已得到兄弟结点:%c\n",ptree->data.da);
else printf("未得到兄弟结点\n");
ptree=NULL;getchar();getchar();break;
case 10:
printf("\n----InsertNode功能待实现!\n");
printf("请输入要插入的结点的父亲结点和插入的位置(0:左结点,1:右结点):");
getchar();scanf("%c",&e);scanf("%d",&LR);
printf("请输入要插入的结点和其值:");
getchar();scanf("%c",&E);scanf("%d",&shu);
ptr->data.da=E;ptr->data.ta=shu;
if(InsertNode(*T,e,LR,&ptr)) printf("结点已插入!\n");
else printf("结点插入失败!\n");
getchar();getchar();break;
case 11:
printf("\n----DeleteNode功能待实现!\n");
printf("请输入要删除的结点:");
getchar();scanf("%c",&e);
if(DeleteNode(T,e)) printf("结点已删除!\n");
else printf("结点删除失败!\n");
getchar();getchar();break;
case 12:
printf("\n----PreOrderTraverse功能待实现!\n");
if(flag[num]){
printf("前序遍历结果为:\n");
PreOrderTraverse(*T,visit);
}
else{
printf("程序错误\n");exit(ERROR);
}
getchar();getchar();break;
case 13:
printf("\n----InOrderTraverse功能待实现!\n");
if(flag[num]){
printf("中序遍历结果为:\n");
InOrderTraverse(*T,visit);
}
else{
printf("程序错误\n");exit(ERROR);
}
getchar();getchar();break;
case 14:
printf("\n----PostOrderTraverse功能待实现!\n");
if(flag[num]){
printf("后序遍历结果为:\n");
PostOrderTraverse(*T,visit);
}
else{
printf("程序错误\n");exit(ERROR);
}
getchar();getchar();break;
case 15:
printf("\n----LevelOrderTraverse功能待实现!\n");
if(flag[num]){
printf("层序遍历结果为:\n");
LevelOrderTraverse(*T,visit);
}
else{
printf("程序错误\n");exit(ERROR);
}
getchar();getchar();break;
case 16:
printf("\n----OpenFile功能待实现!\n");
printf("请输入文件名: ");
if(OpenFile(T)==OK){
nodenum=0;
printf("文件已创建!\n");
}
else printf("\n文件创建失败!\n");
getchar();getchar();break;
case 17:
printf("\n----ReadFile功能待实现!\n");
printf("请输入文件名: ");