二叉樹結(jié)點
struct BSTreeNode
{
int val;
BSTreeNode *left;
BSTreeNode *right;
BSTreeNode(int x = 0) : val(x), left(nullptr), right(nullptr) { }
};
先序，中序和后序遍歷過程：遍歷過程經(jīng)過結(jié)點的路線一樣，只是訪問各結(jié)點的時機不同系谐。每個結(jié)點都會被遍歷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; } } } -
中序非遞歸遍歷
遇到一個結(jié)點许赃，就把它壓棧止喷，并去遍歷它的左子樹，當它的左子數(shù)遍歷結(jié)束混聊，從棧頂彈出這個結(jié)點并訪問它弹谁，然后按照右指針中序遍歷該結(jié)點的右子樹
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; } // 左子樹遍歷結(jié)束 if (!stack_.empty()) { x = stack_.top(); stack_.pop(); func(x); // 從棧頂彈出結(jié)點，訪問 x = x->right; // 中序遍歷該結(jié)點的右子樹 } } }
