如何使用c++圖解層序遍歷和逐層打印智能指針建造的二叉樹-創(chuàng)新互聯(lián)

本篇文章為大家展示了如何使用c++ 圖解層序遍歷和逐層打印智能指針建造的二叉樹，代碼簡明扼要并且容易理解，絕對(duì)能使你眼前一亮，通過這篇文章的詳細(xì)介紹希望你能有所收獲。

創(chuàng)新互聯(lián)建站-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比怒江州網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式怒江州網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋怒江州地區(qū)。費(fèi)用合理售后完善，十載實(shí)體公司更值得信賴。

二叉樹是極為常見的數(shù)據(jù)結(jié)構(gòu)，關(guān)于如何遍歷其中元素的文章更是數(shù)不勝數(shù)。然而大多數(shù)文章都是講解的前序/中序/后序遍歷，有關(guān)逐層打印元素的文章并不多，已有文章的講解也較為晦澀讀起來不得要領(lǐng)。本文將用形象的圖片加上清晰的代碼幫助你理解層序遍歷的實(shí)現(xiàn)，同時(shí)我們使用現(xiàn)代c++提供的智能指針來簡化樹形數(shù)據(jù)結(jié)構(gòu)的資源管理。

使用智能指針構(gòu)建二叉樹

我們這里所要實(shí)現(xiàn)的是一個(gè)簡單地模擬了二叉搜索樹的二叉樹，提供符合二叉搜索樹的要求的插入功能個(gè)中序遍歷。同時(shí)我們使用shared_ptr來管理資源。

現(xiàn)在我們只實(shí)現(xiàn)insert和ldr兩個(gè)方法，其余方法的實(shí)現(xiàn)并不是本文所關(guān)心的內(nèi)容，不過我們會(huì)在后續(xù)的文章中逐個(gè)介紹：

struct BinaryTreeNode: public std::enable_shared_from_this<BinaryTreeNode> {
    explicit BinaryTreeNode(const int value = 0)
    : value_{value}, left{std::shared_ptr<BinaryTreeNode>{}}, right{std::shared_ptr<BinaryTreeNode>{}}
    {}

    void insert(const int value)
    {
        if (value < value_) {
            if (left) {
                left->insert(value);
            } else {
                left = std::make_shared<BinaryTreeNode>(value);
            }
        }

        if (value > value_) {
            if (right) {
                right->insert(value);
            } else {
                right = std::make_shared<BinaryTreeNode>(value);
            }
        }
    }

    // 中序遍歷
    void ldr()
    {
        if (left) {
            left->ldr();
        }

        std::cout << value_ << "\n";

        if (right) {
            right->ldr();
        }
    }

    // 分層打印
    void layer_print();

    int value_;
    // 左右子節(jié)點(diǎn)
    std::shared_ptr<BinaryTreeNode> left;
    std::shared_ptr<BinaryTreeNode> right;

private:
    // 層序遍歷
    std::vector<std::shared_ptr<BinaryTreeNode>> layer_contents();
};

我們的node對(duì)象繼承自enable_shared_from_this，通常這不是必須的，但是為了在層序遍歷時(shí)方便操作，我們需要從this構(gòu)造智能指針，因此這步是必須的。insert會(huì)將比root小的元素插入左子樹，比root大的插入到右子樹；ldr則是最為常規(guī)的中序遍歷，這里實(shí)現(xiàn)它是為了以常規(guī)方式查看tree中的所有元素。

值得注意的是，對(duì)于node節(jié)點(diǎn)我們最好使用make_shared進(jìn)行創(chuàng)建，而不是將其初始化為全局/局部對(duì)象，否則在層序遍歷時(shí)會(huì)因?yàn)?code>shared_ptr的析構(gòu)進(jìn)而導(dǎo)致對(duì)象被銷毀，從而引發(fā)未定義行為。

