文章目录
算法思想
中序遍历
前序遍历
后续遍历

算法思想


借助堆栈实现前序遍历、中序遍历非递归程序的本质是利用堆栈模拟递归函数调用时的入栈和出栈过程。而前序遍历、中序遍历和后序遍历在递归函数执行时，结点（作为函数参数）的入栈和出栈过程是完全一样的。


前序遍历是在结点入栈时输出结点信息，然后开始分别对该结点左右子树的遍历；而在中序遍历中，结点出栈时表明刚完成对该结点左子树的遍历，此时可输出该结点信息。


后序遍历必须在左右子树均输出的情况下才能输出该结点。如果直接采用前序遍历、中序遍历的非递归程序，我们没法判别该结点的右子树什么时候遍历结束。为了能知道结点右子树什么时候遍历结束，可以在其左子树遍历结束时做个标记（暂不出栈），等到再次访问到它时说明其右子树刚刚遍历完毕，此时可以输出该结点。


中序遍历

遇到一个结点，就把它压栈 ，并去遍历它的左子树
当左子树遍历结束 后，从栈顶弹出这个结点并访问它
然后按其右指针再去中序遍历该结点的右子树

// 中序遍历非递归算法
void InOrderTraversal(BinTree BT)
{
    BinTree T = BT;
    Stack S = CreatStack(MaxSize); // 创建并初始化堆栈S
    while (T || !IsEmpty(S))
    {
        while (T)
        {
            // 一直向左并将沿途结点压入堆栈
            Push(S, T);
            T = T->Left;
        }
        if (!IsEmpty(S))
        {
            T = Pop(S);   // 结点弹出堆栈
            printf(“ % 5d”, T->Data); // (访问) 打印结点
            T = T->Right; // 转向右子树
        }
    }
}

前序遍历
// 前序遍历非递归算法
void PreOrderTraversal(BinTree B )
{
    BinTree T = BT;
    Stack S = CreatStack(MaxSize); // 创建并初始化堆栈S
    while (T || !IsEmpty(S))
    {
        while (T)
        {
            // 一直向左并将沿途结点压入堆栈
            Push(S, T);
            printf(“ % 5d”, T->Data); // (访问) 打印结点
            T = T->Left;
        }
        if (!IsEmpty(S))
        {
            T = Pop(S);   // 结点弹出堆栈
            T = T->Right; // 转向右子树
        }
    }
}

后续遍历
void PostOrderTraversal(Bintree BT)
{
    Bintree T = BT;
    Bintree flag = NULL;
    Bintree top;
    Stack S = CreateStack(MaxSize); // 创建并初始化堆栈S
    while (T || !IsEmpty(S))
    {
        while (T)
        {
            // 一直向左并将沿途结点压入堆栈
            push(S, T);
            T = T->Left;
        }

        // 获取栈顶元素，此时不出栈
        top = GetTop(S);

        // 此时top的左子树在上一个while循环中已访问过，当top的右子树为空或已访问过时打印top结点
        if (top->Right == NULL || top->Right == flag) 
        {
            printf("% 5d", top->Data);
            flag = pop(s);  // 用flag记录这个元素，表示已访问
        }
        else
        {
            T = top->Right;  // 若top的右子树没有被访问过，则将其当做一颗新二叉树访问
        }
    }
}

先序、中序、后序遍历的非递归算法
先序遍历
中序遍历
后序遍历

先序遍历
第一次遇到该结点时输出
	public void preOrder(TreeNode root){
		if(root==null) return;
		TreeNode p = root;
		Stack<TreeNode> stack = new Stack<>();
		while(!stack.isEmpty()||p!=null){
			//对每一棵树而言，都一直向左下走，直到走到最左下的叶子结点
			while(p!=null){
				System.out.print(p.val+"  ");	//先序遍历是第一次遇到该结点的时候输出，即结点入栈
				stack.push(p);
				p = p.left;
			}
			
			if(!stack.isEmpty()){
				p = stack.pop();
				p = p.right;	//进入最左下叶子结点的右孩子
			}
			//进入新一轮循环
		}
		
	}

中序遍历
第二次遇到该结点时输出
	public void inOrder(TreeNode root){
		if(root==null) return;
		TreeNode p = root;
		Stack<TreeNode> stack = new Stack<>();
		while(!stack.isEmpty()||p!=null){
			//对每一棵树而言，都一直向左下走，直到走到最左下的叶子结点
			while(p!=null){
				stack.push(p);
				p = p.left;
			}
			
			if(!stack.isEmpty()){
				p = stack.pop();
				System.out.print(p.val+"  ");	//中序遍历是第二次遇到该结点的时候输出，即结点出栈
				p = p.right;	//进入最左下叶子结点的右孩子
			}
			//进入新一轮循环
		}
		
	}

