非递归对二叉树的遍历操作-栈实现

#include <stdio.h>
#include <stdlib.h>

typedef char elemtype;

/*结构体声明*/
typedef struct bitnode{
elemtype ch;
struct bitnode *lchild,*rchild;
}bitnode,*bitree;

/*

*/
bitnode *creat(){
bitnode *t,*s,*p[30];? //t保存二叉树的根节点，s不断分配节点，数组p保存各个节点
char ch;? //二叉树节点的数据域
int i,j;
scanf(“%d%c”,&i,&ch);
while(i!=0)
{
s=(bitnode *)malloc(sizeof(bitnode));
s->ch=ch;??? //将ch保存在节点数据域中
s->lchild=s->rchild=NULL;? //初始化左右子树为空
p[i]=s;???? //将节点s保存数组
if(i==1)??? //如果是第一个节点
t=s;?? // 则让t保存第一个节点
else
{
j=i/2;??? // 如果i不是1，则j保留左右子树在数组中位置（比如:i=2,3 则j=1，p[j]->lchild,p[j]->rchild为左右子树）

if(i%2==0)???? //判断左右子树，偶数为左子树，奇数为右子树.
p[j]->lchild=s;
else
p[j]->rchild=s;

}
scanf(“%d%c”,&i,&ch);
}
return t;

}

void preorder(bitree T)? //栈实现二叉树的前序遍历
{
int top=-1;?? //初始化栈顶指针为-1
bitree elem[30];
bitree p=T;

while(p!=NULL||top!=-1)? //遍历结束条件p为空，“并且”栈为空
if(p!=NULL)? //若p不为空
{
printf(“%c “,p->ch);??? ??? //输出第节点，并且将节点入栈
top++;
elem[top]=p;?? //入栈
p=p->lchild;??? //继续访问p的左子树

}
else? //如果访问的p为空
{
p=elem[top];?? //则（出栈）返回上一节点，并继续访问右子树
top–;
p=p->rchild;
}
}

void inorder(bitree T)
{
int top=-1;
bitree elem[30];
bitree p=T;

while(p!=NULL||top!=-1)? //基本和前序遍历原理一样
{
while(p!=NULL)?? //若p不为空
{

top++;???? //将节点入栈，并一直访问左子树
elem[top]=p;
p=p->lchild;
}

if(p==NULL)? //直到p节点为空
{
p=elem[top];

top–;
printf(“%c “,p->ch);? //出栈，并输出p节点
p=p->rchild;? //再继续访问右节点

}
}
}

int? main()
{
bitree T;
T=creat();
printf(“前序:”);
preorder(T);
printf(“\n中序:”);
inorder(T);
return 0;
}