現(xiàn)在假設(shè)我們有一組數(shù)據(jù)：[3, 1, 0, 2, 5, 4, 6, 7]，將第一個(gè)元素作為root，將所有數(shù)據(jù)插入我們的樹中會(huì)得到如下的一棵二叉樹：

auto root = std::make_shared<BinaryTreeNode>(3);
root->insert(1);
root->insert(0);
root->insert(2);
root->insert(5);
root->insert(4);
root->insert(6);
root->insert(7);

可以看到節(jié)點(diǎn)一共分成了四層，現(xiàn)在我們需要逐層打印，該怎么做呢？

層序遍歷

其實(shí)思路很簡單，我們采用廣度優(yōu)先的思路，先將節(jié)點(diǎn)的孩子都打印，然后再去打印子節(jié)點(diǎn)的孩子。

以上圖為例，我們先打印根節(jié)點(diǎn)的值3，然后我們?cè)俅蛴∷乃凶庸?jié)點(diǎn)的值，是1和5，然后是左右子節(jié)點(diǎn)的子節(jié)點(diǎn)，以此類推。。。。。。

說起來很簡單，但是代碼寫起來卻會(huì)遇到麻煩。我們不能簡單得像中序遍歷時(shí)那樣使用遞歸來解決問題（事實(shí)上可以用改進(jìn)的遞歸算法），因?yàn)樗鼤?huì)直接來到葉子節(jié)點(diǎn)處，這不是我們想要的結(jié)果。不過不要緊，我們可以借助于隊(duì)列，把子節(jié)點(diǎn)隊(duì)列添加到隊(duì)列末尾，然后從隊(duì)列開頭也就是根節(jié)點(diǎn)處遍歷，將其子節(jié)點(diǎn)添加進(jìn)隊(duì)列，隨后再對(duì)第二個(gè)節(jié)點(diǎn)做同樣的操作，遇到一行結(jié)束的地方，我們使用nullptr做標(biāo)記。

先看具體的代碼：

std::vector<std::shared_ptr<BinaryTreeNode>>
BinaryTreeNode::layer_contents()
{
    std::vector<std::shared_ptr<BinaryTreeNode>> nodes;
    // 先添加根節(jié)點(diǎn)，根節(jié)點(diǎn)自己就會(huì)占用一行輸出，所以添加了作為行分隔符的nullptr
    // 因?yàn)樾枰４鎡his，所以這是我們需要繼承enable_shared_from_this是理由
    // 同樣是因?yàn)檫@里，當(dāng)返回的結(jié)果容器析構(gòu)時(shí)this的智能指針也會(huì)析構(gòu)
    // 如果我們使用了局部變量則this的引用計(jì)數(shù)從1減至0，導(dǎo)致對(duì)象被銷毀，而使用了make_shared創(chuàng)建的對(duì)象引用計(jì)數(shù)是從2到1，沒有問題
    nodes.push_back(shared_from_this());
    nodes.push_back(nullptr);
    // 我們使用index而不是迭代器，是因?yàn)樘砑釉貢r(shí)很可能發(fā)生迭代器失效，處理這一問題將會(huì)耗費(fèi)大量精力，而index則無此煩惱
    for (int index = 0; index < nodes.size(); ++index) {
        if (!nodes[index]) {
            // 子節(jié)點(diǎn)打印完成或已經(jīng)遍歷到隊(duì)列末尾
            if (index == nodes.size()-1) {
                break;
            }

            nodes.push_back(nullptr); // 添加分隔符
            continue;
        }

        if (nodes[index]->left) { // 將當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)都添加進(jìn)隊(duì)列
            nodes.push_back(nodes[index]->left);
        }
        if (nodes[index]->right) {
            nodes.push_back(nodes[index]->right);
        }
    }

    return nodes;
}

代碼本身并不復(fù)雜，重要的是其背后的思想。

算法圖解

如果你第一遍并沒有讀懂這段代碼也不要緊，下面我們有請(qǐng)圖解上線：

首先是循環(huán)開始時(shí)的狀態(tài)，第一行的內(nèi)容已經(jīng)確定了(^代表空指針)：

