二叉树非递归遍历代码

xuanke(int qq,int ww,char ee[30],int a,char b[30],char c[30],int d,char x[30],
char v[30],char t[30],float uu,float ii,float oo,float pp):Person(a,&b[30],&c[30],d),teachar(a,&b[30],&c[30],d,&x[30],&v[30],&t[30]),
student(a,&b[30],&c[30],d,uu,ii,oo,pp)#include
using namespace std;
#define MaxSize 100//最多100个字符
typedef struct node
{
char data;
struct node *lchild;
struct node *rchild;
}BTNode;
void CreateBTNode(BTNode *&b,char *str)
{
BTNode *St[MaxSize],*p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL; //建立二叉树时
ch=str[j];
while(ch!='\0')//str未扫描完循环
{
switch(ch)
{
case'(':top++;St[top]=p;k=1;break;//为左结点
case')':top--;break;
case',':k=2;break; //为右结点
default:p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
if(b==NULL)
b=p; //p指向二叉树根节点
else //已建立二叉树
{
switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;
ch=str[j];
}
}
void PreOrder(BTNode *b) //先序遍历
{
BTNode *St[MaxSize],*p;
int top=-1;
if(b!=NULL)
{
top++;
St[top]=b;
while(top>-1) //栈不空循环
{
p=St[top]; //出栈并访问改结点
top--;
cout<data;
if(p->rchild!=NULL) //右孩子入栈
{
top++;
St[top]=p->rchild;
}
if(p->lchild!=NULL) //左孩子入栈
{
top++;
St[top]=p->lchild;
}
}
cout<}
}
void InOrder(BTNode *b)
{
BTNode *St[MaxSize],*p;
int top=-1;
if(b!=NULL)
{
p=b;
while(top>-1||p!=NULL)
{
while(p!=NULL) //栈不空循环
{
top++;
St[top]=p;
p=p->lchild; //P指向最左边的叶子
}
if(top>-1) //将最左边叶子出栈
{
p=St[top];
top--; //指向已出栈叶子结点的父亲
cout<data; //出栈最左边结点
p=p->rchild;
}
}
cout<}
}
void PostOrder(BTNode *b) //后序遍历
{
BTNode *St[MaxSize],*p;
int f,top=-1; //栈指针置初值
if(b!=NULL)
{
do
{
while(b!=NULL) //将b的所有左节点入栈
{
top++;
St[top]=b;
b=b->lchild;
}
p=NULL; //p指向当前节点的前一个已访问的结点
f=1; //设置b的访问标记为已访问过
while(top!=-1&&f)
{
b=St[top]; //取出当前栈顶元素
if(b->rchild==p)//右子树不存在或已访问，访问之
{
cout<data;//访问*b节点
top--;
p=b; //p指向刚被访问的结点
}
else
{
b=b->rchild; //t指向右子树
f=0; //设置未被访问过的标记
}
}
}
while(top!=-1);
cout<}
}


void main()
{
BTNode *b;
char s[100];
cout<<"请输入一个二叉树：";
gets(s);
CreateBTNode(b,s);
cout<<"前序遍历；";
PreOrder(b);
cout<<"中序遍历

；";
InOrder(b);
cout<<"后序遍历；";
PostOrder(b);
}
//测试数据：A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))