快捷導(dǎo)航

C++二叉樹的前序中序后序非遞歸實(shí)現(xiàn)方法詳細(xì)講解

更新時(shí)間：2023年03月08日 11:23:25 作者：平凡的人1

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

二叉樹的前序遍歷

前序遍歷的順序是根、左、右。任何一顆樹都可以認(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;
    }
};

總結(jié)

二叉樹的前序遍歷、中序遍歷、后序遍歷的非遞歸遍歷三種方法都是類似的，差別在于訪問棧頂?shù)脑氐臅r(shí)機(jī)不同,訪問控制不同。其中前序和中序大致相同，而后序需要去進(jìn)行判斷棧頂?shù)挠易訕淝闆r。

到此這篇關(guān)于C++二叉樹的前序中序后序非遞歸實(shí)現(xiàn)方法詳細(xì)講解的文章就介紹到這了,更多相關(guān)C++二叉樹的前序中序后序?qū)崿F(xiàn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: