二叉树的遍历（递归与非递归）

二叉树的遍历

1、前序遍历

判断节点是否为空，如果不为空，先访问根节点，再访问左子树，最后访问右子树；

递归实现在上一篇文章已经做了讨论。如下：

void PreOrder()
  {
    _PreOrder(_pRoot);
    cout << endl;
  }      

void _PreOrder(PNode& pRoot)
  {
    if (pRoot == NULL)
      return;
    cout << pRoot->_data << " ";
    _PreOrder(pRoot->_left);
    _PreOrder(pRoot->_right);
  }      

非递归有两种方式：

（1）在树不为空的情况下，以下步骤循环：

1、将根节点压栈

2、取栈顶元素，访问并出栈

3、右子树存在，保存当前节点的右子树

4、遍历左子树

void _PreOrder1(PNode &pRoot)
  {
    if (pRoot == NULL)
      return;
    stack<PNode> s;
    s.push(pRoot);

    while (!s.empty())
    {
      PNode pCur = s.top();
      s.pop();
      while (pCur)
      {
        cout << pCur->_data << " ";
        if (pCur->_right)
          s.push(pCur->_right);
        pCur = pCur->_left;
      }
    }
  }      

（2）在树不为空的情况下，以下步骤循环：

1、将根节点压栈

2、取栈顶元素，访问并出栈

3、右子树存在，保存当前节点的右子树

4、左子树存在，保存当前节点的左子树

void _PreOrder2(PNode &pRoot)
  {
    if (pRoot == NULL)
      return;
    stack<PNode> s;
    s.push(pRoot);
    while (!s.empty())
    {
      PNode pCur = s.top();
      s.pop();
      cout << pCur->_data << " ";

      if (pCur->_right)
        s.push(pCur->_right);
      if (pCur->_left)
        s.push(pCur->_left);
    }
  }      

2、中序遍历

先访问左子树，再访问根节点，最后访问右子树。

递归：

void InOrder()
  {
    _InOrder(_pRoot);
    cout << endl;
  }      

实现：

左子树--->根节点--->右子树 
  void _InOrder(PNode pRoot)
  {
    //pNode pCur = pRoot;
    if (pRoot == NULL)
      return;
    _InOrder(pRoot->_left);
    cout << pRoot->_data << " ";
    _InOrder(pRoot->_right);
  }      

非递归：将所有的左节点保存但是不访问，因为要保证走到最坐边的节点

1、找以当前节点为根的左侧路径中所有的节点并保存

2、取栈顶元素，访问并出栈

3、遍历右子树

void _InOrder(PNode pRoot)
  {
    if (NULL == pRoot)
      return;
    stack<PNode> s;
    PNode pCur = pRoot;

    while (pCur != NULL || !s.empty())
    {
      //找以当前节点为根节点的左侧路径中的所有节点并保存
      while (pCur)
      {
        s.push(pCur);
        pCur = pCur->_left;
      }

      pCur = s.top();
      cout << pCur->_data << " ";
      s.pop();

      pCur = pCur->_right;
    }
  }      

3、后序遍历

根节点->右子树->左子树

递归：

void PostOrder()
  {
    _PostOrder(_pRoot);
    cout << endl;
  }      

void _PostOrder(PNode pRoot)
  {
    if (pRoot == NULL)
      return;
    _PostOrder(pRoot->_left);
    _PostOrder(pRoot->_right);
    cout << pRoot->_data << " "; 
  }      

非递归：

void _PostOrder(PNode pRoot)
  {
    if (NULL == pRoot)
      return;

    stack<PNode> s;
    PNode pCur = pRoot;
    PNode prev = NULL;    //记录上一个被访问的节点

    //找以根节点为根节点的左侧路径中的所有节点并保存
    while (pCur)
    {
      s.push(pCur);
      pCur = pCur->_left;
    }
    while (!s.empty())
    {
      pCur = s.top();
      s.pop();

      //右子树为空或已被访问过
      if (pCur->_right == NULL || pCur->_right == prev)
      {
        cout << pCur->_data << " ";
        prev = pCur;
      }
      //未被访问，需遍历以当前节点为根的树，因此继续入栈
      else
      {
        s.push(pCur);
        pCur = pCur->_right;
        //找以根节点为根节点的左侧路径中的所有节点并保存
        while (pCur)
        {
          s.push(pCur);
          pCur = pCur->_left;
        }
      }
    }
  }