C++实现二叉树的递归遍历与非递归遍历

基本上所有关于二叉树的操作都是基于二叉树的遍历算法来实现的，因此在这里讲一下二叉树的遍历算法，其中包括递归与非递归算法，在算法中用输出节点数据来代替对节点的操作。
首先给出这样一棵数：

1、前序遍历
所谓前序遍历就是先对节点数据进行处理，然后才对这个节点的左右子树进行处理。对这棵二叉树的前序遍历结果为：ABDCEFG。
递归：

    void _PreOrder(PNode& pRoot)
    {
        if (pRoot)
        {
            cout << pRoot->_data << " ";
            _PreOrder(pRoot->_LChild);
            _PreOrder(pRoot->_RChild);
        }
    }
    void PreOrder()
    {
        _PreOrder(_pRoot);
        cout << endl;
    }

非递归：
非递归方式需要用到栈，这里给出两种算法：
第一种：

void PreOrder_Nor1()
      {
           if(NULL == _pRoot)
               return;
           stack<pNode> s;
           s.push(_pRoot);
           pNode pTemp = NULL;
           while(!s.empty())
           {
               pTemp = s.top();
               cout<< pTemp->_data << " ";
               s.pop();
               if(NULL != pTemp->_RChild)
                   s.push(pTemp->_RChild);
               if(NULL != pTemp->_LChild)
                   s.push(pTemp->_LChild);
           }
           cout<<endl;
      }

第二种：

      void PreOrder_Nor2()
      {
           if(NULL == _pRoot)
               return;
           stack<pNode> s;
           s.push(_pRoot);
           pNode cur = NULL;
           while(!s.empty())
           {
                   cur = s.top();
                   s.pop();
                   while(cur)
                   {
                       cout<< cur->_data << " ";
                       if(cur->_RChild)
                           s.push(cur->_RChild);
                       cur = cur->_LChild;
                   }
            }
            cout<<endl;
     }

调用三种方法：

中序遍历：
中序遍历顺序为左子树->节点->右子树，这棵二叉树的遍历结果为：BDAECFG
递归：

    void _InOrder(PNode& pRoot)
    {
        if (pRoot)
        {
            _InOrder(pRoot->_LChild);
            cout << pRoot->_data << " ";
            _InOrder(pRoot->_RChild);
        }
    }
    void InOrder()
    {
        _InOrder(_pRoot);
        cout << endl;
    }

非递归：

void InOrder_Nor()
{
    if(NULL == _pRoot)
        return;
    stack<pNode> s;
    pNode cur = _pRoot;
    pNode pPre = NULL;
    while(!s.empty() || cur)
    {
        while(cur && cur != pPre)
        {
            s.push(cur);
            cur = cur->_LChild;
        }
        if(s.empty())
            return;
        cur = s.top();
        cout<< cur->_data << " ";
        pPre = cur;
        s.pop();
        cur = cur->_RChild;
    }
    cout<<endl;
}

调用两种中序遍历算法：

后序遍历
后序遍历顺序为：左子树->右子树->节点，这棵二叉树的遍历结果为DBEGFCA
递归：

    void _PostOrder(PNode& pRoot)
    {
        if (pRoot)
        {
            _PostOrder(pRoot->_LChild);
            _PostOrder(pRoot->_RChild);
            cout << pRoot->_data << " ";
        }
    }
    void PostOrder()
    {
        _PostOrder(_pRoot);
        cout << endl;
    }

非递归：

      void PostOrder_Nor()
      {
          if(NULL == _pRoot)
              return;
          stack<pNode> s;
          s.push(_pRoot);
          pNode cur = _pRoot->_LChild;
          pNode pPre = NULL;
          while(!s.empty())
          {
              while(cur && cur!= pPre)
              {
                  s.push(cur);
                  cur = cur->_LChild;
              }
              if(s.empty())
                  return;
              cur = s.top();
              if(cur->_RChild && cur->_RChild != pPre)
              {
                  cur = cur->_RChild;
              }
              else
              {
                  cout<< cur->_data << " ";
                  pPre = cur;
                  s.pop();
              }
         }
         cout<<endl;
     }

调用两种方法：

层序遍历
层序遍历算法不同于前序、中序、后序算法，层序遍历用递归方式实现比较困难，一般用队列结合循环实现比较简单。其基本思想是从根节点开始一层一层的从上向下遍历，其过程为：

因此层序遍历的结果为：ABCDEFG
其代码实现为:

    void LevelOrder()
    {
        queue<PNode> q;
        if (_pRoot)
            q.push(_pRoot);
        while (!q.empty())
        {
            PNode tmp = q.front();
            cout << tmp->_data << " ";
            if (tmp->_LChild)
                q.push(tmp->_LChild);
            if (tmp->_RChild)
                q.push(tmp->_RChild);
            q.pop();
        }
        cout << endl;
    }

遍历结果：

算法实现还有待改进，望高手斧正！