#include?
#include?
#include?
#define?MAXSIZE?100
using?namespace?std;

struct?TreeNode
{
???char?data;
???TreeNode?*lchild*rchild;
};

void?CreateBiTree（TreeNode?*&char?[]）;????//用字符串建樹
void?preorder（TreeNode?*&）;????????????????//二叉樹遞歸遍歷前序
void?inorder（TreeNode?*&）;?????????????????//二叉樹遞歸遍歷中序
void?postorder（TreeNode?*&）;???????????????//二叉樹遞歸遍歷后序
int?count（TreeNode?*&）;????????????????????//葉子計數?
int?TreeHigh（TreeNode?*&）;?????????????????//遞歸求樹高?
void?Exchange（TreeNode?*&）;????????????????//二叉樹左右子樹交換?
void?CopyTree（TreeNode?*&TreeNode?*&）;???//二叉樹拷貝目的二叉樹t源二叉樹s
void?ReadyStack（void）;??????????????????????//棧初實例化?
void??preorder1（TreeNode?*）;???????????????//非遞歸的前序遍歷（利用棧實現）
void??inorder1（TreeNode?*）;????????????????//非遞歸的中序遍歷（利用棧實現）
void?postorder1（TreeNode?*）;???????????????//非遞歸的后序遍歷（利用棧實現）
void?set（TreeNode?*&char?[]char?[]intintintint）;//有前序和中序遍歷序列，用遞歸方法建樹?

int?main（void）
{
???char?*s;
???s=“ABC**DE*G**F***“;
//???cout<<“按先序遍歷序列遍歷二叉樹，其中空用*號代替:“;?
//???cin>>s;
???TreeNode?*tree;
???cout<<“用前序字符串序列?“<???CreateBiTree（trees）;
???cout<???cout<???cout<???cout<???cout<???TreeNode?*ctree;
???CopyTree（ctreetree）;
???cout<???cout<???cout<???cout<???cout<???Exchange（ctree）;
???cout<???cout<???cout<???char?pre[]=“ABCDEGF“;??//前序遍歷后數組
???char?in[]=“CBEGDFA“;??//中序遍歷后數組
????cout<<“前序遍歷數組:“<????cout<<“中序遍歷數組:“<????TreeNode?*top;
????set（topprein0strlen（pre）-10strlen（in）-1）;??//重建二叉樹
???cout<<“重建二叉樹后序遍歷結果:“;???postorder1（top）;
???cout<???system（“PAUSE“）;	
???return?0;
}


void?CreateBiTree（TreeNode?*&pchar?ar[]）???//建樹?
{??char?ch;
???static?int?i;
???ch=ar[i++];
???if（ch!=‘*‘）
???{???p=new?TreeNode;
???????p->data=ch;
???????CreateBiTree（p->lchildar）;
???????CreateBiTree?（p->rchildar）;
???}
???else?p=NULL;
}

void?preorder（TreeNode?*&p）???????//二叉樹遞歸遍歷前序
{
???if（p）
???{???cout<data;
???????preorder（p->lchild）;
???????preorder（p->rchild）;
???}
}

void?inorder（TreeNode?*&p）???????//二叉樹遞歸遍歷中序
{
???if（p）
???{???inorder?（p->lchild）;
???????cout<data;
???????inorder?（p->rchild）;
???}
}

void?postorder（TreeNode?*&p）????//二叉樹遞歸遍歷后序
{
???if（p）
???{???postorder?（p->lchild）;
???????postorder?（p->rchild）;
???????cout<data;
???}
}

int?count（TreeNode?*&p）??????????????//葉子計數?
{
????int?mn;
????if（p）
????{???m=count