然后我們從首元素開始遍歷，第一個(gè)遍歷到的是root，他有兩個(gè)孩子，值分別是1和5：

接著索引值+1，這次遍歷到的是nullptr，因?yàn)椴皇窃陉?duì)列末尾，所以我們簡單添加一個(gè)nullptr在隊(duì)列末尾，這樣第二行的節(jié)點(diǎn)就都在隊(duì)列中了：

隨后我們開始遍歷第二行的節(jié)點(diǎn)，將它們的子節(jié)點(diǎn)作為第三行的內(nèi)容放入隊(duì)列，最后加上一個(gè)行分隔符，以此類推：

簡單來說，就是通過隊(duì)列來緩存上一行的所有節(jié)點(diǎn)，然后再根據(jù)上一行的緩存得到下一行的所有節(jié)點(diǎn)，循環(huán)往復(fù)直到二叉樹的最后一層。當(dāng)然不只是二叉樹，其他多叉樹的層序遍歷也可以用類似的思想實(shí)現(xiàn)。

好了，知道了如何獲取每一行的內(nèi)容，我們就能逐行處理節(jié)點(diǎn)了：

void BinaryTreeNode::layer_print()
{
    auto nodes = layer_contents();
    for (auto iter = nodes.begin(); iter != nodes.end(); ++iter) {
        // 空指針代表一行結(jié)束，這里我們遇到空指針就輸出換行符
        if (*iter) {
            std::cout << (*iter)->value_ << " ";
        } else {
            std::cout << "\n";
        }
    }
}

如你所見，這個(gè)方法足夠簡單，我們把節(jié)點(diǎn)信息保存在額外的容器中是為了方便做進(jìn)一步的處理，如果只是打印的話大可不必這么麻煩，不過簡單通常是有代價(jià)的。對(duì)于我們的實(shí)現(xiàn)來說，分隔符的存在簡化了我們對(duì)層級(jí)之間的區(qū)分，然而這樣會(huì)導(dǎo)致浪費(fèi)至少log2(n)+1個(gè)vector的存儲(chǔ)空間，某些情況下可能引起性能問題，而且通過合理得使用計(jì)數(shù)變量可以避免這些額外的空間浪費(fèi)。當(dāng)然具體的實(shí)現(xiàn)讀者可以自己挑戰(zhàn)一下，原理和我們上面介紹的是類似的因此就不在贅述了，也可以參考園內(nèi)其他的博客文章。

測試

最后讓我們看看完整的測試程序，記住要用make_shared創(chuàng)建root實(shí)例：

int main()
{
    auto root = std::make_shared<BinaryTreeNode>(3);
    root->insert(1);
    root->insert(0);
    root->insert(2);
    root->insert(5);
    root->insert(4);
    root->insert(6);
    root->insert(7);
    root->ldr();
    std::cout << "\n";
    root->layer_print();
}

輸出：

可以看到上半部分是中序遍歷的結(jié)果，下半部分是層序遍歷的輸出，而且是逐行打印的，不過我們沒有做縮進(jìn)。所以不太美觀。

另外你可能已經(jīng)發(fā)現(xiàn)了，我們沒有寫任何有關(guān)資源釋放的代碼，沒錯(cuò)，這就是智能指針的威力，只要注意資源的創(chuàng)建，剩下的事都可以放心得交給智能指針處理，我們可以把更多的精力集中在算法和功能的實(shí)現(xiàn)上。

上述內(nèi)容就是如何使用c++ 圖解層序遍歷和逐層打印智能指針建造的二叉樹，你們學(xué)到知識(shí)或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

本文標(biāo)題：如何使用c++圖解層序遍歷和逐層打印智能指針建造的二叉樹-創(chuàng)新互聯(lián)
網(wǎng)站URL：http://muchs.cn/article26/coiocg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、網(wǎng)頁設(shè)計(jì)公司、自適應(yīng)網(wǎng)站、靜態(tài)網(wǎng)站、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站排名

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)