前言
二叉树的递归遍历在我上一篇“二叉树及其三种序的递归遍历”里有。其中用到的“BinaryTree”也在链接文章的“二叉树的创建”里。大一计算机的自学总结：二叉树及其三种序的递归遍历
而非递归遍历是借助栈的特性，会更难更复杂。TvT......
一、先序遍历
#include<bits/stdc++.h>
#include"BinaryTree.h"
using namespace std;
//非递归先序遍历二叉树
void preOrder(TreeNode* head)
{
if(head!=NULL)
{
stack<TreeNode*>s;
s.push(head);
while(!s.empty())
{
head=s.top();
cout<<head->value<<" ";
s.pop();
if(head->right!=NULL)
{
s.push(head->right);
}
if(head->left!=NULL)
{
s.push(head->left);
}
}
}
}
int main()
{
TreeNode* head=NULL;
addTree(head);
//非递归先序遍历二叉树
cout<<"preorder:"<<endl;
preOrder(head);
return 0;
}因为先序遍历的顺序是“中、左、右”，根据栈的特性，先入右孩子再入左孩子就行。
先将头节点入栈，然后只要栈不为空，就让head指针指向栈顶元素，然后输出栈顶节点的数值，
之后出栈顶。此时输出的即为“中”节点，之后只要按照先入右孩子再入左孩子的顺序入栈即可。
二、中序遍历
#include<bits/stdc++.h>
#include"BinaryTree.h"
using namespace std;
//非递归中序遍历二叉树
void inOrder(TreeNode* head)
{
if(head!=NULL)
{
stack<TreeNode*>s;
while(!s.empty()||head!=NULL)
{
if(head!=NULL)
{
s.push(head);
head=head->left;
}
else
{
head=s.top();
cout<<head->value<<" ";
s.pop();
head=head->right;
}
}
}
}
int main()
{
TreeNode* head;
addTree(head);
//非递归中序遍历二叉树
cout<<"inorder:"<<endl;
inOrder(head);
return 0;
}根据中序“左、中、右”的顺序，思路是先一直入左孩子直到进完，然后弹出一个，之后去到弹出节点的右孩子并重复上述过程，直到没有子树且栈为空。
当不满足没有子树且栈为空时，若有子树，则将节点入栈并移向左孩子；若没有子树了，则输出栈顶节点的数，然后出栈顶并移向右孩子。
三、后序遍历
1.两个栈实现
#include<bits/stdc++.h>
#include"BinaryTree.h"
using namespace std;
//非递归后序遍历二叉树——两个栈实现
void postOrderTwoStacks(TreeNode* head)
{
if(head!=NULL)
{
stack<TreeNode*>data;
stack<TreeNode*>s;
data.push(head);
while(!data.empty())
{
head=data.top();
s.push(head);//反转
data.pop();
if(head->left!=NULL)
{
data.push(head->left);
}
if(head->right!=NULL)
{
data.push(head->right);
}
}
while(!s.empty())
{
head=s.top();
cout<<head->value<<" ";
s.pop();
}
}
}
int main()
{
TreeNode* head=NULL;
addTree(head);
//非递归后序遍历二叉树
cout<<"postorder:"<<endl;
postOrderTwoStacks(head);
return 0;
}第一个思路，观察先序遍历“中、左、右”和后序遍历“左、右、中”的顺序，可以发现，若将先序遍历代码中先入右孩子再入左孩子的顺序调换，再将整个顺序反转就能得到“左、右、中”的顺序。
于是准备两个栈，一个先存放数据，另一个负责反转后输出。
先往data栈中压入节点，当栈不为空时，先向反转栈中压入栈顶元素再弹出，然后调换先序遍历的代码，先入左孩子再入右孩子。
当data栈的数据全部倒完后，只需按顺序输出s栈的栈顶元素即可。
2.一个栈实现
#include<bits/stdc++.h>
#include"BinaryTree.h"
using namespace std;
//非递归后序遍历二叉树——一个栈实现
void postOrderOneStack(TreeNode* head)
{
if(head!=NULL)
{
stack<TreeNode*>s;
s.push(head);
while(!s.empty())
{
TreeNode* p=s.top();
//有左树且左树没处理过
if(p->left!=NULL&&head!=p->left&&head!=p->right)
{
s.push(p->left);
}
//有右树且右树没处理过
else if(p->right!=NULL&&head!=p->right)
{
s.push(p->right);
}
//都没有或都处理过了
else
{
cout<<p->value<<" ";
head=s.top();
s.pop();
}
}
}
}
int main()
{
TreeNode* head;
addTree(head);
//非递归后序遍历二叉树
cout<<"postorder:"<<endl;
postOrderOneStack(head);
return 0;
}为了用一个栈实现，可以将head的更新条件改为更新成上一个输出过的节点。
压入节点后，当栈不为空时，设置指针p来指向当前节点，之后，若有左树且左树没处理过，则压入当前节点的左孩子；否则若有右树且右树没处理过，则压入当前节点的右孩子；否则，即没有子树或都处理过了，就输出当前节点的数，并将head指针更新成此时节点，表示已经处理过了。
只看代码的话会比较抽象很难理解，只有模拟一遍全过程才能理解这个思路的巧妙。
总结
二叉树三种序的非递归遍历也很重要，特别是后序遍历中两个栈优化成一个栈，重设head更新条件的思路。