前面兩篇博客介紹了線性表的順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)以及對(duì)應(yīng)的操作，并且還聊了棧與隊(duì)列的相關(guān)內(nèi)容。本篇博客我們就繼續(xù)聊數(shù)據(jù)結(jié)構(gòu)的相關(guān)東西，并且所涉及的相關(guān)Demo依然使用面向?qū)ο笳Z(yǔ)言Swift來(lái)表示。本篇博客我們就來(lái)介紹樹(shù)結(jié)構(gòu)的一種：二叉樹(shù)。在之前的博客中我們簡(jiǎn)單的聊了一點(diǎn)樹(shù)的東西，樹(shù)結(jié)構(gòu)的特點(diǎn)是除頭節(jié)點(diǎn)以外的節(jié)點(diǎn)只有一個(gè)前驅(qū)，但是可以有一個(gè)或者多個(gè)后繼。而二叉樹(shù)的特點(diǎn)是除頭結(jié)點(diǎn)外的其他節(jié)點(diǎn)只有一個(gè)前驅(qū)，節(jié)點(diǎn)的后繼不能超過(guò)2個(gè)。

本篇博客，我們只對(duì)二叉樹(shù)進(jìn)行討論。在本篇博客中，我們對(duì)二叉樹(shù)進(jìn)行創(chuàng)建，然后進(jìn)行各種遍歷，最后將二叉樹(shù)進(jìn)行線索化。在Demo實(shí)現(xiàn)之前，我們先對(duì)二叉樹(shù)的概念及其特性進(jìn)行介紹，然后在給出具體的代碼實(shí)現(xiàn)。

?

一、二叉樹(shù)的特性

上面我們已經(jīng)提到過(guò)，一個(gè)除頭結(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)只有一個(gè)前驅(qū)，有零到兩個(gè)后繼的樹(shù)即為二叉樹(shù)。在二叉樹(shù)中，一個(gè)節(jié)點(diǎn)可以有左節(jié)點(diǎn)或者左子樹(shù)，也可以有右節(jié)點(diǎn)或者右子樹(shù)。一些特殊的二叉樹(shù)，比如斜二叉樹(shù)、滿二叉樹(shù)、完全二叉樹(shù)等等就不做過(guò)多贅述了。說(shuō)這么多，不如看一張圖來(lái)的直觀。下方就是一個(gè)典型的二叉樹(shù)。

　　

了解二叉樹(shù)，理解其特性還是比較重要的?；诙鏄?shù)本身的邏輯結(jié)構(gòu)，下方是二叉樹(shù)這種數(shù)據(jù)結(jié)構(gòu)所具備的特性。

• 特性1：在二叉樹(shù)的第i層上至多有2^(i-1)（i >= 1）個(gè)節(jié)點(diǎn)。
  • 這一特性比較好理解，如果層數(shù)是從零開(kāi)始數(shù)的話，那么低i層上的節(jié)點(diǎn)數(shù)就是2^i，因?yàn)槎鏄?shù)層與層之間的節(jié)點(diǎn)數(shù)是以2的指數(shù)冪進(jìn)行增長(zhǎng)的。如果根節(jié)點(diǎn)算是第0層的話，那么第n層的節(jié)點(diǎn)數(shù)就是2^n次冪。

• 特性2：深度為k的二叉樹(shù)至多有2^k-1（k>=1）個(gè)節(jié)點(diǎn)。
  • 這一特性也是比較好理解的, 由數(shù)學(xué)上的遞加公式就可以很容易的推出來(lái)。由特性1易知每層最多有多少個(gè)節(jié)點(diǎn)，那么深度為k的話，說(shuō)明一共有k層，那么共有節(jié)點(diǎn)數(shù)為：2^0 + 2^1 + 2^2 + 2^(k-1) = 2^k - 1。

