C++二叉樹的前序中序后序非遞歸怎么實(shí)現(xiàn)

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

二叉樹的前序遍歷

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

先定義棧st存放節(jié)點(diǎn)、v存放值，TreeNode* cur，cur初始化為root。

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

• 棧st不為空說明此時(shí)還有左路節(jié)點(diǎn)的右子樹還沒訪問，cur不為空說明此時(shí)還有樹要去訪問。當(dāng)兩個(gè)同時(shí)為空時(shí)，循環(huán)結(jié)束，最終得到前序遍歷。

• 一個(gè)節(jié)點(diǎn)出棧說明這個(gè)節(jié)點(diǎn)及其左子樹已經(jīng)訪問完了，因?yàn)槲覀兪窍劝炎舐饭?jié)點(diǎn)存入棧中，此時(shí)還剩右子樹沒有訪問。

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

二叉樹的中序遍歷

中序遍歷是左、根、右。左子樹訪問完之后才能去訪問根。左路節(jié)點(diǎn)一直走直到左子樹訪問完，入棧的過程中不去進(jìn)行訪問（存放數(shù)值到v中），當(dāng)左路節(jié)點(diǎn)出棧之后，也就是從棧中彈出進(jìn)行訪問。

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();
            //進(jìn)行訪問
            v.push_back(top->val);
            st.pop();
            cur = top->right;
        }
        return v;
    }
};

二叉樹的后序遍歷

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

如果top的右子樹為空或者右子樹已經(jīng)訪問過了（上一個(gè)訪問節(jié)點(diǎn)是右子樹的根），那么說明右子樹不用訪問或者訪問過了，可以訪問根top;當(dāng)右子樹不為空，且沒有訪問過，則迭代子問題訪問。

通過prev來判斷上一次訪問的節(jié)點(diǎn)：如果prev等于top->right時(shí)，表示棧頂節(jié)點(diǎn)的右子樹已經(jīng)訪問過了，可以彈出棧頂節(jié)點(diǎn)并訪問它。

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的右子樹為空，或者右子樹已經(jīng)訪問過了（上一個(gè)訪問節(jié)點(diǎn)時(shí)右子樹的根）那么說明右子樹不用訪問或者訪問過了，可以訪問根top
            //右子樹不為空，且沒有訪問， 則迭代子問題訪問
            if(top->right==nullptr||top->right==prev)
            {
                st.pop();
                v.push_back(top->val);
                prev = top;
            }
            else
            {
                cur = top->right;
            }
        }
        return v;
    }
};

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