怎样用栈实现二叉树的中序遍历
#include<iostream>
using namespace std;
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
#define OVERFLOW -1
typedef char TElemType ;
typedef char SElemType ;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
void InitStack(SqStack &S){
char *base;
S.base=new SElemType[MAXSIZE];
if(!base)
exit(OVERFLOW);
S.top=S.base;
S.stacksize=MAXSIZE;
}
void Push(SqStack &S,SElemType e){
if(S.top-S.base==S.stacksize)
cout<<"栈满!\n";
*S.top++=e;
}
void Pop(SqStack &S,SElemType &e){
if(S.top==S.base)
cout<<"栈空!\n";
e=*--S.top;
}
void CreatBiTree(BiTree &T)
{
char ch;
cin>>ch;
if(ch=='#')
T=NULL;
else{
T=new BiTNode;
T->data=ch;
CreatBiTree(T->lchild);
CreatBiTree(T->rchild);
}
}
void InOrderTraverse(BiTree T)
{
SqStack S;
BiTree p;
InitStack(S);
p=T;
BiTNode *q=new BiTNode;
while(p!=NULL){
if(p)
{Push(S,p);
p=p->lchild;}
else
{Pop(S,q);
cout<<q->data;
p=q->rchild;}
}
}
void main()
{
BiTree T;
cout<<"建立二叉树:\n";
CreatBiTree(T);
cout<<"二叉树为:\n";
InOrderTraverse(T);
}