• 特性3：二叉樹(shù)的葉子節(jié)點(diǎn)數(shù)為n0, 度為2的節(jié)點(diǎn)數(shù)為n2, 那么n0 = n2 + 1。
  • 這一特性也不難理解，推出n0 = n2 + 1這個(gè)公式并不難。我們假設(shè)葉子節(jié)點(diǎn)，也就是度數(shù)為0的節(jié)點(diǎn)的個(gè)數(shù)為n0, 度數(shù)為1的節(jié)點(diǎn)為n1, 度數(shù)為2的節(jié)點(diǎn)n2。那么二叉樹(shù)的節(jié)點(diǎn)總數(shù)?n = n0 + n1 + n2。因?yàn)槌烁?jié)點(diǎn)外其余的節(jié)點(diǎn)入度都為1，所以二叉樹(shù)的度數(shù)為n-1，當(dāng)然度的個(gè)數(shù)可以使用出度來(lái)算，即為2*n2+n1，所以n-1=2*n2+n1。以n=n0+n1+n2與n-1=2*n2+n1這兩個(gè)公式我們很容易的推出n0 = n2 + 1。

• 特性4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log₂n + 1?（向下取整，比如3.5，就取3）。
  • 這個(gè)特性也是比較好理解的，基于完全二叉樹(shù)的特點(diǎn)，我們假設(shè)完全二叉樹(shù)的深度為k, 那么二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)的范圍為2^(k-1)-1 <= n <= 2^k-1。由這個(gè)表達(dá)式我們很容易推出特性4。

　

二、二叉樹(shù)的創(chuàng)建

上面介紹完二叉樹(shù)的特性后，接下來(lái)我們要做的就是將二叉樹(shù)進(jìn)行存儲(chǔ)。當(dāng)然一般存儲(chǔ)二叉樹(shù)的結(jié)構(gòu)是以二叉鏈表的形式來(lái)存儲(chǔ)的。二叉鏈表的結(jié)構(gòu)類似于雙向鏈表，二叉鏈表的節(jié)點(diǎn)也是有兩個(gè)結(jié)點(diǎn)指針的，一個(gè)指向左子樹(shù)，一個(gè)指向右子樹(shù)。接下來(lái)我們要使用二叉鏈表的形式來(lái)存儲(chǔ)我們的二叉樹(shù)。

?

1.先序創(chuàng)建二叉樹(shù)

在創(chuàng)建二叉樹(shù)之前，我們先了解一個(gè)什么是先序遍歷。先序遍歷就是先遍歷根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。我們就以此規(guī)則來(lái)創(chuàng)建二叉樹(shù)，換句話說(shuō)，我們有一個(gè)數(shù)據(jù)序列，將依照這個(gè)序列按照先序創(chuàng)建二叉樹(shù)的原則來(lái)創(chuàng)建該二叉樹(shù)，先創(chuàng)建二叉樹(shù)的根節(jié)點(diǎn)，然后再創(chuàng)建二叉樹(shù)的左子樹(shù)，然后再創(chuàng)建右子樹(shù)。而這個(gè)創(chuàng)建的二叉樹(shù)的先序遍歷的結(jié)果就是我們之前輸入的數(shù)據(jù)序列。下方就是先序創(chuàng)建二叉樹(shù)的原理圖。

　　

從上面的分析我們不難看出，我們要先創(chuàng)建根節(jié)點(diǎn)，然后創(chuàng)建左子樹(shù)，最后創(chuàng)建右子樹(shù)。因?yàn)樽笞訕?shù)和右子樹(shù)都是二叉樹(shù)，所以創(chuàng)建左子樹(shù)和右子樹(shù)是原問(wèn)題的子問(wèn)題。也就是說(shuō)子問(wèn)題與原問(wèn)題解決方案一致，這種情況下就可以使用遞歸的思想來(lái)解決。我們先將上述二叉樹(shù)的結(jié)構(gòu)轉(zhuǎn)換成二叉鏈表的形式直觀的感受一下，然后再將其使用代碼的形式進(jìn)行表示即可。下方這個(gè)截圖就是上述二叉樹(shù)的二叉鏈表的存儲(chǔ)結(jié)構(gòu)。每個(gè)節(jié)點(diǎn)都有左指針與右指針，分別自己的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。如果沒(méi)有子節(jié)點(diǎn)就為空。

　　

