二叉树先序遍历非递归详解
1. 首先给出一颗二叉树，如下图所示：
图1一颗简单的二叉树
根据二叉树的先序遍历的特性，该二叉树先序遍历顺序为：ABDEGCFHI;
2. 一般遍历一颗二叉树，先序中序或者后序，大家最喜欢也最熟悉的方法是采用递归的形式来描述，但是在面试或者笔试的过程中，面试官一般都会要求采用非递归形式的二叉树遍历过程。我们先给出二叉树的递归形式（以先序遍历为例子），然后给出二叉树的非递归形式。
Void priorOrder(BiTree root)
{
If(root!=NULL)
{
Cout<<root->data;//输出根节点的元素值;
priorOrder(root->left);//遍历左子树;
priOrder(root->right);//遍历右子树；
}
}
3. 二叉树的非递归写法如下，先给出代码，后面会具体给出代码分析：
Void priorOrder(BiTree root){
BiTree stack[MaxSize],p;
int top=1;
if(root!=NULL){
stack[++top]=p;//根节点入栈;
while(top>0){
p=stack[top--];//根节点出栈，并将p指向当前出栈的节点;
cout<<p->data<<”\t”;
if(p->right!=NULL)//右孩子不为空，将右孩子入栈；
stack[++top]=p->right;
if(p->left!=NULL) //左孩子不为空，将左孩子入栈；
stack[++top]=p->left;
}
}
}
二叉树先序遍历非递归的思想：首先外层循环的判断条件时根节点不为空，不为空的情况下，将根节点入栈，然后在栈的大小不为空的前提下循环，将栈顶指针出栈，建立一个临时的栈，将该栈指向当前出栈的结点，并判断该结点的右孩子是否为空，为空则不进行处理，不为空，则将右孩子入栈，同时判断该结点的左孩子是否为空，为空不进行处理，不为空，则将左孩子入栈，关于为什么要先将右孩子入栈，左孩子后入栈的问题，大家应该清楚（栈是先进后出，二叉树先序遍历是根左右，右孩子先入栈，坐孩子后入栈，那么出栈的时候就会先输出左孩子，然后是右孩子）。
针对上面的图，对于非递归的先序遍历进行图形化分析：
欢迎大家指出错误！