中序遍历的非递归算法实例
1、#include<iostream>
using namespace std;
typedef struct BiTnode//二叉树的二叉链表储存表示
{
char data;
struct BiTnode *lchild,*rchild;
}BiTnode,*BiTree;
2、typedef struct //顺序栈的储存结构
{
BiTnode *base;
BiTnode *top;
int stacksize;
}SqStack;
3、int InitStack(SqStack &S)//初始化顺序栈
{
S.base=new BiTnode[1000];
if(!S.base)exit(0);
S.top=S.base;
S.stacksize=1000;
return 1;
}
4、int StackEmpty(SqStack &S)//判断栈是否为空
{
if(S.base==S.top)
return 1;
else
return 0;
}
5、int Push(SqStack &S,BiTnode *p)//入栈
{
if(S.top-S.base==S.stacksize)return 0;
*S.top++=*p;
return 1;
}
6、int Pop(SqStack &S,BiTnode *q)//出栈
{
if(S.top==S.base)return 1;
*q=*--S.top;
return 0;
}
7、void InorderTraver(BiTree T)//中序遍历
{
SqStack S;
InitStack(S);//初始化一个空栈S
BiTnode *p,*q;
p=T;
q=new BiTnode;//申请一个节点空间，用来存放栈顶弹出的元素
while(p||!StackEmpty(S))//当p非空或者栈S非空时，执行以下操作
{
if(p) //如果p非空，则将p进栈，p指向该结点的左孩子
{
Push(S,p);
p=p->lchild;
}
else //如果p为空，则弹出栈顶元素并访问，将p指向该结点的右孩子
{
Pop(S,q);
cout<<q->data;
p=q->rchild;
}
}
}
8、void CreateBiTree(BiTree &T)//先序创建二叉树
{
char ch;
cin>>ch;
if(ch=='#')T=NULL;
else
{
T=new BiTnode;
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
9、int main()
{
BiTnode *T;
CreateBiTree(T);
InorderTraver(T);
return 0;
}
10、以“a*b-c”为实例中序遍历输出