2.先序創(chuàng)建二叉樹(shù)的代碼實(shí)現(xiàn)

上面我們分析了二叉鏈表的結(jié)構(gòu)，接下來(lái)我們就來(lái)創(chuàng)建二叉鏈表了。首先我們得創(chuàng)建二叉鏈表的節(jié)點(diǎn)類，之前我們用C語(yǔ)言來(lái)實(shí)現(xiàn)二叉樹(shù)的時(shí)候，是使用的結(jié)構(gòu)體來(lái)實(shí)現(xiàn)的二叉鏈表的節(jié)點(diǎn)，因?yàn)镃語(yǔ)言是面向過(guò)程的語(yǔ)言，根本就沒(méi)有類這個(gè)概念。因?yàn)榇丝涛覀兪鞘褂玫拿嫦驅(qū)ο笳Z(yǔ)言，所以我就可以使用一個(gè)類來(lái)表示我們二叉鏈表的節(jié)點(diǎn)了。下方這個(gè)GeneralBinaryTreeNote就是二叉鏈表的類。data屬性存儲(chǔ)的就是樹(shù)節(jié)點(diǎn)中所存儲(chǔ)的值，而leftChild就指向左節(jié)點(diǎn)的內(nèi)存地址，而rightChild就指向右節(jié)點(diǎn)的內(nèi)存地址。

　　

上面我們已經(jīng)說(shuō)過(guò)，先序創(chuàng)建二叉樹(shù)的過(guò)程是可以用遞歸來(lái)表示的，所以我們就遞歸的去創(chuàng)建我們想要?jiǎng)?chuàng)建的二叉樹(shù)。下方就是先序創(chuàng)建二叉樹(shù)的核心代碼，self.items中存儲(chǔ)的是二叉樹(shù)的節(jié)點(diǎn)信息。經(jīng)過(guò)下方函數(shù)的遞歸執(zhí)行，就可以創(chuàng)建出我們想要的二叉樹(shù)了。從下方的遞歸過(guò)程我們就明顯的能看出是先序創(chuàng)建的二叉樹(shù)。先創(chuàng)建的根節(jié)點(diǎn)，然后遞歸創(chuàng)建左子樹(shù)，然后在遞歸創(chuàng)建右子樹(shù)。

　　

下方就是我們二叉樹(shù)的初始化過(guò)程，下方在初始化過(guò)程中主要是調(diào)用上方的這個(gè)方法，將items數(shù)組中存儲(chǔ)的值轉(zhuǎn)換成二叉鏈表的存儲(chǔ)結(jié)構(gòu)。items數(shù)組中的空字符串，表明該節(jié)點(diǎn)為空。

　　

其實(shí)上面實(shí)例中所創(chuàng)建的二叉樹(shù)的結(jié)構(gòu)就是下方的結(jié)構(gòu)。

　　

?

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

聊二叉樹(shù)怎么能沒(méi)有二叉樹(shù)的遍歷呢，下方就會(huì)給出幾種常見(jiàn)的二叉樹(shù)的遍歷方法。在遍歷二叉樹(shù)的方法中一般有先序遍歷，中序遍歷，后續(xù)遍歷，層次遍歷。本篇博客主要給出前三種遍歷方式，而層次遍歷會(huì)在圖的部分進(jìn)行介紹。二叉樹(shù)的層次遍歷其實(shí)與圖的廣度搜索是一樣的，所以這部分放到圖的相關(guān)博客中介紹。下方會(huì)給出幾種遍歷的具體方式，然后給出具體的代碼實(shí)現(xiàn)。

