// tree.cpp : 定义控制台应用程序的入口点。
//
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#define Elemtype string
using namespace std;
typedef struct Node
{
    struct Node *lchilde;
    struct Node *rchilde;
    Elemtype data;
}BiNode;
void New_Tree(BiNode *&b,Elemtype str)
{
    stack <Node *> s;
    BiNode *p,*t;
    char ch;
    int i=0,k=0;
    ch=str[i];
    while(ch!='@')
    {
        switch(ch)
        {
        case'(':s.push(p);k=1;break;
        case ',':k=2;break;
        case ')':s.pop();break;
        default:{p=new BiNode();p->lchilde=p->rchilde=NULL;}
        if(b==NULL)
            b=p;
        else
        {
            if(k==1)
            {t=s.top();t->lchilde=p;}
            if(k==2)
            {t=s.top();t->rchilde=p;}
        }
        }
        ch=str[++i];
    }
}
void Tree_leaf(BiNode *b)
{
    BiNode *p;
    p=b;
    if(p->lchilde==NULL&&p->rchilde==NULL)
        cout<<p->data<<'\t';
    Tree_leaf(p->lchilde);
    Tree_leaf(p->rchilde);
}
void DispBTNode(BiNode *b)
{
    if(b!=NULL)
    {
        if(b->lchilde!=NULL&&b->rchilde1=NULL)
        {
            cout<<'(';
        DispBTNode(b->lchilde);
        }
        if(b->rchilde!=NULL)
        {
            cout<<',';
        DispBTNode(b->rchilde);
        }
        cout<<')';    
    }
}
void levelOrder(BiNode *b)
{
    if(b->lchilde==NULL&&b->rchilde==NULL)
        cout<<b->data<<',';
    levelOrder(b->lchilde);
    levelOrder(b->rchilde);
}
int BiNodeHeight(BiNode *b)
{
    int ln=0,rn=0;
    if(b==NULL)
        return 1;
    else
    {
    ln+=BiNodeHeight(b->lchilde);
    rn+=BiNodeHeight(b->rchilde);
    return ((rn<ln)?rn:ln);
    }
}
void FindNode(BiNode *b)
{
    queue<Node *> qe;
    qe.push(b);
    while(qe.size()!=0)
    {
    if(qe.front()->lchilde!=NULL) {cout<<qe.front()->data;qe.push(qe.front->lchilde);}
    if(qe.front()->rchilde!=NULL) {cout<<qe.front()->data;qe.push(qe.front->lchilde);}
    qe.pop();
    }

}

int main(void)
{
    BiNode *tree=NULL;
    Elemtype a="a(b(c,b),d(e(f,g)))@";
    New_Tree(tree,a);
    levelOrder(tree);
    DispBTNode(tree);
    BiNodeHeight(tree);
    FindNode(tree);
    return 0;
}