作者：apocelipes?

鏈接：https://www.cnblogs.com/apocelipes/p/10758692.html

二叉樹是極為常見的數據結構，關于如何遍歷其中元素的文章更是數不勝數。

然而大多數文章都是講解的前序/中序/后序遍歷，有關逐層打印元素的文章并不多，已有文章的講解也較為晦澀讀起來不得要領。本文將用形象的圖片加上清晰的代碼幫助你理解層序遍歷的實現，同時我們使用現代c++提供的智能指針來簡化樹形數據結構的資源管理。

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

使用智能指針構建二叉樹

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

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

struct?BinaryTreeNode:?public?std::enable_shared_from_this?{
????explicit?BinaryTreeNode(const?int?value?=?0)
????:?value_{value},?left{std::shared_ptr{}},?right{std::shared_ptr{}}
????{}
????void?insert(const?int?value)
????{if?(value?????????????if?(left)?{
????????????????left->insert(value);
????????????}?else?{
????????????????left?=?std::make_shared(value);
????????????}
????????}if?(value?>?value_)?{if?(right)?{
????????????????right->insert(value);
????????????}?else?{
????????????????right?=?std::make_shared(value);
????????????}
????????}
????}//?中序遍歷
????void?ldr()
????{if?(left)?{
????????????left->ldr();
????????}
????????std::cout?<"\n";if?(right)?{
????????????right->ldr();
????????}
????}//?分層打印
????void?layer_print();
????int?value_;//?左右子節點
????std::shared_ptr?left;
????std::shared_ptr?right;private://?層序遍歷
????std::vector<:shared_ptr>>?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(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::layer_contents()
{std::vector<std::shared_ptr>?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?????????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?<value_?<"?";
????????}?else?{
????????????std::cout?<"\n";
????????}
????}
}

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

測試

最后讓我們看看完整的測試程序，記住要用make_shared創建root實例：

int?main()
{
????auto?root?=?std::make_shared(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();
}

輸出：

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

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

智能指針和層序遍歷的內容到這里就結束了，在下一篇文章中我們還將看到智能指針和二叉樹的更多操作。

---

●編號492，輸入編號直達本文

●輸入m獲取文章目錄

C語言與C++編程

分享C/C++技術文章

總結

以上是生活随笔為你收集整理的bartender一行打印两个二次开发_C++ 智能指针和二叉树：图解层序遍历和逐层打印二叉树...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。