二叉樹(shù)的先、中、后遍歷，這個(gè)先中后指的是遍歷根節(jié)點(diǎn)的先后順序。先序遍歷：根左右，中序遍歷：左根右，后序遍歷：左右根。下方將詳細(xì)介紹到。

?

1.先序遍歷

關(guān)于先序遍歷，上面已經(jīng)介紹過(guò)一些了，接下來(lái)再進(jìn)行細(xì)化一下。先序遍歷，就是先遍歷根節(jié)點(diǎn)然后再遍歷左子樹(shù)，最后遍歷右子樹(shù)。下圖就是我們上面創(chuàng)建的二叉樹(shù)的先序遍歷的順序，由下方的示例圖就可以看出先序遍歷的規(guī)則。一句話總結(jié)下方的結(jié)構(gòu)圖：根節(jié)點(diǎn)->左節(jié)點(diǎn)->右節(jié)點(diǎn)。下方先序遍歷的順序?yàn)?#xff1a;A B D?空?空?E?空?空?C?空?F?空?空?。

　　

上面給出了原理，接下來(lái)又到了代碼實(shí)現(xiàn)的時(shí)候了。在樹(shù)的遍歷時(shí)，我們依然是采用遞歸的方式，因?yàn)闊o(wú)論是左子樹(shù)還是右子樹(shù)，都是二叉樹(shù)的范疇。所以在進(jìn)行二叉樹(shù)遍歷時(shí)，可以使用遞歸遍歷的形式。而先序遍歷莫非就是先遍歷根節(jié)點(diǎn)，然后遞歸遍歷左子樹(shù)，最后遍歷右子樹(shù)。下方就是先序遍歷的代碼實(shí)現(xiàn)。在下方代碼中，如果左節(jié)點(diǎn)或者右節(jié)點(diǎn)為空，那么我們就輸出“空”。

　　

?

2.中序遍歷

中序遍歷，與先序遍歷的不同之處在于，中序遍歷是先遍歷左子樹(shù)，然后遍歷根節(jié)點(diǎn)，最后遍歷右子樹(shù)。一句話總結(jié)：左子樹(shù)->根節(jié)點(diǎn)->右子樹(shù)。下方就是我們之前創(chuàng)建的樹(shù)的中序遍歷的結(jié)構(gòu)圖以及中序遍歷的結(jié)果。

　　?

中序遍歷的代碼實(shí)現(xiàn)與先序遍歷的代碼實(shí)現(xiàn)類似，都是使用遞歸的方式來(lái)實(shí)現(xiàn)的，只不過(guò)是先遞歸遍歷左子樹(shù)，然后遍歷根節(jié)點(diǎn)，最后遍歷右子樹(shù)。下方就是中序遍歷的代碼具體實(shí)現(xiàn)。

　　

?

3.后序遍歷

接下來(lái)聊一下二叉樹(shù)的后序遍歷。如果上面這兩種遍歷方式理解的話，那么后序遍歷也是比較好理解的。后序遍歷是先遍歷左子樹(shù)，然后再遍歷右子樹(shù)，最后遍歷根節(jié)點(diǎn)。與上方的表示方法一直，首先我們給出表示圖，如下所示：

　　

后序遍歷的代碼就不做過(guò)多贅述了，與之前兩種依然類似，只是換了一下遍歷的順序。下方就是二叉樹(shù)后序遍歷的代碼實(shí)現(xiàn)。

　　

?

4、層次遍歷

