二叉树的非递归遍历
在常规的二叉树的遍历的三种方式中，先序，中序，后序遍历，均采用了递归的方式。如果采用递归的方式是如何操作的？我们都知道递归调用，其实离不开栈的使用，我们如果能手动模拟栈，就能使用非递归的方式进行遍历，接下来将分别写一下非递归遍历的伪代码。
先序遍历
void PreOrder(BiTree T){
InintStack(S);
BiTree p = T; //初始化栈s，p是遍历指针
whlie(p || !IsEmpty(S)){ //栈不空或p不空时循环
if(p){ //一路向左
visit(p);
Push(S,p); //访问当前节点，并入栈
p = p->lchild //左孩子不空，一直往左走
}
else{ //出栈，并转向栈顶节点的右子树
Pop(S,p); //栈顶元素出栈
p = p-> rchild //向右子树走，p赋值为当前节点的右孩子
}
}
}
中序遍历
中序遍历和先序遍历非常类似，区别在于访问顺序不一样
void InOrder(BiTree T){
InintStack(S);
BiTree p = T; //初始化栈s，p是遍历指针
whlie(p || !IsEmpty(S)){ //栈不空或p不空时循环
if(p){ //一路向左
Push(S,p); //并入栈
p = p->lchild //左孩子不空，一直往左走
}
else{ //出栈，并转向栈顶节点的右子树
Pop(S,p); //栈顶元素出栈
visit(p); //访问当前节点
p = p-> rchild //向右子树走，p赋值为当前节点的右孩子
}
}
}
后序遍历
后序遍历和前两种还是有区别的，后序遍历需要保证左右孩子都被访问后，并且左孩子要在右孩子之前访问才能访问根节点。
后序遍历的算法思路分析：从根节点开始入栈，然后沿着其左子树一直往下搜索，知道搜索到没有左孩子节点，此时还不能进行出栈访问，因为如果有其右子树，还需要按相同的规则对右子树进行处理，直到上述操作不能进行为止，若栈顶元素想出栈，要么右子树为空，要么右子树被访问完（此时左子树已经被访问完），这样就保证了正确的访问顺序。
void PostOrder(BiTree T){
InitStack(S);
BiTree p = T;
r = NULL;
while(p || IsEmpty(S)){
if(p){ //走到最左面
Push(S,p);
p = p->lchild;
}else{ //向右
GetTop(S,p); //找到栈顶元素
if(p->rchlid && p->rchild != r){ //若右子树存在且未访问
p = p->rchild; //转向右
Push(S,p); //压入栈
p = p->lchild //再转向左
}else{ //否则，弹出并访问
Pop(S,p);visit(p->data);
r = p; //记录最近访问过的结点
p = NULL; //访问结束后，重置p指针（该结点的父亲结点只有左孩子）
}
}
}
}
