#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<conio.h>
typedef char telemtype;
typedef int status;
typedef struct bitnode
{ telemtype data;
struct bitnode *lchild,*rchild;
}bitnode,*bitree;
bitree t;
status initbitree(bitree&t)
{t=NULL;
return 1;
}
void creatbitree(bitree&t)
{telemtype a;
initbitree(t);
cout<<"请输入元素值：";
cin>>a;
if(a=='#') t=NULL;
else
{
 t=(bitree)malloc(sizeof(bitnode));
if(!t) exit(-2); 
t->data =a;
creatbitree (t->lchild);
creatbitree (t->rchild);
}
}
status vist(telemtype e)
{
    cout<<e;
    return 1;
}
status preordertraverse(bitree t)
{
    if(t)
{vist(t->data);
preordertraverse(t->lchild);
preordertraverse(t->rchild);
    } 
    else
        return 0;
}
status inordertraverse(bitree t)
{
    if(t)
    {
    preordertraverse(t->lchild);
    vist(t->data);
    preordertraverse(t->rchild);
    }
    else
        return 0;
}
status postordertraverse(bitree t)
{
    if(t)
{
        
preordertraverse(t->lchild);
preordertraverse(t->rchild);
vist(t->data);
    }
    else
        return 0;
}
void preorderttraverseleaf(bitree t)
{
    if(t!=NULL)
    {if(t->lchild==NULL&&t->rchild==NULL)
    cout<<t->data;
preorderttraverseleaf(t->lchild);
preorderttraverseleaf(t->rchild);
    }
}
status leafcount(bitree t)
{
    int leafnumber;
    if(t==NULL) leafnumber=0;
    else if(t->lchild==0&&t->rchild==0) leafnumber=1;
    else leafnumber=leafcount(t->lchild )+leafcount(t->rchild);
    return leafnumber;
}
status posttreedepth(bitree t)
{
    int hl,hr,max;
    if(t!=NULL)
    {
    hl=posttreedepth(t->lchild);
    hr=posttreedepth(t->rchild);
    max=hl>hr? hl:hr;
    return (max+1);
    }
    else return 0;
}

void mainwork()
{int m;
cout<<"********************欢迎使用二叉树的一些基本操作********************"<<endl;
cout<<"********************          菜单选择          ********************"<<endl;
cout<<"********************    1.先序遍历二叉树        ********************"<<endl;
cout<<"********************    2.中序遍历二叉树        ********************"<<endl;
cout<<"********************    3.后序遍历二叉树        ********************"<<endl;
cout<<"********************    4.输出叶子节点          ********************"<<endl;
cout<<"********************    5.输出叶子节点个数      ********************"<<endl;
cout<<"********************    6.输出二叉树的深度      ********************"<<endl;
cout<<"********************    7.退出                  ********************"<<endl;
cout<<"请输入您的选择：";
cin>>m;
while (!(m==1||m==2||m==3||m==4||m==5||m==6||m==7))
{
    cout<<"请重新输入";
cin>>m;
}
while(1)
{
    switch(m)
    {
    case 1:cout<<"先序遍历结果为：";preordertraverse(t); break;
    case 2:cout<<"中序遍历结果为：";inordertraverse(t);break;
    case 3:cout<<"后序遍历结果为：";postordertraverse(t);break;
    case 4:cout<<"  叶子节点为  ：";preorderttraverseleaf(t);break;
    case 5:cout<<"叶子结点个数为：";leafcount(t);break;
    case 6:cout<<" 二叉树深度为 ：";posttreedepth(t);break;
    case 7:system("cls");exit(0);break;
    default:break;
    }
cout<<"********************欢迎使用二叉树的一些基本操作********************"<<endl;
cout<<"********************          菜单选择          ********************"<<endl;
cout<<"********************    1.先序遍历二叉树        ********************"<<endl;
cout<<"********************    2.中序遍历二叉树        ********************"<<endl;
cout<<"********************    3.后序遍历二叉树        ********************"<<endl;
cout<<"********************    4.输出叶子节点          ********************"<<endl;
cout<<"********************    5.输出叶子节点个数      ********************"<<endl;
cout<<"********************    6.输出二叉树的深度      ********************"<<endl;
cout<<"********************    7.退出                  ********************"<<endl;
cout<<"请输入您的选择：";
cin>>m;
}
}
void main()
{
    cout<<"请先输入节点序列"<<endl;
creatbitree(t);
cout<<"请按菜单操作"<<endl;
mainwork();
}