二叉樹(shù)的層次遍歷就不是二叉樹(shù)這種數(shù)據(jù)結(jié)構(gòu)所獨(dú)有的了。后面的博客中我們會(huì)介紹到圖這種數(shù)據(jù)結(jié)構(gòu)，在圖中有一個(gè)廣度搜索，放到二叉樹(shù)中就是層次遍歷。也就是說(shuō)二叉樹(shù)的層次遍歷，就是圖中以二叉樹(shù)的根節(jié)點(diǎn)為起始節(jié)點(diǎn)的廣度搜索（BFS）。本篇博客就不給出具體的代碼了，后面的博客會(huì)給出BFS的具體算法。當(dāng)然在之前的博客中有圖的BFS以及DFS。不過(guò)是C語(yǔ)言的實(shí)現(xiàn)。下方就是二叉樹(shù)層次遍歷的實(shí)例圖。

　　　　

?

四、二叉樹(shù)的線索化

二叉樹(shù)的線索化，起始就是利用二叉樹(shù)中的空的節(jié)點(diǎn)來(lái)將二叉樹(shù)轉(zhuǎn)換成鏈表的結(jié)構(gòu)。當(dāng)然只針對(duì)中序遍歷的序列。從上面中序遍歷的結(jié)果中，我們不難看出，有節(jié)點(diǎn)的值與空指針是間隔的（空?D?空?B?空?E?空?A?空?C?空?F?空）。也就是說(shuō)好多空的左指針與右指針浪費(fèi)了。二叉樹(shù)的線索化，就是在中序遍歷中，將空的左子樹(shù)的指針指向其中序遍歷結(jié)果的前驅(qū)，而空的右子樹(shù)指針指向中序遍歷中該節(jié)點(diǎn)的后繼。具體的示意圖如下所示：

　　

從上面的圖中我們不難看出。在被線索化的二叉樹(shù)中，左節(jié)點(diǎn)指針不止指向左節(jié)點(diǎn)，而且有可能指向節(jié)點(diǎn)的前驅(qū)。而右節(jié)點(diǎn)指針不僅僅是指向右節(jié)點(diǎn)的指針，還有可能指向該節(jié)點(diǎn)在中序遍歷中的后繼節(jié)點(diǎn)。為了標(biāo)記指針是指向子節(jié)點(diǎn)還是指向前驅(qū)或者后繼，所以我們要添加相應(yīng)的標(biāo)志位來(lái)標(biāo)記指針指向的是那些節(jié)點(diǎn)。下方就是我們改造后的二叉樹(shù)的節(jié)點(diǎn)：

　　

改造完節(jié)點(diǎn)后，我們就可以將二叉樹(shù)進(jìn)行線索化了，下方就是被線索話的二叉樹(shù)的代碼?？梢钥闯?#xff0c;下方的代碼的整體步驟與二叉樹(shù)的中序遍歷類似。

　　

被線索化的二叉樹(shù)就可以根據(jù)我們添加的線索進(jìn)行中序遍歷了，效率要比遞歸的中序遍歷要高的多，如下所示：

　　

?

五、測(cè)試用例

上面的代碼都是如何去實(shí)現(xiàn)了，接下來(lái)到了我們測(cè)試的時(shí)間了，下方這段代碼段是我們的測(cè)試用例。首先給出二叉樹(shù)的節(jié)點(diǎn)信息，然后先序的創(chuàng)建一棵二叉樹(shù)。然后給出二叉樹(shù)的先、中、后續(xù)遍歷，最后給出二叉樹(shù)線索話的結(jié)果。

　　?

下方截圖就是我們測(cè)試用例的運(yùn)行結(jié)果，一目了然，在此就不做過(guò)多的贅述了。

　　

本篇博客的篇幅也夠長(zhǎng)的了，就先到這兒吧，上述實(shí)例的完整Demo會(huì)在github上進(jìn)行分享, 下篇博客我們將要介紹圖的鄰接鏈表和鄰接矩陣，以及圖的BFS和DFS。

github鏈接地址：https://github.com/lizelu/DataStruct-Swift/tree/master/BinaryTree

?

轉(zhuǎn)載于:https://www.cnblogs.com/ludashi/p/5976682.html

總結(jié)

以上是生活随笔為你收集整理的算法与数据结构(三) 二叉树的遍历及其线索化(Swift版)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。