c++ 圖解層序遍歷與逐層列印智慧指標所建造的二元樹

二元樹是極為常見的資料結構，關於如何遍歷其中元素的文章更是無數。然而大多數文章都是講解的前序/中序/後序遍歷，有關逐層打印元素的文章並不多，已有文章的講解也較為晦澀讀起來不得要領。本文將以形象的圖片加上清晰的程式碼幫助你理解層序遍歷的實現，同時我們使用現代c 提供的智慧指標來簡化樹狀資料結構的資源管理。

相關教學：資料結構樹教學

那麼現在讓我們進入正題。

使用智慧指標建立二元樹

我們這裡所要實現的是一個簡單地模擬了二元搜尋樹的二元樹，提供符合二元搜尋樹的要求的插入功能個中序遍歷。同時我們使用shared_ptr來管理資源。

現在我們只實作insert和ldr兩個方法，其餘方法的實作並不是本文所關心的內容，不過我們會在後續的文章中逐個介紹：

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_;
    // 左右子节点
    std::shared_ptr<BinaryTreeNode> left;
    std::shared_ptr<BinaryTreeNode> right;

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

我們的node物件繼承自enable_shared_from_this，通常這不是必須的，但是為了在層序遍歷時方便操作，我們需要從this構造智慧指針，因此這步是必須的。 insert會將比root小的元素插入左子樹，比root大的插入到右子樹；ldr則是最為常規的中序遍歷，這裡實現它是為了以常規方式查看tree中的所有元素。

值得注意的是，對於node節點我們最好使用make_shared進行創建，而不是將其初始化為全域/局部對象，否則在層序遍歷時會因為 shared_ptr的析構進而導致物件被銷毀，進而引發未定義行為。

現在假設我們有一組資料：[3, 1, 0, 2, 5, 4, 6, 7]，將第一個元素作為root，將所有資料插入我們的樹中會得到如下的一棵二元樹：

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);

可以看到節點一共分成了四層，現在我們需要逐層列印，該怎麼做呢？

層序遍歷

其實思路很簡單，我們採用廣度優先的思路，先將節點的孩子都列印，然後再去列印子節點的孩子。

以上圖為例，我們先列印根節點的值3，然後我們再列印它的所有子節點的值，是1和 5，然後是左右子節點的子節點，以此類推。 。 。 。 。 。

說起來很簡單，但程式碼寫起來卻會遇到麻煩。我們不能簡單得像中序遍歷時那樣使用遞歸來解決問題（事實上可以用改進的遞歸演算法），因為它會直接來到葉子節點處，這不是我們想要的結果。不過不要緊，我們可以藉助於隊列，把子節點隊列添加到隊列末尾，然後從隊列開頭也就是根節點處遍歷，將其子節點添加進隊列，隨後再對第二個節點做同樣的操作，遇到一行結束的地方，我們使用nullptr做標記。

先看具體的程式碼：

std::vector<std::shared_ptr<BinaryTreeNode>>
BinaryTreeNode::layer_contents()
{
    std::vector<std::shared_ptr<BinaryTreeNode>> nodes;
    // 先添加根节点，根节点自己就会占用一行输出，所以添加了作为行分隔符的nullptr
    // 因为需要保存this，所以这是我们需要继承enable_shared_from_this是理由
    // 同样是因为这里，当返回的结果容器析构时this的智能指针也会析构
    // 如果我们使用了局部变量则this的引用计数从1减至0，导致对象被销毁，而使用了make_shared创建的对象引用计数是从2到1，没有问题
    nodes.push_back(shared_from_this());
    nodes.push_back(nullptr);
    // 我们使用index而不是迭代器，是因为添加元素时很可能发生迭代器失效，处理这一问题将会耗费大量精力，而index则无此烦恼
    for (int index = 0; index < nodes.size(); ++index) {
        if (!nodes[index]) {
            // 子节点打印完成或已经遍历到队列末尾
            if (index == nodes.size()-1) {
                break;
            }

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

        if (nodes[index]->left) { // 将当前节点的子节点都添加进队列
            nodes.push_back(nodes[index]->left);
        }
        if (nodes[index]->right) {
            nodes.push_back(nodes[index]->right);
        }
    }

    return nodes;
}

程式碼本身並不複雜，重要的是背後的想法。

演算法圖解

如果你第一遍並沒有讀懂這段程式碼也不要緊，下面我們有請圖解上線：

先是迴圈開始時的狀態，第一行的內容已經確定了(^代表空指標)：

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

接著索引值1，這次遍歷到的是nullptr，因為不是在佇列末尾，所以我們簡單地加入一個nullptr在佇列末尾，這樣第二行的節點就都在佇列中了：

然後我們開始遍歷第二行的節點，將它們的子節點當作第三行的內容放入佇列，最後加上一個行分隔符，以此類推：

#簡單來說，就是透過佇列來快取上一行的所有節點，然後再根據上一行的快取得到下一行的所有節點，循環往復直到二元樹的最後一層。當然不只是二元樹，其他多叉樹的層序遍歷也可以用類似的想法來實現。

好了，知道如何取得每一行的內容，我們就能逐行處理節點了：

void BinaryTreeNode::layer_print()
{
    auto nodes = layer_contents();
    for (auto iter = nodes.begin(); iter != nodes.end(); ++iter) {
        // 空指针代表一行结束，这里我们遇到空指针就输出换行符
        if (*iter) {
            std::cout << (*iter)->value_ << " ";
        } else {
            std::cout << "\n";
        }
    }
}

如你所见，这个方法足够简单，我们把节点信息保存在额外的容器中是为了方便做进一步的处理，如果只是打印的话大可不必这么麻烦，不过简单通常是有代价的。对于我们的实现来说，分隔符的存在简化了我们对层级之间的区分，然而这样会导致浪费至少log2(n)+1个vector的存储空间，某些情况下可能引起性能问题，而且通过合理得使用计数变量可以避免这些额外的空间浪费。当然具体的实现读者可以自己挑战一下，原理和我们上面介绍的是类似的因此就不在赘述了，也可以参考园内其他的博客文章。

测试

最后让我们看看完整的测试程序，记住要用make_shared创建root实例：

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();
}

输出：

可以看到上半部分是中序遍历的结果，下半部分是层序遍历的输出，而且是逐行打印的，不过我们没有做缩进。所以不太美观。

另外你可能已经发现了，我们没有写任何有关资源释放的代码，没错，这就是智能指针的威力，只要注意资源的创建，剩下的事都可以放心得交给智能指针处理，我们可以把更多的精力集中在算法和功能的实现上。

如有错误和疑问欢迎指出！

以上是c++ 圖解層序遍歷與逐層列印智慧指標所建造的二元樹的詳細內容。更多資訊請關注PHP中文網其他相關文章！