后序遍历
第三次遇到该结点时输出
	public static void postOrder(TreeNode root){
		if(root==null) return;
		TreeNode p = root,lastVisted = root;
		Stack<TreeNode> stack = new Stack<>();
		boolean alreadyPushed = false;
		while(!stack.isEmpty()||p!=null){
			//根据alreadyPushed判断右子树是否已经被压入栈过
			if(!alreadyPushed){
				while(p!=null){		//未被压入栈过，则依次入栈
					stack.push(p);
					p = p.left;
				}
			}
			
			//后序遍历是第三次遇到该结点的时候输出，只有两种情况：
			//①该结点的右孩子为空（这里也看作第二次遇到后，先去了空的右孩子，再回头，所以是第三次遇到）
			//②该结点的右孩子已经访问过了（还可以肯定的是，被访问过的右孩子一定就是上一次访问的结点）
			if(!stack.isEmpty()){
				p = stack.pop();	//可能是第二或第三次遇到，要做进一步判断
				if(p.right==null||p.right==lastVisted){		//第三次遇到：①右孩子为空||②上一次访问的结点是它的右孩子
					System.out.print(p.val + " ");
					lastVisted = p;		//更新上一个访问的结点
					p = null;	//必须设空，否则最外层循环条件p!=null可能永远无法满足
					alreadyPushed = true;	//右孩子已经访问过了（已被压入栈过），不需要再进入右孩子
				}else{
					stack.push(p);		//说明右孩子还没访问过，将该结点再次入栈
					p = p.right;		//右孩子还没有访问过（未被压入栈过），先进入右孩子
					alreadyPushed = false;
				}
			}
		}
	}

算法思路

        后序遍历的非递归算法。思路参考来自这里。思路是当当前结点没有左孩子或右孩子或左孩子和右孩子已经被访问的情况下，访问该结点。 具体思路如下：

当前结点左子树不为空且左孩子和右孩子没有被访问过的情况下，不断入栈左子树；
	
左子树访问结束，判断当前结点是否有右孩子且右孩子没有访问过的情况下，入栈右孩子，回到步骤1；
	
当最后一个右孩子被访问到时，开始出栈，并记录上一次 范围的结点。
算法实现

void PostOrder(BiTree T){	//入栈所有的左子树以及左子树的右子树直到没有可以访问的右子树后退栈。 
	BiTNode *pre = T;	//记录上一次退栈的结点 
	BiTNode *p=T;		//当前访问结点 
	BiStack s ;             //保存结点用的栈
	s.top=0;                //栈底预留，用于保存NULL结束算法。
	s.data[s.top]=NULL;
	while(p||s.top!=0){
		if(p!=NULL&&pre!=p->lchild&&pre!=p->rchild){	//结点不为空且左孩子和右孩子没有访问过 ，入栈左子树 
			s.data[++s.top]=p;
			p=p->lchild;
		}
		else{					
			p=s.data[s.top];						 
			if(p->rchild!=NULL&&pre!=p->rchild){	//右子树不为空且右孩子没有访问过，入栈右子树结点 
				p=p->rchild;
			}
			else{
				printf("%d ",p->data);		//访问到最后的右子树的结点后，退栈。 
				pre=s.data[s.top];
				p=s.data[--s.top];
			}
		}
	}
}

C编程实现

#include<stdio.h>

typedef struct BiTNode{
	int data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

typedef struct{
	BiTree data[100];
	int top;
}BiStack;

void PostOrder(BiTree T);

int main(){
	BiTNode a,b,c,d,e,f,g;        //简单的测试数据
	a.data=1;
	b.data=2;
	c.data=3;
	d.data=4;
	e.data=5;
	f.data=6;
	g.data=7;
	a.lchild=&b;
	a.rchild=&g;
	b.lchild=&c;
	b.rchild=NULL;
	c.lchild=&d;
	c.rchild=&e;
	d.lchild=NULL;
	d.rchild=NULL;
	e.lchild=NULL;
	e.rchild=&f;
	f.lchild=NULL;
	f.rchild=NULL;
	g.lchild=NULL;
	g.rchild=NULL;
	
	
	PostOrder(&a);
	
	return 0;
}

void PostOrder(BiTree T){	//入栈所有的左子树以及左子树的右子树直到没有可以访问的右子树后退栈。 
	BiTNode *pre = T;		//记录上一次退栈的结点 
	BiTNode *p=T;			//当前访问结点 
	BiStack s ;
	s.top=0;
	s.data[s.top]=NULL;
	while(p||s.top!=0){
		if(p!=NULL&&pre!=p->lchild&&pre!=p->rchild){	//结点不为空且左孩子和右孩子没有访问过 ，入栈左子树 
			s.data[++s.top]=p;
			p=p->lchild;
		}
		else{					
			p=s.data[s.top];						 
			if(p->rchild!=NULL&&pre!=p->rchild){	//右子树不为空且右孩子没有访问过，入栈右子树结点 
				p=p->rchild;
			}
			else{
				printf("%d ",p->data);			//访问到最后的右子树的结点后，退栈。 
				pre=s.data[s.top];
				p=s.data[--s.top];
			}
		}
	}
}

 

void PostOrder2(BiTree T)
{    
    InitStack(S);
    BiTree p=T;
    BiTree r=NULL;
    while(p||!IsEmpty(S))
    {
        if(p)
        {
            Push(S,p);
            p=p->lchild;
        }
        else
        {
            p=GetTop(S);//先不出栈，满足条件再出栈访问
            if(p->right && p->right!=r)
                p=p->right;
            else//满足该结点没有右子树 或者 右儿子刚出栈，则出栈访问
            {
                p=Pop(S);
                visit(p);
                r=p;//记录最近出栈的结点
                p=NULL;//该结点的左右子树都已出栈，所以要继续出栈，访问其父结点
            }
        }
    }
}