#include<stdio.h>
#define TREEMAX 100
typedef struct BT
{
char data;
BT *lchild;
BT *rchild;
}BT;
BT *CreateTree();
void Preorder(BT *T);
void Postorder(BT *T);
void Inorder(BT *T);
void Leafnum(BT *T);
void Nodenum(BT *T);
int TreeDepth(BT *T);
int count=0;
void main()
{
BT *T=NULL;
char ch1,ch2,a;
ch1='y';
while(ch1=='y'||ch1=='y')
{
printf("\n");
printf("\n\t\t 二叉树子系统");
printf("\n\t\t*****************************************");
printf("\n\t\t 1---------建二叉树 ");
printf("\n\t\t 2---------先序遍历 ");
printf("\n\t\t 3---------中序遍历 ");
printf("\n\t\t 4---------后序遍历 ");
printf("\n\t\t 5---------求叶子数 ");
printf("\n\t\t 6---------求结点数 ");
printf("\n\t\t 7---------求树深度 ");
printf("\n\t\t 0---------返 回 ");
printf("\n\t\t*****************************************");
printf("\n\t\t 请选择菜单号 （0--7）");
scanf("%c",&ch2);
getchar();
printf("\n");
switch(ch2)
{
case'1':
printf("\n\t\t请按先序序列输入二叉树的结点:\n");
printf("\n\t\t说明：输入结点（‘0’代表后继结点为空）后按回车。\n");
printf("\n\t\t请输入根结点:");
T=CreateTree();
printf("\n\t\t二叉树成功建立！\n");break;
case'2':
printf("\n\t\t该二叉树的先序遍历序列为:");
Preorder(T);break;
case'3':
printf("\n\t\t该二叉树的中序遍历序列为:");
Inorder(T);break;
case'4':
printf("\n\t\t该二叉树的后序遍历序列为:");
Postorder(T);break;
case'5':
count=0;Leafnum(T);
printf("\n\t\t该二叉树有%d个叶子。\n",count);break;
case'6':
count=0;Nodenum(T);
printf("\n\t\t该二叉树总共有%d个结点。\n",count);break;
case'7':
printf("\n\t\t该树的深度为:%d",TreeDepth(T));
break;
case'0':
ch1='n';break;
default:
printf("\n\t\t***请注意：输入有误！***");
}
if(ch2!='0')
{
printf("\n\n\t\t按【Enter】键继续，按任意键返回主菜单！\n");
a=getchar();
if(a!='\xA')
{
getchar();
ch1='n';
}
}
}
}
BT *CreateTree()
{
BT *t;
char x;
scanf("%c",&x);
getchar();
if(x=='0')
t=NULL;
else
{
t=new BT;
t->data=x;
printf("\n\t\t请输入%c结点的左子结点:",t->data);
t->lchild=CreateTree();
printf("\n\t\t请输入%c结点的右子结点:",t->data);
t->rchild=CreateTree();
}
return t;
}
void Preorder(BT *T)
{
if(T)
{
printf("%3c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
void Inorder(BT *T)
{
if(T)
{
Inorder(T->lchild);
printf("%3c",T->data);
Inorder(T->rchild);
}
}
void Postorder(BT *T)
{
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
printf("%3c",T->data);
}
}
void Leafnum(BT *T)
{
if(T)
{
if(T->lchild==NULL&&T->rchild==NULL)
count++;
Leafnum(T->lchild);
Leafnum(T->rchild);
}
}
void Nodenum(BT *T)
{
if(T)
{
count++;
Nodenum(T->lchild);
Nodenum(T->rchild);
}
}
int TreeDepth(BT *T)
{
int ldep,rdep;
if(T==NULL)
return 0;
else
{
ldep=TreeDepth(T->lchild);
rdep=TreeDepth(T->rchild);
if(ldep>rdep)
return ldep+1;
else
return rdep+1;
}
}
