二叉树遍历 前序/中序/后序 递归/非递归

前序遍历递归

void PreOrder(pTreeT root)
{
    if (NULL != root)
    {
        visit(root);
        PreOrder(root->left);
        PreOrder(root->right);
    }    
}

前序遍历非递归

void PreOrderNoRec(pTreeT root)
{
    stack<treeT *> s;

    while ((NULL != root) || !s.empty())
    {
        if (NULL != root)
        {
            visit(root);
            s.push(root);
            root = root->left;
        }
        else
        {
            root = s.top();
            s.pop();
            root = root->right;
        }
    }
}

中序遍历递归

void InOrder(pTreeT root)
{
    if (NULL != root)
    {
        BT_InOrder(root->left);
        visit(root);
        BT_InOrder(root->right);
    }
}

中序遍历非递归

void InOrderNoRec(pTreeT root)
{
    stack<treeT *> s;
    while ((NULL != root) || !s.empty())
    {
        if (NULL != root)
        {
            s.push(root);
            root = root->left;
        }
        else
        {
            root = s.top();
            visit(root);
            s.pop();
            root = root->right;
        }
    }

后序遍历递归

void PostOrder(pTreeT root)
{
    if (NULL != root)
    {
        BT_PostOrder(root->left);
        BT_PostOrder(root->right);
        visit(root);    
    }
}

后序遍历非递归
利用pre记录最近访问的结点

void postOrder(TreeNode<T> *root)
{
  stack<TreeNode<T>*> st;//定义栈，节点类型为TreeNode
  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)

}

分别来自：
http://www.cppblog.com/ngaut/archive/2012/09/06/2351.html
http://blog.csdn.net/iamyina/article/details/4124613