#include<iostream>
using namespace std;
typedef char ElemType;
struct BTreeNode
{ ElemType data;
BTreeNode *leftChild;
BTreeNode *rightChild;
};

void InitTree(BTreeNode* T)
{
T=NULL;
}

void DestroyTree(BTreeNode* T)
{
if(T!=NULL) {
DestroyTree(T->leftChild);
DestroyTree(T->rightChild);
delete T;
}

}

void CreateBiTree(BTreeNode* &T)
{ ElemType mark;
cin>>mark;
if(mark=='$') T=NULL;
else {
T=new BTreeNode;
T->data=mark;
CreateBiTree(T->leftChild);
CreateBiTree(T->rightChild);
}
}

void InOrder(BTreeNode* T )
{
if(T!=NULL)
{
InOrder(T->leftChild);
cout<<T->data;
InOrder(T->rightChild);
}
}

void main()
{
BTreeNode *T=new BTreeNode;
InitTree(T);
cout<<"按先序序列輸入:"<<endl;
cout<<"例如輸入ABC$$DE$G$$F$$$"<<endl;
CreateBiTree(T);
cout<<"按中序序列輸出："<<endl;
InOrder(T );
cout<<endl;
DestroyTree(T);
}