通常在開始學(xué)編程的時候，你會接觸一些常用數(shù)據(jù)結(jié)構(gòu)。

[[275700]]

到最后一般會學(xué)到哈希表。對于修讀計算機科學(xué)學(xué)位的朋友，你通常要上專門的數(shù)據(jù)結(jié)構(gòu)課，從了解有關(guān)鏈表、隊列和棧的各種知識。這些統(tǒng)稱為線性數(shù)據(jù)結(jié)構(gòu)，因為依邏輯次序從頭排到尾。

當你開始進入下一階段，學(xué)習(xí)樹和圖結(jié)構(gòu)時，事情就會顯得比處理線性數(shù)據(jù)結(jié)構(gòu)復(fù)雜很多。這促使我們專門寫一篇文章來探討“樹”這種特定的數(shù)據(jù)結(jié)構(gòu)幫大家答疑解惑。

本文內(nèi)容包括:

• 樹的定義樹的結(jié)構(gòu)工作原理代碼實現(xiàn)

現(xiàn)在就開始學(xué)習(xí)吧 :)

樹的定義

通常對編程新手來說，線性數(shù)據(jù)結(jié)構(gòu)比樹和圖要更好理解。我們此處所說的樹，即是以層次化方式組織和存放數(shù)據(jù)的特定數(shù)據(jù)結(jié)構(gòu)。

實例解析

為了理解“層次化”的意思，我們以家譜為例：里面有祖父母、父母、孩子、兄弟姐妹。這就是用層次化的模式來構(gòu)建家譜。

上圖就是我的家譜。Tossico，Akikazu，Hitomi和Takemi作為我的祖父母和外祖父母處于最頂層。Toshiaki 和 Juliana是我父母。TK，Yuji，Bruno 和 Kaio 則是我和我的的兄弟姐妹們。

公司組織也是類似的層次化結(jié)構(gòu)

HTML的文檔模型對象 (DOM) 就是一棵樹最頂層 HTML 標簽連接到 head 標簽和 body 標簽。二者又有對應(yīng)的子標簽，比如 head 含有 meta 和 title 標簽，body 含有與可視化內(nèi)容相關(guān)的 h1, a, li等標簽。名詞定義

樹(tree)：是以邊(edge)相連的結(jié)點(node)的集合，每個結(jié)點存儲對應(yīng)的值(value/data)，當存在子結(jié)點時與之相連。

根結(jié)點(root)：是樹的首個結(jié)點，在相連兩結(jié)點中更接近根結(jié)點的成為父結(jié)點(parent node)，相應(yīng)的另一個結(jié)點稱為子結(jié)點(parent node)。

邊(edge)：所有結(jié)點都由邊相連，用于標識結(jié)點間的關(guān)系。邊是樹中很重要的一個概念，因為我們用它來確定節(jié)點之間的關(guān)系。

葉子結(jié)點(Leaves)：是樹的末端結(jié)點，他們沒有子結(jié)點，就像真實的樹那樣 ，由根開始，伸展枝干，到葉為止。

樹高(height)與結(jié)點深度(depth)也是很重要的概念。樹高：是由根結(jié)點出發(fā)，到子結(jié)點的最長路徑長度。結(jié)點深度：是指對應(yīng)結(jié)點到根結(jié)點路徑長度。

二叉樹

現(xiàn)在來探討一種特殊的樹結(jié)構(gòu)-二叉樹(binary tree)，它每個節(jié)點最多有兩個子結(jié)點，亦稱左孩子和右孩子。

在計算機科學(xué)中，二叉樹是一種“樹”數(shù)據(jù)結(jié)構(gòu)，樹上的每個節(jié)點最多有兩個孩子，分別為左孩和右孩。——維基百科

來看一個二叉樹的實例。

動手寫二叉樹

首先明確我們要實現(xiàn)的對象是一個結(jié)點集合，每個結(jié)點有三個屬性：值(value), 左孩子(left_child)和右孩子(right_child)。

寫出來會是這個樣子：

我們寫了一個BinaryTree類，在初始化實際對象的時候傳入對應(yīng)值，并在此時還沒有子結(jié)點的情況下將左右孩子設(shè)為空。

為什么要這么做呢?

因為當我們創(chuàng)建節(jié)點的時候，它還沒有孩子，我們只有節(jié)點數(shù)據(jù)。

讓我們測試一下：

下面到了插入結(jié)點的操作：在樹還沒有對應(yīng)子結(jié)點時新建結(jié)點，并賦值給現(xiàn)有結(jié)點對應(yīng)變量。否則，新建結(jié)點連接并替換掉現(xiàn)有位置子結(jié)點。

畫出來是這個樣子：

相應(yīng)代碼(左右相同)：

為了進一步測試，讓我們構(gòu)建一個更復(fù)雜一些的樹：

這棵樹共有六個結(jié)點，其中結(jié)點b沒有左孩子。對應(yīng)初始化并插入結(jié)點的代碼如下：

下一步讓我們看看如何對樹進行遍歷。

