#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define OVERFLOW -1
#define OK 0
#define ERROR -1
#define TRUE 1
#define FALSE 0
#define MAXQSIZE 100
typedef int Status;
/*typedef struct TElemType{
char name[20];
char number[12];
}TElemType;
*/
typedef struct BiTNode{ // 结点结构
char data;
struct BiTNode *lchild, *rchild; // 左右孩子指针
}BiTNode;
typedef BiTNode *BiTree;//定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数,leaf为叶子数
void ClearBiTree(BiTNode *T);
void DestroyBiTree(BiTNode *T);
Status CreateBiTree(BiTNode *T);
Status PreOrderTraverse(BiTree T);
void InOrderTraverse(BiTree T);
void PostOrderTraverse(BiTree T);
Status LayerOrderTraverse(BiTree T);
Status LeaCount(BiTree T);
int BiTreeEmpty(BiTree T);
int InsertChild(BiTNode *T,BiTNode *p,int LR,char c);
int InsertL_BiTree(BiTNode *parent,char x);
int InsertR_BiTree(BiTNode *parent,char x);
char Root(BiTree T);
char Value(BiTree *T,BiTNode *e);
int Assign(BiTree *T, BiTNode *e, char value);
BiTNode* Parent(BiTNode *T,BiTNode *e);
BiTNode* LeftChild(BiTNode *T,BiTNode *e);
BiTNode* RightChild(BiTNode *T,BiTNode *e);
BiTNode* LeftSibling(BiTNode *T,BiTNode *e);
BiTNode* RightSibling(BiTNode *T,BiTNode *e);
BiTNode* Search(BiTNode *T,int snum);
void Inorder(BiTNode *t);
int DepthZ(BiTNode *t);
void menu();
int main()
{
BiTree T=NULL;
BiTree M;
int st;
int j;
char k;
int op = 0,dep = 0;
do{
system("cls");
menu();
printf("\n\n Please input your option:");
scanf("%d",&op);
switch(op){
case 0 :break;
case 1 :
InitBiTree(T);
printf("success");
getchar();getchar();
break;
case 2:
DestroyBiTree(T);
printf("success");
break;
case 3:
printf("\n\n写入一个二叉树:\n");
getchar();
st=CreateBiTree(T);
if(st==OK)
printf("创建成功");
else
printf("创建失败");
getchar();getchar();
break;
case 4:
ClearBiTree(T);
printf("清为空树1");
getchar();getchar();
break;
case 5:
st=BiTreeEmpty(T);
if(st==1)
printf("T为空树2");
else
printf("非空3");
getchar();getchar();
break;
case 6:
st=BiTreeEmpty(T);
printf("%d\n",st);
getchar();getchar();
break;
case 7:
printf("%c\n",Root(T));
getchar();getchar();
break;
case 8:
printf("输入一个数:\n");
scanf("%d",&j);
M=Search(T,j);
printf("%c",M->data);
getchar();getchar();
break;
case 9:
{
printf("输入一个数:\n");
scanf("%d",&j);
printf("输入一个节点:\n");
scanf("%c",&k);
M=Search(T,j);
st=Assign(T,M,k);
if(st==1)
printf("\n赋值成功");
else
printf("\n失败");
getchar();getchar();
break;
}
case 10:
{
printf("输入一个数:\n");
scanf("%d",&j);
M=Search(T,j);
Parent(T,M);
break;
}
case 11:
{
printf("输入一个数:\n");
scanf("%d",&j);
LeftChild(T,Search(T,j));
break;
}
case 12:
{
printf("输入一个数:\n");
scanf("%d",&j);
RightChild(T,Search(T,j));
break;
}
case 13:
{
printf("输入一个数:\n");
scanf("%d",&j);
LeftSibling(T,Search(T,j));
break;
}
case 14:
{
printf("输入一个数:\n");
scanf("%d",&j);
RightSibling(T,Search(T,j));
break;
}
case 15:
{
BiTNode *c=NULL;
CreateBiTree(c);
int j,LR;
printf("输入一个数:\n");
scanf("%d",&j);
printf("Please input LR:\n");
scanf("%d",&LR);
InsertChild(T,Search(T,j),LR,c);
break;
}
case 16:
{
int j,LR;
printf("输入一个数:\n");
scanf("%d",&j);
printf("Please input LR:\n");
scanf("%d",&LR);
DeleteChild(T,Search(T,j),LR);
break;
}
case 17 :
getchar();
PreOrderTraverse(T);
getchar();
break;
case 18 :getchar();
InOrderTraverse(T);
getchar();
break;
case 19:getchar();
PostOrderTraverse(T);
getchar();
break;
case 20:getchar();
LevelOrder(T);
getchar();
break;
/*case 7 :getchar();
int count;
count = LeaCount(T);
printf("\t叶子数目:%d",count);
getchar();
break;*/
default : ;
}
}while(op);
printf("\n--------------------Welcome again!--------------------\n");
return 0;
}
void InitBiTree(BiTNode *T)
{
T=NULL;
}
void DestroyBiTree(BiTNode *T)
{
if(T!=NULL)
{
DestroyBiTree(T->lchild);
DestroyBiTree(T->rchild);
free(T);
}
}
BiTree Initiate_BiTree()
/*初始化二叉树函数1.先决条件:无2.函数作用:初始化一棵空的带头结点的二叉树,返回头结点的地址*/
{
BiTNode *bt;
bt=(BiTNode *)malloc(sizeof(BiTNode));
bt->lchild=NULL;
bt->rchild=NULL;
return bt;
}
BiTNode *Search_BiTree(BiTree bt,char x)
/*查找函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:在二叉树bt中查找值为x的数据元素,成功返回其地址,找不到返回NULL*/
{
BiTree p=NULL;
if(bt)
{
if(bt->data==x)
return bt;
if(bt->lchild)
p=Search_BiTree(bt->lchild,x);
if(p)
return p;
if(bt->rchild)
p=Search_BiTree(bt->rchild,x);
if(p)
return p;
}
return FALSE;
}
int InsertChild(BiTNode *T,BiTNode *p,int LR,char c)
{
int st;
switch(LR){
case 0:
st=InsertL_BiTree(p,c);
break;
case 1:
st=InsertR_BiTree(p,c);
break;
}
return st;
}
int InsertL_BiTree(BiTNode *parent,char x)
/*�
评论0