先说一下：二叉树的非递归遍历的基本思路：使用堆栈
下面是用到的栈的存储结构以及基本操作，代码如下：
/*非递归遍历中栈存储结构：包括栈的容量，栈顶指针和栈底指针。代码如下：*/ typedef struct { bst *base; bst *top; int stacksize; }stack; /*非递归遍历中所用到的栈的基本操作：代码如下：*/ int initialstack(stack &s)//初始化栈 { s.base=new bst[200]; if(s.base==NULL) return 0; s.stacksize=200; s.top=s.base; return 1; } int push(stack &s,bst e)//进栈 { if(s.top-s.base==s.stacksize) return 0; *s.top++=e; return 1; } int pop(stack &s,bst &e)//出栈 { if(s.top==s.base) return 0; e=*--s.top; return 1; } int GetTop(stack &s,bst &e) //若栈不空，则用e返回S的栈顶元素 { if(s.top!=s.base) e=*(s.top-1);//返回栈顶元素的值，栈顶指针不变 return 1; }1. 非递归中序遍历 遍历过程为： ① 遇到一个结点，就把它压栈，并去遍历它的左子树； ② 当左子树遍历结束后，从栈顶弹出这个结点并访问它； ③然后按其右指针再去中序遍历该结点的右子树。
利用栈先进后出的思想，当t非空或栈s非空时，执行以下循环：如果t非空，则将t进栈，t指向该结点的左孩子；如果t为空，则弹出栈顶元素并访问，将p指向该结点右子树。 代码如下：
void InOrder2(bst t,stack &s)//非递归中序遍历 { while(t!=NULL||s.base!=s.top) /*只有遍历完并且栈空了才结束，单独一个栈为空是不够的，因为一开始就是空栈， 单独一个t为NULL也是不够的，因为这只代表你遍历完一条分支，此时栈是非空的*/ { if(t) { push(s,t); t=t->lchild; } else { pop(s,t); cout<<t->data<<" "; t=t->rchild; } } cout<<endl; }2. 非递归先序遍历 遍历过程为： ① 遇到一个结点，就访问它并把它压栈，然后去遍历它的左子树； ② 当左子树遍历结束后，从栈顶弹出这个结点并遍历它的右子树； ③然后按其右指针再去先序遍历该结点的右子树。
利用栈先进后出的思想，当t非空或栈s非空时，执行以下循环：如果t非空，则访问根结点，t进栈，t指向该结点左孩子；如果t为空，则弹出栈顶元素，将p指向该结点右子树。 代码如下：
void PreOrder2(bst t, stack &s)//非递归前序遍历 { while(t!=NULL||s.base!=s.top) //只有遍历完并且栈空了才结束，单独一个栈为空是不够的，因为一开始就是空栈， //单独一个t为NULL也是不够的，因为这只代表你遍历完一条分支，此时栈是非空的 { if(t) { cout<<t->data<<" ";//先序先遍历根结点 push(s,t); t=t->lchild; } else//在t为空的情况下，弹出该结点，遍历右孩子 { pop(s,t); t=t->rchild; } } }3. 非递归后序遍历 ① 遇到一个结点，就把它压栈，然后去遍历它的左子树； ② 当左子树遍历结束后，从栈顶弹出这个结点并访问它，回退到其父结点； ③然后判断回退到的父结点的右孩子是否被访问过，是则将自己弹出并访问；否则再去遍历其右子树
后序遍历较前两种遍历方法比较难实现，原因在于需要遍历完左子树，遍历完右子树，最后才去访问根节点。这样栈顶结点可能会从该结点的左子树返回，也有可能从它的右子树返回，需要区分这种情况，如果是第一次从左子树返回，那么还需要跳过根节点，先去遍历其右子树，再回头访问根节点；如果是从右子树返回，那么直接返回该结点就可以了。这里使用辅助指针来区分来源。 代码如下：
void LastOrder2(bst t,stack &s)//非递归后序遍历 { bst r=NULL;//辅助指针 while(t!=NULL||s.base!=s.top) { if(t)//从根节点到最左下角的左子树都入栈 { push(s,t);//中序现将结点进栈保存 t=t->lchild; } else { GetTop(s,t); if(t->rchild&&t->rchild!=r)//1.右子树还没有访问并且右子树不空，第一次栈顶 { t=t->rchild; } else//右子树已经访问或为空，接下来出栈访问结点，第二次栈顶 { pop(s,t); cout<<t->data<<" "; r=t;//指向访问过的右子树结点 t=NULL;//使p为空继续访问栈顶 } } } cout<<endl; }