C++實(shí)現(xiàn)二叉樹非遞歸遍歷算法詳解

更新時(shí)間：2023年04月23日 09:14:48 作者：命由己造～

在C++中，二叉樹非遞歸遍歷是一種常用的算法，可避免遞歸過程中的系統(tǒng)開銷和棧溢出問題。非遞歸遍歷算法利用棧數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，可以實(shí)現(xiàn)前序、中序和后序遍歷，是C++程序員必備技能之一

一、二叉樹的前序遍歷

題目鏈接

我們可以把任何一棵樹看成左路節(jié)點(diǎn)，左路節(jié)點(diǎn)和右子樹。先訪問左路節(jié)點(diǎn)，再訪問左路節(jié)點(diǎn)的右子樹。在右子樹中也重復(fù)這種循環(huán)，就是非遞歸遍歷二叉樹的思想。

解釋：

棧st存放節(jié)點(diǎn)，v存放數(shù)值，cur初始化為root。

循環(huán)條件是棧不為空或者cur不為空(訪問最后一個(gè)節(jié)點(diǎn)之前棧就已經(jīng)為空了)，循環(huán)遍歷左子樹并且把左子樹入棧，同時(shí)把值存入v中。然后彈出棧頂元素，并且把棧頂元素的右子樹賦值給cur，這樣就形成了遍歷。

當(dāng)棧不為空的時(shí)候說明還有左路節(jié)點(diǎn)的右子樹沒有被訪問，當(dāng)cur不為空的時(shí)候說明還有樹要被訪問。當(dāng)同時(shí)為空的時(shí)候才是訪問完成。當(dāng)一個(gè)節(jié)點(diǎn)出棧的時(shí)候說明此時(shí)該節(jié)點(diǎn)及該節(jié)點(diǎn)的左子樹已經(jīng)被訪問完成了。

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

二、二叉樹的中序遍歷

題目鏈接

因?yàn)橹行虮闅v的訪問順序是左根右，跟前序遍歷不同，所以我們讓左節(jié)點(diǎn)入棧的時(shí)候先不訪問，出棧（說明左子樹訪問完了）時(shí)在訪問節(jié)點(diǎn)。

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

三、二叉樹的后序遍歷

3.1 方法一

首先我們知道后序遍歷就是左右根，而我們可以把訪問順序變成根右左，然后再逆置順序。而根右左就跟前序遍歷的方法一樣：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur = root;
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                v.push_back(cur->val);
                cur = cur->right;
            }
            TreeNode* node = st.top();
            st.pop();
            cur = node->left;
        }
        reverse(v.begin(), v.end());
        return v;
    }
};

3.2 方法二

按照常規(guī)的遍歷方法走左右根，但是這里有一個(gè)問題：

當(dāng)訪問到根的時(shí)候有兩種情況：

1?? 從左子樹回來，現(xiàn)在要先訪問右子樹

2?? 從右子樹回來，左右子樹已經(jīng)訪問完畢，再訪問根。

針對(duì)這種情況我們可以在加一個(gè)變量來確定是第幾次訪問根，如果是第一次就訪問右子樹，如果是第二次就訪問。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<pair<TreeNode*, bool>> st;
        vector<int> v;
        TreeNode* cur = root;
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(make_pair(cur, false));
                cur = cur->left;
            }
            TreeNode* node = st.top().first;
            if(st.top().second == true)
            {
                st.pop();
                v.push_back(node->val);
            }
            else
            {
                st.top().second = true;
                cur = node->right;
            }
        }
        return v;
    }
};

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

您可能感興趣的文章: