二叉树的后序遍历非递归算法之c++实现
#include <stack>
#include <iostream>
using namespace std;
template <class T>
class TreeNode
{
public:
T data;
TreeNode<T> *left; //left child
TreeNode<T> *right; //right child
TreeNode():left(NULL),right(NULL)
{
}
TreeNode(const T& t):data(t),left(NULL), right(NULL)
{
}
TreeNode(const T& t, TreeNode<T*> left, TreeNode<T*> right):data(t),left(left), right(left)
{
}
};
/**purpose: 对二叉树进行后序遍历（非递归算法）
*@param TreeNode<T> *root the root of the binary tree
*/
template <class T>
void postOrder(TreeNode<T> *root)
{
stack<TreeNode<T>*> st;
TreeNode<T> *p = root;
TreeNode<T> *pre = NULL;//pre表示最近一次访问的结点
while(p || st.size()!=0)
{
//沿着左孩子方向走到最左下 。
while(p)
{
st.push(p);
p = p->left;
}
//get the top element of the stack
p = st.top();
//如果p没有右孩子或者其右孩子刚刚被访问过
if(p->right == NULL || p->right == pre)
{
//visit this element and then pop it
cout << "visit: " << p->data << endl;
st.pop();
pre = p;
p = NULL;
}
else
{
p = p->right;
}
}//end of while(p || st.size()!=0)
}