利用栈的二叉树非递归后序遍历

gistfile1.txt

/**********
【题目】试利用栈及其基本操作写出二叉树T的非递归
的后序遍历算法(提示：为分辨后序遍历时两次进栈的
不同返回点，需在指针进栈时同时将一个标志进栈）。
二叉链表类型定义：
typedef struct BiTNode {
  TElemType  data;
  struct BiTNode  *lchild,*rchild;
} BiTNode, *BiTree;
可用栈类型Stack的相关定义：
typedef struct {
  struct BiTNode *ptr; // 二叉树结点的指针类型
  int      tag; // 0..1
} SElemType;    // 栈的元素类型
Status InitStack(Stack &S); 
Status StackEmpty(Stack S); 
Status Push(Stack &S, SElemType e);
Status Pop(Stack &S, SElemType &e); 
Status GetTop(Stack S, SElemType &e); 
**********/   
void PostOrder(BiTree T, void (*visit)(TElemType))
/* 使用栈，非递归后序遍历二叉树T，     */
/* 对每个结点的元素域data调用函数visit */
{
 Stack S;
 InitStack(S);
 SElemType e;
 BiTree p = T;
 int tag = 0;
 if(T) {
     e.tag = 0;
     while(!StackEmpty(S) || p == T) {
         while(p && !tag) {       
             e.ptr = p;
             if(p -> lchild) {
                 p = p -> lchild;
                 e.tag = 0;
             } else {
                 p = p -> rchild;
                 e.tag = 1;  // 叶子结点tag=1
             }
             Push(S, e);
         } // 向左走到底，并把结点和tag压入栈
         GetTop(S, e); // 把栈顶元素给e
         if(!StackEmpty(S) && e.tag) {  // 栈非空且该点为叶子结点
                 Pop(S, e);  // 栈S的栈顶元素出栈，并用e返回
                 p = e.ptr;
                 visit(p -> data);
         }
         if(!StackEmpty(S)) {
             Pop(S, e);  // 返回的是上一个结点
             p = e.ptr;
             if(e.tag) {   // 如果右子树已经入过栈了
                 visit(p -> data);
                 p = NULL;
             } else {     // 没有入栈
                 if(p -> rchild) {    // 有右子树
                     p = p -> rchild;
                     tag = 0;
                     e.tag = 1;
                     Push(S, e);
                 } else {             // 没有右子树
                     visit(p -> data);
                     p = NULL;
                 }
             }
         } else {   // 栈为空
             p = NULL;
         }     
     } // while(!StackEmpty(S) || p == T)
 }        
}