#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
using namespace std;
typedef char ElemType; //定义二叉树结点值的类型为字符型
//全局变量
int LEAFCOUNT=0;
int NODECOUNT=0;
typedef struct BiTNode //定义树
{
char data ; //字符 数据
struct BiTNode *lchild,*rchild ; //定义左右孩子 struct为构造体
}BiTNode, *BiTree;
void CreateBiTree(BiTree &T)//按先序次序输入，以"#"表示空树
{
char ch ; 输入数据
scanf("%c",&ch) ; //输入数据，当ch为#时判断为空
if(ch =='#')
T = NULL ;
else{ //为T赋值，将BITNode属性赋予T
T=new BiTNode;
T->data = ch ; //将数据域指向ch
CreateBiTree(T->lchild); //构建左孩子
CreateBiTree(T->rchild)；//构建右孩子
}
}
void PreOrderTraverse(BiTree T)//先序遍历
{
if(T)
{
printf("%c ",T->data) ;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T->lchild);
printf("%c ",T->data) ;
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T)//后序遍历
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c ",T->data) ;
}
}
int BTDepth(BiTree T)//求二叉树的深度
{
if(T==NULL)
return 0;
else
{
int m=BTDepth(T->lchild);
int n=BTDepth(T->rchild);
if(m>n) return (m+1);
else return (n+1);
}
}
int Leaf(BiTree T)//求二叉树的叶子数, 使用全局变量
{
if(T!=NULL)
{
LEAFCOUNT=Leaf(T->lchild);
if((T->lchild==NULL)&&(T->rchild==NULL))
LEAFCOUNT=LEAFCOUNT+1;
LEAFCOUNT=Leaf(T->rchild);
}
return LEAFCOUNT;
}
void NodeCount(BiTree T)//求二叉树的结点总数, 使用全局变量
{
if (T!= NULL)
{
NODECOUNT = NODECOUNT + 1;
NodeCount(T->lchild);
NodeCount(T->rchild);
}
}
int main()
{
BiTree T=NULL;
int select;
while(scanf("%d",&select)!=EOF)
{
switch(select)
{
case 0:
return 0;
case 1:
getchar();
CreateBiTree(T);
break;
case 2:
if(T) {
PreOrderTraverse(T);
printf("\n");
}
break;
case 3:
if(T) {
InOrderTraverse(T);
printf("\n");
}
break;
case 4:
if(T) {
PostOrderTraverse(T);
printf("\n");
}
break;
case 5:
printf("%d\n",BTDepth(T));
break;
case 6:
LEAFCOUNT=0;
Leaf(T);
printf("%d\n",LEAFCOUNT);
break;
case 7:
NODECOUNT=0;
NodeCount(T);
printf("%d\n",NODECOUNT);
break;
}
}
return 0;
}