快捷導(dǎo)航

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

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

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

一、二叉樹(shù)的前序遍歷

題目鏈接

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

解釋?zhuān)?/p>

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

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

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

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)化成子問(wèn)題訪問(wèn)右子樹(shù)
        }
        return v;
    }
};

二、二叉樹(shù)的中序遍歷

題目鏈接

因?yàn)橹行虮闅v的訪問(wèn)順序是左根右，跟前序遍歷不同，所以我們讓左節(jié)點(diǎn)入棧的時(shí)候先不訪問(wèn)，出棧（說(shuō)明左子樹(shù)訪問(wèn)完了）時(shí)在訪問(wèn)節(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;
    }
};

三、二叉樹(shù)的后序遍歷

3.1 方法一

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

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è)問(wèn)題：

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

1?? 從左子樹(shù)回來(lái)，現(xiàn)在要先訪問(wèn)右子樹(shù)

2?? 從右子樹(shù)回來(lái)，左右子樹(shù)已經(jīng)訪問(wèn)完畢，再訪問(wèn)根。

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

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

您可能感興趣的文章: