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

[[275700]]

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

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

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

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

現(xiàn)在就開始學習吧 :)

樹的定義

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

實例解析

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

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

公司組織也是類似的層次化結構

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

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

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

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

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

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

二叉樹

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

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

來看一個二叉樹的實例。

動手寫二叉樹

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

寫出來會是這個樣子：

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

為什么要這么做呢?

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

讓我們測試一下：

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

畫出來是這個樣子：

相應代碼(左右相同)：

為了進一步測試，讓我們構建一個更復雜一些的樹：

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

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

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

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

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

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

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

先序遍歷

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

中序遍歷

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

左孩子值最先輸出，然后是父結點，最后是右孩子。對應代碼如下：

后序遍歷

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

左右孩子值依次輸出，最后是父結點，對應代碼如下：

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

BFS：按照結點深度逐層遍歷樹結構。

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

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

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

二叉搜索樹

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

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

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

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

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

插入

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

再依次進行如下操作：

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

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

發(fā)現(xiàn)規(guī)律了么?像開車一樣，從根結點駛入，待插入值大于當前結點值向右開否則向左開知道找到空位停車入庫。(嘀嘀嘀，老司機)

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

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

結點檢索

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

代碼如下：

刪除: 移除并重構

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

情景 #1：葉子結點

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

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

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

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

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

一些別的操作

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

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

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