C语言实现二叉树的前序、中序、后续遍历(非递归法).doc

文档介绍：二叉树的前序遍历、中序遍历、后续遍历
(非递归法)
1、前序遍历(非递归):
#include<>
#include<>
struct BiTNode *stack[100];
struct BiTNode//定义结构体
{
char data;
struct BiTNode *lchild,*rchild;
};
void later(struct BiTNode *&p) //前序创建树
{
char ch;
scanf("%c",&ch);
if(ch==' ')
p=NULL;
else
{
p=(struct BiTNode *)malloc(sizeof(struct BiTNode));
p->data=ch;
later(p->lchild);
later(p->rchild);
}
}
void print(struct BiTNode *p) //前序遍历(输出二叉树)
{
int i=-1;
while(1)
{
while(p!=NULL)
{
stack[++i]=p->rchild;/*printf("ok?\n");*/
printf("%c",p->data);
p=p->lchild;
}
if(i!=-1)
{
p=stack[i];
i--;
}
else
return;
}
}
void main()//主函数
{
struct BiTNode *p,*t;
later(p);
print(p);
}
2、中序遍历(非递归)
#include<>
#include<>
struct BiTNode *stack[100];
struct BiTNode//定义结构体
{
char data;
struct BiTNode *lchild,*rchild;
};
void later(struct BiTNode *&p) //前序创建树
{
char ch;
scanf("%c",&ch);
if(ch==' ')
p=NULL;
else
{
p=(struct BiTNode *)malloc(sizeof(struct BiTNode));
p->data=ch;
later(p->lchild);
later(p->rchild);
}
}
void print(struct BiTNode *p) //中序遍历(输出二叉树)
{
int i=-1;
while(1)
{
while(p!=NULL)
{
i++;
stack[i]=p;
p=p->lchild;
}
if(i!=-1)
{
p=stack[i];
i--;
printf("%c",p->data);
p=p->rchild;
}
}
}
void main()//主函数
{
struct BiTNode *p;
later(p);
print(p);