二叉树的遍历

二叉树结点

struct BSTreeNode
{
    int val;
    BSTreeNode *left;
    BSTreeNode *right;
    BSTreeNode(int x = 0) : val(x), left(nullptr), right(nullptr) {  }
};

先序，中序和后序遍历过程：遍历过程经过结点的路线一样，只是访问各结点的时机不同。每个结点都会被遍历3次，先序遍历是第一次就打印，中序遍历是第二次打印，后序遍历是第3次打印。

遍历.jpg

递归遍历

• 前序递归遍历

  void BSTree::_preOrder(BSTreeNodePtr x, std::function<void(BSTreeNodePtr)> func)
  {
      if (x == nullptr)
          return;
  
      func(x);
      _preOrder(x->left, func);
      _preOrder(x->right, func);
  }
  

• 中序递归遍历

  void BSTree::_inOrder(BSTreeNodePtr x, std::function<void(BSTreeNodePtr)> func)
  {
      if (x == nullptr)
          return;
  
      _inOrder(x->left, func);
      func(x);
      _inOrder(x->right, func);
  }
  

• 后序递归遍历

  void BSTree::_postOrder(BSTreeNodePtr x, std::function<void(BSTreeNodePtr)> func)
  {
      if (x == nullptr)
        return;
  
      _postOrder(x->left, func);
      _postOrder(x->right, func);
      func(x);
  }
  

非递归遍历

• 前序非递归遍历

  void BSTree::_preorderWithNonRecursion(BSTreeNodePtr x, std::function<void(BSTreeNodePtr)> func)
  {
      std::stack<BSTreeNodePtr> stack_;
  
      while(!stack_.empty() || x)
      {
          while(x)
          {
              func(x);
              stack_.push(x);
              x = x->left;
          }
          if (!stack_.empty())
          {
              x = stack_.top();
              stack_.pop();
              x = x->right;
          }
      }
  }
  

• 中序非递归遍历

  遇到一个结点，就把它压栈，并去遍历它的左子树，当它的左子数遍历结束，从栈顶弹出这个结点并访问它，然后按照右指针中序遍历该结点的右子树

  void BSTree::_inOrderWithNonRecursion(BSTreeNodePtr x, std::function<void(BSTreeNodePtr)> func)
  {
      std::stack<BSTreeNodePtr> stack_;
  
      while(!stack_.empty() || x)
      {
          while(x)
          {
              stack_.push(x);
              x = x->left;
          }          // 左子树遍历结束
          if (!stack_.empty())
          {
              x = stack_.top();
              stack_.pop();
              func(x);          // 从栈顶弹出结点，访问
              x = x->right;     // 中序遍历该结点的右子树
          }
      }
  }