#include <iostream>
#include <iomanip>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define NO 0
int totall=0;                //树中结点总数
int yezi=0;                  //叶子接点总数
struct Tree
{
    char date;
    struct Tree *Lchild;
    struct Tree *Rchild;
};
struct Stack               // 栈结构体
{
    Tree elem[MAXSIZE];
    int top;
};
void Init_Tree(Tree *T)    //树初始化
{
    T->Lchild=NULL;
    T->Rchild=NULL;
}
void Init_Stack(Stack *S)   //栈的初始化
{
    S->top=-1;
}
int IsEmpty(Stack *S)
{
    return (S->top==-1?OK:NO);
}
void Creat_Tree(Tree *T)     //先序建立一棵树
{
    char ch;
    cin>>ch;
    if(ch=='/')
        return ;
    totall++;
    if(ch=='.')
    {
        T=NULL;
        return ;
    }
   
    else
    {
        T=new Tree;
        T->date=ch;
        Init_Tree(T);
        Creat_Tree(T->Lchild);            //就像递归调用建立树
        Creat_Tree(T->Rchild);
    }

}
void Visit(char x)
{
    cout<<x;
}
void pop(Stack *s,Tree *T)     //取栈顶元素
{
    *T=s->elem[s->top];
    s->top--;
    yezi++;

}
void push(Stack *s,Tree *T)
{
    s->top++;
    s->elem[s->top]=*T;
   
}
void InOrder(Tree *T)            //中序遍历(非递归，调用栈)
{   
    Stack S;
    Init_Stack(&S);
    Tree *p=T;
    while(p!=NULL || !IsEmpty(&S))
    {
        if(p!=NULL)
        {
            //cout<<p->date<<endl;
            push(&S,p);
            p=p->Lchild;
        }
        else
        {
            pop(&S,p);
            Visit(p->date);
            p=p->Rchild;
        }
    }
}
void dele(Tree *root)     //释放空间()
{
    if(root!=NULL)
    {
        dele(root->Lchild);
        dele(root->Rchild);
        delete root;             //当左右子结点都为空时，dele释放空间
    }

}
void welcom()          //无聊的欢迎界面
{
    cout<<"========================================= "<<endl;
    cout<<"         欢迎使用小白制作                 "<<endl;
    cout<<"┏━━━━━━━━━━━━━━━━━━━┓"<<endl;
    cout<<"┃  输入的格式为ABC..DE.G..F../         ┃"<<endl;
    cout<<"┃  使用“.“代表空格                   ┃"<<endl;
    cout<<"┃  请以字符“/”结束                   ┃"<<endl;
    cout<<"┃                                      ┃"<<endl;
    cout<<"┗━━━━━━━━━━━━━━━━━━━┛"<<endl;
    cout<<"┃ 还是1.00版本    2011/11/06           ┃"<<endl;
    cout<<"========================================= "<<endl;
    cout<<"   请输入要测试的字符:"<<" ";
}
void xianshi()
{
    cout<<"   树总共有结点数:"<<totall<<endl;
    cout<<"   树总共有叶子数:"<<yezi<<endl;
}
int main()
{
    Tree T;
    welcom();
    Creat_Tree(&T);
    cout<<"  以下是非用递归打印出来结果"<<endl;
    InOrder(&T);
    cout<<"  以下是用递归打印树"<<endl;
    //diorder(&T);
    dele(&T);
    xianshi();
    return 0;
}