以二叉链表为存储结构，分别写出前序、中序、后序遍历二叉树的递归与非递归算法。（数据结构）

#include
#include

typedef char ElemType;

struct BTreeNode
{
ElemType data;
BTreeNode*left;
BTreeNode*right;
};

void InitBTree(BTreeNode*& BT)
{
BT=NULL;
}
void CreateBTree(BTreeNode*& BT,char*a)
{
const int MaxSize=1000;
BTreeNode*s[MaxSize];
int top=-1;
BT=NULL;
BTreeNode*p;
int k;
int i=0;
while (a[i])
{
switch(a[i])
{
case ' ':
break;
case'(':
if(top==MaxSize-1)
{
cout<<"栈空间太少，请增加MaxSize的值！"< exit(1);
}
top++; s[top]=p;k=1;
break;
case ')':
if(top==-1)
{
cout<<"二叉树的广义表出错!"< }
top--;
break;
case ',':
k=2;
break;
default:
p=new BTreeNode;
p->data=a[i];p->left=p->right=NULL;
if(BT==NULL) BT=p;
else
{
if(k==1) s[top]->left=p;
else s[top]->right=p;
}
}
i++;
}
}
bool EmptyBTree (BTreeNode*BT)
{
return BT==NULL;
}
void PreOrder(BTreeNode* BT)
{
if(BT!=NULL)
{
cout<data<<' ';
PreOrder(BT->left);
PreOrder(BT->right);

}
}
void InOrder(BTreeNode* BT)
{
if(BT!=NULL)
{
InOrder(BT->left);
cout<data<<' ';
InOrder(BT->right);
}
}
void PostOrder(BTreeNode* BT)
{
if(BT!=NULL)
{
PostOrder(BT->left);
PostOrder(BT->right);
cout<data<<' ';
}
}
void LevelOrder(BTreeNode* BT)
{
const int MaxSize=30;
BTreeNode* q[MaxSize];
int front=0,rear=0;
BTreeNode* p;
if(BT!=NULL)
{
rear=(rear+1)%MaxSize;
q[rear]=BT;
}
while (front!=rear)
{
front=(front+1)%MaxSize;
p=q[front];
cout<data<<' ';
if(p->left!=NULL)
{
rear=(rear+1)%MaxSize;
q[rear]=p->left;
}
if(p->right!=NULL)
{
rear=(rear+1)%MaxSize;
q[rear]=p->right;
}
}
}
void PrintBTree(BTreeNode*BT)
{
if(BT!=NULL)
{
cout<data;
if(BT->left!=NULL || BT->right!=NULL )
{
cout<<'(';
PrintBTree(BT->left);
if(BT->right!=NULL)
cout<<',';
PrintBTree(BT->right);
cout<<')';
}
}
}
void ClearBTree(BTreeNode*&BT)
{
if(BT!=NULL)
{
ClearBTree(BT->left);
ClearBTree(BT->right);
delete BT;
BT=NULL;
}
}

void main()
{
BTreeNode* bt;
InitBTree(bt);
char b[50];
cout<<"输入二叉树的广义表字符串"< cin.getline(b,sizeof(b));
CreateBTree(bt,b);
PrintBTree(bt); cout< cout<<"前序："; PreOrder(bt);cout< cout<<"中序："; InOrder(bt); cout< cout<<"后序: "; PostOrder(bt); cout< cout<<"按层："; LevelOrder(bt); cout<
}