二叉树前前后后中序遍历的非递归实现

二叉树前后中序遍历的非递归实现

其中前序和中序，简单且容易理解。后序遍历有难度。

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"


typedef struct BiNode
{
char data;
struct BiNode *lchild,*rchild;
}BiNode,*LinkBiTree;




typedef struct stack
{
LinkBiTree *elem;//开辟空间去存贮链的结点,相当于是个顺序链表
int top;
int size;//顺序栈的大小，防止溢出
}SqStack;


//栈初始化


void InitStack(SqStack &s)
{
s.elem=(LinkBiTree*)malloc(sizeof(BiNode)*100);//给这个实例化的s的栈的元素分配100大小的空间；
s.top=-1;
s.size=100;
}


void push (SqStack &s,LinkBiTree e)
{
if (s.top==99)
printf("栈满！");
else
{
s.top++;
s.elem[s.top]=e;
}
}


LinkBiTree pop(SqStack &s,LinkBiTree e)
{
if(s.top==-1)
printf("栈空！");
else
{
e=s.elem[s.top];
s.top--;
}
return e;
}


//递归算法创建二叉树


void CreatTree(LinkBiTree &T)
{
char ch;
ch=getchar();
if(ch=='#')
{
T=NULL;
return;
}
else
{
T=new BiNode;//链表式的二叉树，每一个结点都需要开辟空间给它
T->data=ch;
CreatTree(T->lchild);
CreatTree(T->rchild);
}
}


void preorder (LinkBiTree &T)
{
LinkBiTree p;//结点p
SqStack s;//栈s；
InitStack(s);//初始化栈


p=T;//同样类型的结点指针指向树结点；
if (T==NULL)//边界条件要考虑到啊
{
printf("空树！");}
while(p||!(s.top==-1))//树结点存在且栈不为空，因为不停的入栈出栈，直到所有结点都出栈才算完
{
if (p)
{
push(s,p);
printf("%c ",p->data);
p=p->lchild;//左子节点为空时，因为栈还不为空，循环会继续
}
else
{
p=pop(s,p);

p=p->rchild;
}


}
}


void midorder ( LinkBiTree &T)
{


LinkBiTree p;//结点p
SqStack s;//栈s；
InitStack(s);//初始化栈


p=T;//同样类型的结点指针指向树结点；
if (T==NULL)//边界条件要考虑到啊
{
printf("空树！");}
while(p||!(s.top==-1))//树结点存在且栈不为空，因为不停的入栈出栈，直到所有结点都出栈才算完
{
if (p)
{
push(s,p);
p=p->lchild;//左子节点为空时，因为栈还不为空，循环会继续
}
else
{

p=pop(s,p);
printf("%c ",p->data);
p=p->rchild;
}


}
  }


void backorder(LinkBiTree &T)//后序遍历比较难
{


LinkBiTree p;//结点p
SqStack s;//栈s；
InitStack(s);//初始化栈


p=T;//同样类型的结点指针指向树结点；


    int flag[100];//用于标记右子树是否已经访问。这是后序遍历难度的体现
if (T==NULL)//边界条件要考虑到啊
{
printf("空树！");
      }
else


{
while (p!=NULL || s.top!=-1)
            {
                  while (p!=NULL)
           {
                  push(s,p);
                  flag[s.top]=0;
                  p=p->lchild;
            }
            while (!(s.top==-1)&&flag[s.top]==1)
            {
                  p=pop(s,p);
                  printf("%c ",p->data);

            }
            if (!(s.top==-1))
            {
                             flag[s.top]=1;   //设置标记右子树已经访问 
                             p=s.elem[s.top];
                             p=p->rchild;
            }
            else break;
}

}
}




int main()
{
LinkBiTree t;
CreatTree(t);
printf("前序遍历：\n");
preorder(t);
printf("\n");
printf("中序遍历：\n");
midorder(t);
printf("\n");
printf("后序遍历：\n");
backorder(t);

system("pause");
return 0;
}