#include <iostream.h>
#include <malloc.h>
#include <iomanip.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define length 50
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int CreateBiTree(BiTree &BT) //先序次序输入二叉树中节点的值，空格表示空树
{
char ch;
cin>>ch;
if (ch== '/') BT=NULL;
else
{
BT=(BiTNode *)malloc(sizeof(BiTNode)); //构造新结点
BT->data=ch;
CreateBiTree(BT->lchild); //构造左子树
CreateBiTree(BT->rchild); //构造右子树
}
return OK;
}
//先序遍历
void PreTraverse(BiTree BT)
{
if(BT!=NULL)
{
cout<<BT->data;
PreTraverse(BT->lchild);
PreTraverse(BT->rchild);
}
}
// 中序遍历
void InTraverse(BiTree BT){
if (BT!=NULL){
InTraverse(BT->lchild);
cout<<BT->data;
InTraverse(BT->rchild);
}
}
//后序遍历
void LastTraverse(BiTree BT){
if (BT!=NULL){
LastTraverse(BT->lchild);
LastTraverse(BT->rchild);
cout<<BT->data;
}
}
//层次遍历
void LevelTraverse(BiTree BT){
BiTree array[length],pos;
int front,end; //头尾指针
array[1]=BT;
front=end=1;
while (front<=end){ //出队
pos=array[front];
front++;
cout<<pos->data<<" ";
if(pos->lchild!=NULL)
{
end++;
array[end]=pos->lchild;
}
if(pos->rchild!=NULL)
{
end++;
array[end]=pos->rchild;
}
}
}
void main()
{
int x=0;
int count1=0,count2=0;
BiTree BT;
cout<<"please input the value of node"<<endl;
CreateBiTree(BT);
if(BT==NULL)
cout<<"The BiTree is Empty."<<endl;
else{
cout<<"先序遍历为"<<endl;
PreTraverse(BT);
cout<<endl;

cout<<"中序遍历为"<<endl;
InTraverse(BT);
cout<<endl;

cout<<"后序遍历为"<<endl;
LastTraverse(BT);
cout<<endl;

cout<<"层次遍历为:"<<endl;
LevelTraverse(BT);
cout<<endl;
}
}