#include<iostream>
#include<string>
using namespace std;
#define MAXNODE 100
typedef struct Binnode
{
char data;
struct Binnode *lchild,*rchild;
}Binnode,*Bintree; //定义结点类型
typedef struct
{
Bintree link;
int flag;
}stacktype; //定义进入栈的指针节点类型
void Creat_Bintree(Bintree &root)
{
char ch;
if((ch=getchar())=='#') //从键盘上输入二叉树的结点数值,若是‘#’表示输入的是空树
{
root=NULL;
}
else
{
root=new Binnode; //生成结点
if(!root)exit(0);
root->data=ch;
Creat_Bintree(root->lchild); //构造左子树
Creat_Bintree(root->rchild); //构造右子树
}
}
//=========================================================================递归算法遍历
void Preorder(Bintree bt)
{
if(bt)
{
cout<<bt->data;
Preorder(bt->lchild);
Preorder(bt->rchild);
}
}//先序遍历
void Inorder(Bintree bt)
{
if(bt)
{
Inorder(bt->lchild);
cout<<bt->data;
Inorder(bt->rchild);
}
}//中序遍历
void Posorder(Bintree bt)
{
if(bt)
{
Posorder(bt->lchild);
Posorder(bt->rchild);
cout<<bt->data;
}
}
//==============================================================================非递归算法遍历
void NRPreorder( Bintree bt)
{
Bintree stack[MAXNODE],p;
int top;
if(bt==NULL) return;
top=0;
p=bt;
while(!(p==NULL&&top==0))
{
while(p!=NULL)
{
cout<<p->data;
if(top<(MAXNODE-1))
{
stack[top]=p;
top++;
}
else
{
cout<<"error!";
return;
}
p=p->lchild;
}
if(top<=0) return;
else
{
top--;
p=stack[top];
p=p->rchild;
}
}
} //先序遍历
void NRInorder(Bintree bt)
{
Bintree stack[MAXNODE],p;
int top;
if(bt==NULL) return;
top=0;
p=bt;
while(!(p==NULL&&top==0))
{
while(p!=NULL)
{
if(top<(MAXNODE-1))
{
stack[top]=p;
top++;
}
else
{
cout<<"error!";
return;
}
p=p->lchild;
}
if(top<=0) return;
else
{
top--;
p=stack[top];
cout<<p->data;
p=p->rchild;
}
}
} //中序遍历
void NRPosorder(Bintree bt)
{
stacktype stack[MAXNODE];
Bintree p;
int top,sign;
if(bt==NULL) return;
top=-1; //栈顶位置初始化
p=bt;
while(!(p==NULL&&top==-1))
{
if(p!=NULL)
{ //结点第一次进栈
top++;
stack[top].link=p;
stack[top].flag=1;
p=p->lchild; //找到该结点的左孩子
}
else
{
p=stack[top].link;
sign=stack[top].flag;
top--;
if(sign==1) //结点第二次进栈
{
top++;
stack[top].link=p;
stack[top].flag=2; //标记第二次出栈
p=p->rchild;
}
else
{
cout<<p->data; //访问该结点数据域值
p=NULL;
}
}
}
} //后序遍历
void main()
{
Bintree bt;
cout<<"建立二叉树,请输按先序序列输入一串字符,当子树为空时,用#来代替:"<<endl;
Creat_Bintree(bt);
cout<<endl;
cout<<"先序遍历二叉树的递归算法结果为:";
Preorder(bt);
cout<<endl;
cout<<"中序遍历二叉树的递归算法结果为:";
Inorder(bt);
cout<<endl;
cout<<"后序遍历二叉树的递归算法结果为:";
Posorder(bt);
cout<<endl;
cout<<"先序遍历二叉树的非递归算法结果为:";
NRPreorder(bt);
cout<<endl;
cout<<"中序遍历二叉树的非递归算法结果为:";
NRInorder(bt);
cout<<endl;
cout<<"后序遍历二叉树的非递归算法结果为:";
NRPosorder(bt);
cout<<endl;
}