一般來講我們有兩種遍歷方式：深度優(yōu)先遍歷(DFS)和 廣度優(yōu)先遍歷(BFS)，前者沿著特定路徑遍歷到根結(jié)點再轉(zhuǎn)換臨近路徑繼續(xù)遍歷，后者逐層遍歷整個樹結(jié)構(gòu)。來看具體的例子：

深度優(yōu)先遍歷 (DFS)

DFS會沿特定路徑遍歷到葉子結(jié)點再回溯 (backtracking)進入臨近路徑繼續(xù)遍歷。以下面的樹結(jié)構(gòu)為例：

遍歷順序為1–2–3–4–5–6–7

具體來講，我們會先訪問根結(jié)點1再訪問其左孩子2，接著是2的左孩子3，到達葉子結(jié)點回溯一步，訪問2的右孩子4，進一步回溯，繼續(xù)順序訪問5，6和7。在輸出遍歷結(jié)果時，據(jù)父結(jié)點值相對子結(jié)點輸出順序的不同，深度優(yōu)先遍歷又可細分為先序、中序和后序遍歷三種情況。

先序遍歷

即直接按照我們對結(jié)點的訪問順序輸出遍歷結(jié)果即實現(xiàn)，父結(jié)點值被最先輸出。代碼：

中序遍歷

中序遍歷輸出結(jié)果為：3–2–4–1–6–5–7。

左孩子值最先輸出，然后是父結(jié)點，最后是右孩子。對應(yīng)代碼如下：

后序遍歷

后序遍歷輸出結(jié)果為：3–4–2–6–7–5–1.

左右孩子值依次輸出，最后是父結(jié)點，對應(yīng)代碼如下：

廣度優(yōu)先搜索 (BFS)

BFS：按照結(jié)點深度逐層遍歷樹結(jié)構(gòu)。

再拿上面的圖來實際解釋這種方法：

逐層每層從左到右進行遍歷，對應(yīng)遍歷結(jié)果為：1–2–5–3–4–6–7。對應(yīng)代碼如下：

你應(yīng)該已經(jīng)注意到了，我們要借助先進先出(FIFO)的隊列(queue)結(jié)構(gòu)完成操作，具體的出入隊列順序如下圖所示：

二叉搜索樹

二叉搜索樹又名有序二叉樹，結(jié)點元素按固定次序排布，使得我們可以在進行查找等操作時使用二分搜索提高效率。——維基百科

它最明顯的特征是父結(jié)點值大于左子樹任意結(jié)點值，小于右子樹任意結(jié)點值。

上圖以三個二叉樹為例，哪個才是正確的呢?

A 左右子樹需要進行交換。B 滿足條件，是二叉搜索樹。C 值為4的結(jié)點需要移至3的右孩子處

接下來進行二叉搜索插入、結(jié)點檢索、結(jié)點刪除以及平衡的解釋。

插入

假設(shè)以這種順序插入結(jié)點: 50, 76, 21, 4, 32, 100, 64, 52。50會是我們初始的根結(jié)點。

再依次進行如下操作：

76 大于50，置于右邊21 小于 50, 置于左邊4 置于21左邊

最終一氣呵成我們會得到下面這棵樹：

發(fā)現(xiàn)規(guī)律了么?像開車一樣，從根結(jié)點駛?cè)耄迦胫荡笥诋斍敖Y(jié)點值向右開否則向左開知道找到空位停車入庫。(嘀嘀嘀，老司機)

代碼實現(xiàn)也很簡單：

這個算法最牛逼的地方在于他的遞歸部分，你知道是哪幾行嗎?

結(jié)點檢索

其實結(jié)合我們的插入操作，檢索的方法就顯而易見，依舊從根結(jié)點開始，小于對應(yīng)結(jié)點值左轉(zhuǎn)，大于右轉(zhuǎn)，等于報告找到，走到葉子結(jié)點都沒找到 gg，就報沒有該元素。例如我們想知道下圖中有沒有52這個值：

代碼如下：

刪除: 移除并重構(gòu)

刪除操作要更復(fù)雜一些，因為要處理三種不同情況：

情景 #1：葉子結(jié)點

是最簡單的情況，直接刪除就好.

情景 #2：只有左孩子或右孩子

該情景等價于鏈表上的結(jié)點刪除，把當前結(jié)點刪除并讓其子結(jié)點替換自己原來位置。

情景 #3：同時具有左右孩子的結(jié)點

找到該結(jié)點右子樹中最小值所在的結(jié)點，剔除要刪除的當前結(jié)點并把最小值結(jié)點提升到空缺位置。

一些別的操作

清零：將三個屬性全部置None即可。

找到最小值：從根節(jié)點開始，一直左轉(zhuǎn)，直到找不到任何結(jié)點為止，此時我們就找到了最小值。

恭喜你學(xué)完本篇內(nèi)容!數(shù)據(jù)結(jié)構(gòu)中的樹的內(nèi)容大致如此，趕緊收藏起來吧