二叉树的递归与非递归遍历（二叉链表结构）

       # include <stdio.h>
       # include <iostream.h>
       # include <malloc.h>
       # include <stdlib.h>
       # define STACK_INIT_SIZE 100
       # define STACKINCREMENT 10
       # define OK 1
       # define ERROR 0
       # define OVERFLOW -1
       typedef char TElemtype;
       typedef struct BiTNode
       {
        TElemtype data;
       struct BiTNode *lchild,*rchild;
       }BiTNode,*BiTree;
       typedef struct
       {
        BiTree *top;
        BiTree *base;
       int stacksize;
       }SqStack;
       int Init_Stack(SqStack &S)
       {
        S.base = (BiTree *) malloc (STACK_INIT_SIZE * sizeof (BiTree));
       if (!S.base)
        exit (OVERFLOW);
        S.top = S.base;
        S.stacksize = STACK_INIT_SIZE;
       return OK;
       }
       int GetTop(SqStack S,BiTree &e)
       {
       if (S.base == S.top )
        return ERROR;
        e = *(S.top -1);
       return OK;
       }
       int StackEmpty(SqStack S)
       {
       if (S.top == S.base )
        return OK;
       else
        return ERROR;
       }
       int Push(SqStack &S,BiTree e)
       {
       if (S.top - S.base >= S.stacksize )
        {
         S.base = (BiTree *)realloc (S.base,(S.stacksize + STACKINCREMENT)*sizeof (BiTree));
        if (!S.base)
         exit (OVERFLOW);
         S.top = S.base + S.stacksize;
         S.stacksize += STACKINCREMENT;
        }
        *S.top++ = e;
       return OK;
       }
       int Pop(SqStack &S,BiTree &e)
       {
       if (S.top == S.base )
        return ERROR;
        e = * --S.top;
       return OK;
       }
       int CreateBiTree(BiTree &T)
       {
        TElemtype ch;
       cin>>ch;
       if (ch == '#')
         T = NULL;
       else
        {
         T = (BiTNode *) malloc (sizeof (BiTNode));
        if (!T)
         exit (OVERFLOW);
         T->data = ch;
         CreateBiTree(T->lchild);
         CreateBiTree(T->rchild);
        }
       return OK;
       }
       void PreOrderTraverse (BiTree T)
       {
       if (T)
        {
        cout<<T->data ;
         PreOrderTraverse(T->lchild);
         PreOrderTraverse(T->rchild);
        }
       }
       void InOrderTraverse (BiTree T)
       {
       if (T)
        {
         InOrderTraverse(T->lchild);
        cout<<T->data;
         InOrderTraverse(T->rchild);
        }
       }
       void PostOrderTraverse (BiTree T)
       {
       if (T)
        {
         PostOrderTraverse(T->lchild);
         PostOrderTraverse(T->rchild);
        cout<<T->data ;
        }
       }
       void PreOrderTraverse1 (BiTree T)
       {
        SqStack S;
        BiTree p;
        Init_Stack(S);
        Push(S,T);
       while (! StackEmpty(S))
        {
        while (GetTop(S,p) && p)
         {
         cout<<p->data ;
          Push(S,p->lchild);
         }
         Pop(S,p);
        if (!StackEmpty(S))
         {
          Pop(S,p);
          Push(S,p->rchild);
         }
        }
       }
       void InOrderTraverse1 (BiTree T)
       {
        SqStack S;
        BiTree p;
        Init_Stack(S);
        Push(S,T);
       while (! StackEmpty(S))
        {
        while (GetTop(S,p) && p)
          Push(S,p->lchild);
         Pop(S,p);
        if (!StackEmpty(S))
         {
          Pop(S,p);
         cout<<p->data ;
          Push(S,p->rchild);
         }
        }
       }
       void PostOrderTraverse1(BiTree T)
       {//本源码来源于网络
        SqStack S;
        BiTree p, p1;
        p = T;
        p1 = NULL;
        Init_Stack(S);
       while(p || !StackEmpty(S))
        {
        if(p){
          Push(S,p);
         //visit,先序
          p=p->lchild;
         }
        else
         {
          GetTop(S,p);
         //visit,中序
         if(p->rchild==p1)
          {
        Pop(S,p1);p=NULL;
       //visit,后序
       cout<<p1->data;
          }
         else
          {
        p=p->rchild;p1=NULL;
          }
         }
        }
       }
       int main(void)
       {
        BiTree T;
       cout<<"请按照先序序列建立一棵二叉树，#代表空树!"<<endl;
        CreateBiTree(T);
       cout<<"先序遍历二叉树:";
        PreOrderTraverse(T);
       cout<<endl;
       cout<<"中序遍历二叉树:";
        InOrderTraverse(T);
       cout<<endl;
       cout<<"后序遍历二叉树:";
        PostOrderTraverse(T);
       cout<<endl;
       cout<<"非递归先序遍历二叉树:";
        PreOrderTraverse1(T);
       cout<<endl;
       cout<<"非递归中序遍历二叉树:";
        InOrderTraverse1(T);
       cout<<endl;
       cout<<"非递归后序遍历二叉树:";
        PostOrderTraverse(T);
       cout<<endl;
       return 0;
       }
   
  





 运行结果：

文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq523176585/article/details/6758451