二叉樹的遍歷

1：前序遍歷

• 在這個圖中，我們把1 ，2 ，4三個節點壓入了棧中
  • 在壓入棧的時候，直接讀取
• 然后我們把2彈出來
  • 判斷右邊是不是為空，如果不為空
    • 按照第一步的方法，以該節點為根節點，把左子節點壓入棧中，壓入的時候進行讀取
  • 如果為空，就什么都不做

#include<iostream> #include<vector> #include<stack>using namespace std;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) {vector<int> res;if(root == nullptr) return res;stack<TreeNode*> mystack;while(root != nullptr){res.push_back(root->val);mystack.push(root);root = root->left;}while(!mystack.empty()){TreeNode* temp = mystack.top();mystack.pop();if(temp->right != nullptr){TreeNode* newNode = temp->right;cout << newNode->val;while(newNode != nullptr){res.push_back(newNode->val);mystack.push(newNode);newNode = newNode->left;}}}for(int i = 0; i < res.size(); i++){cout << res[i] << " ";}cout << endl;return res;} };

2：中序遍歷

• 結果是 4 2 6 5 7 1 3
• 將左子節點壓入棧中，1，2，4
• 將他們彈出來，然后彈出來之后進行訪問

// 在前序的基礎上，壓入的時候不進行遍歷，彈出的時候進行遍歷

3：后續遍歷

• 結果是4 6 7 5 2 3 1
• 我們還是壓入左子樹
• 彈出了四
  • 此時判斷右子樹沒有，我們遍歷4
• 彈出了二
  • 此時右子樹是有的，所以我們將5 和 6 進行彈入
• 彈出6，此時可以遍歷
• 彈出5，此時右子樹有7，什么時候進行打印呢？？

——————————————————學習——————————————

• 棧和空的，root 不為空
• 將1，2，4壓入到棧中
• 將4彈出來
  • 判斷4的右邊是不是為空，或者是是不是上次的prev，為空，直接讀取，將prev設置為4，root 設置為null
• 將2彈出來
  • 判斷2的右邊不為空，
    • 將2探進去，把5，6探進去
    • 把6 彈出來
    • 把5彈出來
    • 右邊的元素不是prev，所以要再彈出來

#include<iostream> #include<vector> #include<stack>using namespace std;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) {vector<int> res;stack<TreeNode *> mystack;TreeNode* prev;while(root != nullptr || !mystack.empty()){while(root != nullptr){mystack.push(root);root = root->left;}root = mystack.top();mystack.pop();if(root->right == nullptr or root->right == prev){res.push_back(root->val);prev = root;root = nullptr;}else{mystack.push(root);root = root->right;}}return res;} };

總結

以上是生活随笔為你收集整理的二叉树的遍历（前，中，后）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。