二叉树遍历算法的重要性大家都知道，是很多算法的基础，它的递归实现非常简单，相信学过数据结构的同学都应该能够轻松写出来。如果需要写出二叉树的前序遍历、中序遍历以及后续遍历的非递归实现，可能还是需要费点时间。下面给出实现方式。
因为每个结点都只遍历一边，所以时间复杂度为O(N)。
前序遍历：
二叉树的前序非递归实现可以按照这样的思路：毫无疑问，我们需要一个栈来作为辅助空间，首先将根节点入栈，当栈不为空时，取出栈顶元素，访问该元素，然后将其右孩子入栈，再将其左孩子入栈(将右孩子先于左海子入栈，保证了左海子在右孩子前面被访问)。这样一直进行下去，知道栈为空，得到的访问序列就是二叉树的先根遍历序列。
下面给出实现代码：
树的节点结构：
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
先根遍历代码：
//非递归先根遍历
class Solution1 {
public:
vector<int> preorderTraversal1(TreeNode *root) {
vector<int> ret ;
if (root == NULL)
return ret ;
stack<TreeNode*> s ;
s.push(root) ;
TreeNode* tmpNode = NULL ;
while(!s.empty())
{
tmpNode = s.top() ;
s.pop() ;
ret.push_back(tmpNode->val) ;
if (tmpNode->right != NULL)
s.push(tmpNode->right) ;
if (tmpNode->left!= NULL)
s.push(tmpNode->left) ;
}
return ret ;
}
vector<int> preorderTraversal2(TreeNode *root) {
vector<int> ret ;
stack<TreeNode*> s ;
while(root != NULL || !s.empty())
{
if (root != NULL)
{
ret.push_back(root->val) ;
s.push(root) ;
root = root->left ;
}
else
{
root = s.top() ; //回溯
s.pop() ;
root = root->right ;
}
}
return ret ;
}
};
这里给出了两种实现方式，preorderTraversal1()则严格按照上面的思路实现。而preorderTraversal2()的思路稍有不同，先是访问节点并将其入栈，然后再继续访问其左节点，知道当前节点没有左节点位置，这时候进行回溯，访问上一个节点的右孩子节点。这样一直下去，知道当前节点为空，并且栈也为空为止。此时，访问序列同样是二叉树的前序遍历序列。
中序遍历：
中序遍历的思想与上面前序遍历的第二种实现一致，仅仅是访问的时机不同，下面直接给出实现代码：
//非递归中根遍历
class Solution2
{
public:
vector<int> inorderTraversla(TreeNode *root)
{
vector<int> ret ;
stack<TreeNode*> s ;
while (root != NULL || !s.empty())
{
if (root != NULL)
{
s.push(root) ;
root = root->left ;
}
else
{
//开始回溯
root = s.top() ;
s.pop() ;
ret.push_back(root->val) ; //访问
root = root->right ;
}
}
return ret ;
}
};
后续遍历：
后续遍历的非递归实现是二叉树非递归遍历算法中最复杂的一个，我们可以通过在树的节点数据结构中增加数据项来记录访问的状态，标记其右子树是否已经被访问来实现，但是这样就需要改变树的数据结构。
这里，我们可以换一种思维方式，将问题进行转化，我们可以先求出数的后续遍历的逆序，这样问题就迎刃而解了。
我们可以按照这样的顺序来访问节点<根节点、右节点、左节点>，然后将得到的访问序列逆序，得到的新序列就是二叉树的后续遍历序列，对于访问序列<根节点、右节点、左节点>的实现，方法和上面的先根遍历一致，这里不做赘述。下面直给出代码：
//非递归后根遍历
class Solution3 {
public:
vector<int> postorderTraversal(TreeNode *root) {
//先按照 <根，右孩子，左孩子>的顺序存入序列ret中，
//最后将ret逆序，就得到正确的访问顺序
vector<int> ret ;
if (root == NULL) return ret ;
stack<TreeNode*> s ;
s.push(root) ;
TreeNode* tmpNode = NULL ;
while(!s.empty())
{
tmpNode = s.top() ;
s.pop() ;
ret.push_back(tmpNode->val) ; //访问根节点
if (tmpNode->left != NULL)//左侧节点入队列
s.push(tmpNode->left) ;
if (tmpNode->right != NULL)//右侧节点入队列
s.push(tmpNode->right) ;
}
reverse(ret.begin(), ret.end()) ;
return ret ;
}
};
后根遍历的第二种实现思路：要保证根节点在左孩子和右孩子访问之后才能访问，因此对于任一结点p，先将其入栈。如果p不存在左孩子和右孩子，则可以直接访问，或者p存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将p的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。。
void postorderTraversal2(TreeNode *root) //非递归后序遍历
{
stack<TreeNode*> s;
TreeNode *cur; //当前结点
TreeNode *pre=NULL; //记录前一次访问的结点
s.push(root);
while(!s.empty())
{
cur=s.top();
if((cur->left==NULL&&cur->right==NULL)|| (pre!=NULL&&(pre==cur->left||pre==cur->right)))//可以访问根结点时的两种情况
{
cout<<cur->val<<" "; //如果当前结点没有孩子结点或者孩子节点都已被访问过
s.pop(); pre=cur;
}
else
{
if(cur->right!=NULL)
s.push(cur->right);
if(cur->left!=NULL)
s.push(cur->left);
}
}
}
三种遍历算法的测试程序
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//非递归先根遍历
class Solution1 {
public:
vector<int> preorderTraversal1(TreeNode *root) {
vector<int> ret ;
if (root == NULL)
return ret ;
stack<TreeNode*> s ;
s.push(root) ;
TreeNode* tmpNode = NULL ;
while(!s.empty())
{
tmpNode = s.top() ;
s.pop() ;
ret.push_back(tmpNode->val) ;
if (tmpNode->right != NULL)
s.push(tmpNode->right) ;
if (tmpNode->left!= NULL)
s.push(tmpNode->left) ;
}
return ret ;
}
vector<int> preorderTraversal2(TreeNode *root) {
vector<int> ret ;
stack<TreeNode*> s ;
while(root != NULL || !s.empty())
{
if (root != NULL)
{
ret.push_back(root->val) ;
s.push(root) ;
root = root->left ;
}
else
{
root = s.top() ; //回溯
s.pop() ;
root = root->right ;
}
}
return ret ;
}
};
//非递归中根遍历
class Solution2
{
public:
vector<int> inorderTraversla(TreeNode *root)
{
vector<int> ret ;
stack<TreeNode*> s ;
while (root != NULL || !s.empty())
{
if (root != NULL)
{
s.push(root) ;
root = root->left ;
}
else
{
//开始回溯
root = s.top() ;
s.pop() ;
ret.push_back(root->val) ; //访问
root = root->right ;
}
}
return ret ;
}
};
//非递归后根遍历
class Solution3 {
public:
vector<int> postorderTraversal(TreeNode *root) {
//先按照 <根，右孩子，左孩子>的顺序存入序列ret中，
//最后将ret逆序，就得到正确的访问顺序
vector<int> ret ;
if (root == NULL) return ret ;
stack<TreeNode*> s ;
s.push(root) ;
TreeNode* tmpNode = NULL ;
while(!s.empty())
{
tmpNode = s.top() ;
s.pop() ;
ret.push_back(tmpNode->val) ; //访问根节点
if (tmpNode->left != NULL)//左侧节点入队列
s.push(tmpNode->left) ;
if (tmpNode->right != NULL)//右侧节点入队列
s.push(tmpNode->right) ;
}
reverse(ret.begin(), ret.end()) ;
return ret ;
}
};
int main(int argc, char **argv)
{
/*************************************************************
*树结构: 1
* / \
* 2 3
* / \ \
* 4 5 6
*************************************************************/
TreeNode* root = new TreeNode(1) ;
root->left = new TreeNode(2) ;
root->right = new TreeNode(3) ;
root->left->left = new TreeNode(4) ;
root->left->right = new TreeNode(5) ;
root->right->right = new TreeNode(6) ;
//先根遍历
Solution1 s1;
vector<int> ret1 = s1.preorderTraversal1(root) ;
cout << "先根遍历的结果：" << endl;
for (int i = 0; i < ret1.size(); ++ i)
cout << ret1[i] << " " ;
cout << endl;
//中根遍历
Solution2 s2;
vector<int> ret2 = s2.inorderTraversla(root) ;
cout << "中根遍历的结果：" << endl;
for (int i = 0; i < ret2.size(); ++ i)
cout << ret2[i] << " " ;
cout << endl;
//后根遍历
Solution3 s3;
vector<int> ret3 = s3.postorderTraversal(root) ;
cout << "后根遍历的结果：" << endl;
for (int i = 0; i < ret3.size(); ++ i)
cout << ret3[i] << " " ;
cout << endl;
return 0 ;
}