#include<iostream>
using namespace std;
typedef char elemtype;
int flag=0,find=0;

class bitree
{public:
    elemtype data;
    bitree *lchild,*rchild;
    int ltag,rtag;
    bitree *create();
    void preorder(bitree *root);
    void inorder(bitree *root);
    void postorder(bitree *root);
    int treehigh(bitree *t);
    int leaf(bitree *t,int &n);
    int num(bitree *t);
    void lorder(bitree *t);
    void search(bitree *root,char t);
    void level(bitree *root,int lev,char t);
    /*void inth(bitree *p);
    bitree *houji(bitree *p);
    void traver(bitree *t,int lev,char x);
    int level(bitree *t,int x);*/
};
 int p=0;
 bitree *pre=NULL;
 bitree *bitree::create()
{
    bitree *root,*s,*q[100];
    int front=1,rear=0;
    char ch;
    root=NULL;
    cout<<"请输入节点的值(','为虚节点，‘#’表示结束）;"<<endl;
    cin>>ch;
    while(ch!='#')
    {
        s=NULL;
        if(ch!=',')
        {
            s=new bitree;
            s->data=ch;
            s->lchild=NULL;
            s->rchild=NULL;
        }
        rear++;
        q[rear]=s;
        if(rear==1)root=s;
        else{if((s!=NULL)&&(q[front]!=NULL))
        {
            if(rear%2==0)q[front]->lchild=s;
            else q[front]->rchild=s;}
        if(rear%2==1)front++;
        }
        cin>>ch;
    }
    return root;
}
void bitree::preorder(bitree *root)
{
    bitree *p;
    p=root;
    if(p!=NULL)
    {
        cout<<p->data<<" ";
        preorder(p->lchild);
        preorder(p->rchild);
    }
}
void bitree::inorder(bitree *root)
{
    bitree *p;
    p=root;
    if(p!=NULL)
    {
        
        inorder(p->lchild);
        cout<<p->data<<" ";
        inorder(p->rchild);
    }
}
void bitree::postorder(bitree *root)
{
    bitree *p;
    p=root;
    if(p!=NULL)
    {
        
        postorder(p->lchild);
        postorder(p->rchild);
        cout<<p->data<<" ";
    }
}
int bitree::treehigh(bitree *t)
{
    if(t==NULL) return 0;
    else
    {int ln,rn;
     ln=treehigh(t->lchild);
     rn=treehigh(t->rchild);
     if(ln>rn)return 1+ln;
     else return 1+rn;
    }
}
int bitree::leaf(bitree *t,int &n)
{if(t!=NULL)
{if((t->lchild==NULL)&&(t->rchild==NULL))
 n++;
n=leaf(t->lchild,n);
n=leaf(t->rchild,n);
}
return n;
}
int bitree::num(bitree *t)
{if(t==NULL) return 0;
else return 1+num(t->lchild)+num(t->rchild);
} 
void bitree::lorder(bitree *t)
{bitree *q[100],*p;
int f,r;
q[1]=t;f=r=1;
cout<<"按层次遍历二叉树的结果为:\n";
while(f<=r)
{p=q[f];f++;
 cout<<p->data<<" ";
 if(p->lchild!=NULL)
 {r++;q[r]=p->lchild;}
  if(p->rchild!=NULL)
 {r++;q[r]=p->rchild;}
}
cout<<endl;
}
void bitree::search(bitree *root,char t)
{
    bitree *p;
    p=root;
    if((p!=NULL)&&(!flag))
    {
        if(p->data==t)
        {
            flag=1;
            cout<<"查找成功"<<endl;
            
        }
        else
        {    
                search(p->lchild,t);
            
            
                search(p->rchild,t);
            
        }
    }

}
void bitree::level(bitree *root,int lev,char t)
{
    if(root!=NULL){
        lev++;
        if(root->data==t)
        {find=lev;cout<<find<<endl;}
        else
        {
         level(root->lchild, lev, t);
         if(find==0)
         level(root->rchild, lev, t);
        }
    }
}
  
void main()
{   int n=0;
    bitree *root,s,*q;
    char x;
    root=s.create();
    cout<<"先序遍历的结果"<<endl;
    s.preorder(root);
    cout<<endl;
    cout<<"中序遍历的结果"<<endl;
    s.inorder(root);
    cout<<endl;
    cout<<"后序遍历的结果"<<endl;
    s.postorder(root);
    cout<<endl;
    cout<<"树的高度为\n";
    cout<<s.treehigh(root)<<endl;
    cout<<"树的叶子数目为\n";
    cout<<s.leaf(root,n)<<endl;
    cout<<"树的节点数目\n";
    cout<<s.num(root)<<endl;
    s.lorder(root);
    cout<<"要查询的元素:";
    char t;
    cin>>t;
    s.search(root,t);
    cout<<"要查询的元素:";
    char r;cin>>r;
    while(1)
    {
    
    cout<<r<<"元素所在的层数为:";
    s.level(root,0, r);
    find=0;
    cout<<"要查询的元素:";
    cin>>r;
    }
}