二叉树后序遍历(非递归)

二叉树的递归遍历算法就不用说了；在非递归算法中，后序遍历难度大，很多书上只给出思想或者几段无法直接调试的代码，甚至有些书上是错的，当时我在研究的过程中，就是按着书上错误的代码绕了好半天，几预抓狂。好在最终摸索出来了，不禁感叹很多出书人的水平真是......   这里将直接可以在编译器里调试的代码贴出来(在DEV-C++编译器中编译通过)

这里我们约定：空的节点用空格表示，按照前序遍历来创建树！

  1// main.cpp

  2#include iostream>  3usingnamespace std;
  4typedef struct node {
  5char data;
  6struct node *lchild;
  7struct node *rchild;
  8        }BiNode,*BiTree;
  9typedef struct node1{
 10        BiTree data[30];     //默认30个元素 ，这里需要一个辅助堆栈！！！ 11int top;
 12        }Stack;
 13 14void createTree(BiTree &T)   //先序递归创建树，这里注意参数的类型，T的类型是 '*&' ,如果是 '**' 代码稍加改动就OK... 15{
 16char ch;
 17     cin.get(ch).get();      //过滤输入流中每次回车产生的回车符 18if (ch=='') T=NULL;    //这里首先判断是不是空格，如果是，则为该节点赋NULL 19else{
 20            T=(BiTree)malloc(sizeof(BiNode));
 21            T->data=ch;
 22            createTree(T->lchild);
 23            createTree(T->rchild);
 24          }
 25}
 26void initstack(Stack *&st)
 27{
 28     st=(Stack *)malloc(sizeof(Stack));
 29     st->=-1;
 30}
 31bool isempty(Stack *st)
 32{
 33return st->==-1;
 34}
 35bool isfull(Stack *st)
 36{
 37return st->==19;
 38}
 39void push(Stack *st,BiTree T)
 40{
 41if (!isfull(st))
 42st->data[++st->top]=T;     //栈顶指针始终指向堆栈最上面可用的一个元素，因此入栈时候，先要将指针加1,然后再执行入栈操作！ 43else cout'已满'endl;
 44}
 45BiTree pop(Stack *st)
 46{
 47if (!isempty(st)) return st->data[st->--];
 48}
 49BiTree gettop(Stack *st)
 50{
 51if (!isempty(st)) return st->data[st->top];  //出栈时，先取出栈顶指针指向的元素，然后再将指针减1，使其指向栈中下一个可用元素！ 52}
 53void preOrderNoRe(BiTree T)          // 前序遍历 54{
 55   Stack *st;
 56   initstack(st);
 57   BiTree p;
 58   p=T;
 59while (p!=NULL||!isempty(st))
 60     {
 61while (p!=NULL)
 62           {
 63                 coutp->data'';
 64                 push(st,p);
 65                 p=p->lchild;
 66           }
 67if (!isempty(st))
 68           {
 69                       p=pop(st);
 70                       p=p->rchild;
 71           }
 72 73     }
 74}
 75void inOrderNoRe(BiTree T)       //中序遍历 76{
 77   Stack *st;
 78   initstack(st);
 79   BiTree p;
 80   p=T;
 81while (p!=NULL||!isempty(st))
 82     {
 83while (p!=NULL)
 84           {
 85                 push(st,p);
 86                 p=p->lchild;
 87           }
 88if (!isempty(st))
 89           {
 90                       p=pop(st);
 91                       coutp->data'';
 92                       p=p->rchild;
 93           }
 94 95     }
 96}
 97void postOrderNoRe(BiTree T)          //后序遍历 98{
 99     BiTree p;
100     Stack *st;
101     initstack(st);
102     p=T;
103int Tag[20];      //栈，用于标识从左（0）或右（1）返回 104while (p!=NULL ||!isempty(st))
105     {
106while (p!=NULL)
107           {
108                 push(st,p);
109                 Tag[st->top]=0;
110                 p=p->lchild;
111           }
112while (!isempty(st)&&Tag[st->top]==1)
113           {
114                 p=pop(st);
115                 coutp->data'';
116           }
117if (!isempty(st))
118           {
119                            Tag[st->top]=1;   //设置标记右子树已经访问 120                            p=gettop(st);
121                            p=p->rchild;
122           }
123elsebreak;
124     }
125}
126int main()
127{
128    cout'Enter char one by one                      hicjiajia'endl;
129    BiNode *T;
130    createTree(T);
131    coutendl;
132133    cout'preOrderNoRe:  ';preOrderNoRe(T);coutendl;
134    cout'inOrderNoRe:   ';inOrderNoRe(T);coutendl;
135    cout'postOrderNoRe: ';postOrderNoRe(T);coutendl; 
136    system('pause');
137return0;
138}

 运行结果如图：