#include<iostream>
using namespace std;
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
    ElemType data;
    int ltag,rtag;
    struct node *lchild;
    struct node *rchild;
}TBTNode;


void CreateTBTNode(TBTNode *&b,char *str)
{
    TBTNode *St[MaxSize],*p=NULL;
    int top=-1,k,j=0;
    char ch;
    b=NULL;
    ch=str[j];
    while(ch!='\0')
    {
        switch(ch)
        {
        case '(': top++;St[top]=p;k=1;break;
        case ')': top--;break;
        case ',': k=2;break;
        default: p=(TBTNode *)malloc(sizeof(TBTNode));
                 p->data=ch;p->lchild=p->rchild=NULL;
            if(b==NULL)
                b=p;
            else
            {
                switch(k)
                {
                case 1:St[top]->lchild=p;break;
                case 2:St[top]->rchild=p;break;
                }
            }
        }
        j++;
        ch=str[j];
    }
}


void DispTBTNode(TBTNode *b)
{
    if(b!=NULL)
    {
        cout<<b->data;
        if(b->lchild!=NULL||b->rchild!=NULL)
        {
            cout<<"(";
            DispTBTNode(b->lchild);
            if(b->rchild!=NULL) cout<<",";
            DispTBTNode(b->rchild);
            cout<<")";
        }
    }
}


TBTNode *pre;
void Thread(TBTNode *&p)
{
    if(p!=NULL)
    {
        Thread(p->lchild);
        if(!p->lchild)
        {
            p->lchild=pre;
            p->ltag=1;
        }
        else p->ltag=0;
        if(pre->rchild==NULL)
        {
            pre->rchild=p;
            pre->rtag=1;
        }
        else 
        pre->rchild=0;
        pre=p;
        Thread(p->rchild);
    }
}


TBTNode *CreaThread(TBTNode *b)
{
    TBTNode *root;
    root=(TBTNode *)malloc(sizeof(TBTNode));
    root->ltag=0;root->rtag=1;
    root->rchild=root;
    if(b==NULL)
        root->lchild=root;
    else
    {
        root->lchild=b;
        pre=root;
        Thread(b);
        pre->rchild=root;
        pre->rtag=1;
        root->rchild=pre;
    }
    return root;
}


void ThInOrder(TBTNode *tb)
{
    TBTNode *p=tb->lchild;
    while(p!=tb)
    {
        while(p->ltag==0) p=p->lchild;
        cout<<p->data;
        while(p->rtag==1&&p->rchild!=tb)
        {
            p=p->rchild;
            cout<<p->data;
        }
        p=p->rchild;
    }
}


int main()
{
    TBTNode *b,*tb;
    CreateTBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
    cout<<"二叉树"<<endl;
    DispTBTNode(b);cout<<endl;
    cout<<"********"<<endl;
    tb=CreaThread(b);
    cout<<"%%%%%%%%"<<endl;
    ThInOrder(tb);
    cout<<"#######";
    cout<<endl;
    return 0;
}