C++二叉樹的前序中序后序非遞歸怎么實現

這篇“C++二叉樹的前序中序后序非遞歸怎么實現”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“C++二叉樹的前序中序后序非遞歸怎么實現”文章吧。

二叉樹的前序遍歷

前序遍歷的順序是根、左、右。任何一顆樹都可以認為分為左路節點，左路節點的右子樹。先訪問左路節點，再來訪問左路節點的右子樹。把訪問左路節點的右子樹看成一個子問題，就可以完整遞歸訪問了。

先定義棧st存放節點、v存放值，TreeNode* cur，cur初始化為root。

當cur不為空或者棧不為空的時候(一開始棧是空的，cur不為空)，循環繼續：先把左路節點存放進棧中，同時把值存入v中，一直循環，直到此時的左路節點為空，訪問結束。在彈出棧頂元素top，把top->right賦值給我們的cur，就可以轉化成子問題去訪問左路節點的右子樹了。

• 棧st不為空說明此時還有左路節點的右子樹還沒訪問，cur不為空說明此時還有樹要去訪問。當兩個同時為空時，循環結束，最終得到前序遍歷。

• 一個節點出棧說明這個節點及其左子樹已經訪問完了，因為我們是先把左路節點存入棧中，此時還剩右子樹沒有訪問。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> st;
        TreeNode*cur = root;
        while(!st.empty()||cur)
        {
            //左路節點
            while(cur)
            {
                st.push(cur);
                v.push_back(cur->val);
                cur = cur->left;
            }
            //左路節點右子樹
            TreeNode* top = st.top();
            st.pop();
            cur = top->right;//轉化成子問題訪問右子樹
        }
        return v;
    }
};

二叉樹的中序遍歷

中序遍歷是左、根、右。左子樹訪問完之后才能去訪問根。左路節點一直走直到左子樹訪問完，入棧的過程中不去進行訪問（存放數值到v中），當左路節點出棧之后，也就是從棧中彈出進行訪問。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> st;
        TreeNode*cur = root;
        while(cur||!st.empty())
        {
            while(cur)
            {
                //不訪問
                st.push(cur);
                cur = cur->left;
            }
            TreeNode*top = st.top();
            //進行訪問
            v.push_back(top->val);
            st.pop();
            cur = top->right;
        }
        return v;
    }
};

二叉樹的后序遍歷

后序的遍歷順序是左、右、根。與前面的相比，比較麻煩，我們需要把左子樹和右子樹訪問完再去訪問根。我們定義一個棧，在棧里面取到一個節點時：右子樹是否訪問過，如果沒有訪問，迭代子問題訪問，如果訪問過了，則訪問這個根節點，pop出棧

如果top的右子樹為空或者右子樹已經訪問過了（上一個訪問節點是右子樹的根），那么說明右子樹不用訪問或者訪問過了，可以訪問根top;當右子樹不為空，且沒有訪問過，則迭代子問題訪問。

通過prev來判斷上一次訪問的節點：如果prev等于top->right時，表示棧頂節點的右子樹已經訪問過了，可以彈出棧頂節點并訪問它。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> st;
        TreeNode*cur = root;
        TreeNode*prev = nullptr;
        while(cur||!st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode*top = st.top();
            //top的右子樹為空，或者右子樹已經訪問過了（上一個訪問節點時右子樹的根）那么說明右子樹不用訪問或者訪問過了，可以訪問根top
            //右子樹不為空，且沒有訪問， 則迭代子問題訪問
            if(top->right==nullptr||top->right==prev)
            {
                st.pop();
                v.push_back(top->val);
                prev = top;
            }
            else
            {
                cur = top->right;
            }
        }
        return v;
    }
};

以上就是關于“C++二叉樹的前序中序后序非遞歸怎么實現”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業資訊頻道。