C++ 非遞歸實現二叉樹的前中後序遍歷
二叉樹的前序遍歷
在不使用遞歸的方式遍歷二叉樹時,我們可以使用一個棧模擬遞歸的機制。二叉樹的前序遍歷順序是:根 → 左子樹 → 右子樹,我們可以先將二叉樹的左路結點入棧,在入棧的同時便對其進行訪問,此時就相當於完成瞭根和左子樹的訪問,當左路結點入棧完畢後再從棧頂依次取出結點,並用同樣的方式訪問其右子樹即可。
具體步驟如下:
- 將左路結點入棧,入棧的同時訪問左路結點。
- 取出棧頂結點top。
- 準備訪問top結點的右子樹。
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; class Solution { public: //前序遍歷 vector<int> preorderTraversal(TreeNode* root) { stack<TreeNode*> st; //輔助棧 vector<int> ret; //用於存放前序遍歷的結果 TreeNode* cur = root; while (cur || !st.empty()) { //1、將左路結點入棧,入棧的同時訪問左路結點 while (cur) { st.push(cur); ret.push_back(cur->val); cur = cur->left; } //2、取出棧頂結點 TreeNode* top = st.top(); st.pop(); //3、準備訪問其右子樹 cur = top->right; } return ret; //返回前序遍歷結果 } };
二叉樹的中序遍歷
二叉樹的中序遍歷順序是:左子樹 → 根 → 右子樹,我們可以先將二叉樹的左路結點入棧,當左路結點入棧完畢後,再從棧頂依次取出結點,在取出結點的同時便對其進行訪問,此時就相當於先訪問瞭左子樹再訪問瞭根,之後再用同樣的方式訪問取出結點的右子樹即可。
具體步驟如下:
- 將左路結點入棧。
- 取出棧頂結點top並訪問。
- 準備訪問top結點的右子樹。
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; class Solution { public: //中序遍歷 vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> st; //輔助棧 vector<int> ret; //用於存放中序遍歷的結果 TreeNode* cur = root; while (cur || !st.empty()) { //1、將左路結點入棧 while (cur) { st.push(cur); cur = cur->left; } //2、取出棧頂結點並訪問 TreeNode* top = st.top(); st.pop(); ret.push_back(top->val); //3、準備訪問其右子樹 cur = top->right; } return ret; //返回中序遍歷結果 } };
二叉樹的後序遍歷
二叉樹的後序遍歷順序是:左子樹 → 右子樹 → 根,我們可以先將二叉樹的左路結點入棧,當左路結點入棧完畢後,再觀察棧頂結點,若棧頂結點的右子樹為空,或棧頂結點的右子樹已經被訪問過瞭,則棧頂結點可以出棧並訪問,若棧頂結點的右子樹還未被訪問,則用同樣的方式訪問棧頂結點的右子樹,直到其右子樹被訪問後再訪問該結點,這時的訪問順序遵循瞭二叉樹的後序遍歷所要求的順序。
具體步驟如下:
- 將左路結點入棧。
- 觀察棧頂結點top。
- 若top結點的右子樹為空,或top結點的右子樹已經訪問過瞭,則訪問top結點。訪問top結點後將其從棧中彈出,並更新上一次訪問的結點為top。
- 若top結點的右子樹還未被訪問,則準備訪問其右子樹。
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; class Solution { public: //後序遍歷 vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*> st; //輔助棧 vector<int> ret; //用於存放後序遍歷的結果 TreeNode* cur = root; TreeNode* prev = nullptr; //記錄上一次訪問的結點 while (cur || !st.empty()) { //1、將左路結點入棧 while (cur) { st.push(cur); cur = cur->left; } //2、取出棧頂結點 TreeNode* top = st.top(); //3、若取出結點的右子樹為空,或右子樹已經訪問過瞭,則訪問該結點 if (top->right == nullptr || top->right == prev) { //訪問top結點後將其從棧中彈出 st.pop(); ret.push_back(top->val); //更新上一次訪問的結點為top prev = top; } else //4、若取出結點的右子樹還未被訪問,則準備訪問其右子樹 { cur = top->right; } } return ret; //返回後序遍歷結果 } };
註意: 看動圖演示時請結合所給代碼,動圖是嚴格按照代碼的邏輯制作的。
到此這篇關於C++ 非遞歸實現二叉樹的前中後序遍歷的文章就介紹到這瞭,更多相關二叉樹前中後序遍歷內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- C++實現LeetCode(144.二叉樹的先序遍歷)
- Java 數據結構中二叉樹前中後序遍歷非遞歸的具體實現詳解
- C++實現LeetCode(99.復原二叉搜索樹)
- C++實現LeetCode(100.判斷相同樹)
- C++二叉樹的直徑與合並詳解