【文件属性】：
文件名称：非递归算法遍历二叉树程序代码
文件大小：2KB
文件格式：TXT
更新时间：2013-06-04 06:18:54
代码
#include
#include
//#define error 0
//#define OVERFLOW -1
//#define ok 1
#define MAXSIZE 100
typedef char TElemType;
typedef int Status;
typedef struct BiTNode{ //树的结点
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef BiTree datatype;
typedef struct
{
datatype data[MAXSIZE];
int top;
}sqstack;
typedef sqstack *STK;
Status CreateBiTree(BiTree *T)
{ //先序建立二叉树
char ch;
ch=getchar();
if(ch=='#') (*T)=NULL; //#代表空
else
{
(*T)=(BiTree)malloc(sizeof(BiTNode));
(*T)->data=ch;
CreateBiTree(&(*T)->lchild); //先序建立左子树
CreateBiTree(&(*T)->rchild); //先序建立右子树
}
return 1;
}
STK initstack() //栈的初始化
{
STK s;
s=(STK)malloc(MAXSIZE*sizeof(sqstack));
s->top=0;
return s; //返回指向栈地址的指针
}
Status stackempty(STK s) //判断栈是否为空
{
return(s->top==0);
}
Status push(STK s,datatype *e) //压栈函数
{
if(s->top==MAXSIZE) //栈满，则返回错误
return 0;
else
{
s->data[s->top]=*e;
(s->top)++;
return 1;
}
}
Status pop(STK s,datatype *e) //出栈函数
{
if(stackempty(s)) //判断栈是否为空
return 0;
else
{
s->top--;
*e=s->data[s->top]; //用e接受栈顶元素
return 1;
}
}
Status inordertraverse(BiTree T) //中序非递归遍历二叉树
{
STK s;
s=initstack();
// BiTree T;
BiTree p;
p=T;
while (p||!stackempty(s))
{
if(p)
{
push(s,&p);
p=p->lchild;
}
else
{
pop(s,&p);
printf("%2c",p->data);
p=p->rchild;
}//else
}//while
return 1;
}//inordertraverse
void main()
{
BiTree T=NULL;
printf("\n Creat a Binary Tree .\n"); //建立一棵二叉树T*
CreateBiTree( &T );
printf ("\nThe preorder is:\n");
inordertraverse(T);
}
