數(shù)據(jù)結(jié)構(gòu)中你需要知道的關(guān)于樹的一切

作者：佚名 2017-11-14 13:48:26

當(dāng)我們開始學(xué)習(xí)樹和圖的時(shí)候，這兩個(gè)數(shù)據(jù)結(jié)構(gòu)確實(shí)會(huì)讓人困惑，因?yàn)樗鼈兇鎯?chǔ)數(shù)據(jù)不是線性方式了。這兩種數(shù)據(jù)結(jié)構(gòu)都用特定的方式存儲(chǔ)數(shù)據(jù)。這篇文章幫助你更好的理解樹形數(shù)據(jù)結(jié)構(gòu)并幫你弄清楚你對(duì)它的疑問。

當(dāng)你剛開始學(xué)習(xí)編程的時(shí)候，將數(shù)組作為“主要數(shù)據(jù)結(jié)構(gòu)”來(lái)學(xué)習(xí)是很常見的。

最終，你也會(huì)學(xué)習(xí)到哈希表。如果你正在攻讀計(jì)算機(jī)科學(xué)學(xué)位，你肯定需要參加一門數(shù)據(jù)結(jié)構(gòu)的課程。在課上你將會(huì)學(xué)到鄰接鏈表、隊(duì)列和棧。這些數(shù)據(jù)結(jié)構(gòu)都被稱作是“線性”的，因?yàn)樗麄兌加羞壿嬌系钠瘘c(diǎn)和終點(diǎn)。

這篇文章幫助你更好的理解樹形數(shù)據(jù)結(jié)構(gòu)并幫你弄清楚你對(duì)它的疑問。

[[209900]]

本篇文章我們將會(huì)學(xué)習(xí)到：

樹是什么?
樹的例子
樹的術(shù)語(yǔ)及其工作原理
如何用代碼實(shí)現(xiàn)樹形結(jié)構(gòu)

讓我們開始學(xué)習(xí)之旅吧。:)

定義

當(dāng)開始編程時(shí)，人們更容易理解線性數(shù)據(jù)結(jié)構(gòu)，而不是像樹和圖這樣的數(shù)據(jù)結(jié)構(gòu)。

樹是眾所周知的非線性數(shù)據(jù)結(jié)構(gòu)。它們不以線性方式存儲(chǔ)數(shù)據(jù)，而是按層次組織數(shù)據(jù)。

讓我們舉個(gè)現(xiàn)實(shí)生活中的例子

當(dāng)我說(shuō)層次方式意味著什么?

想象一個(gè)有所有輩分關(guān)系的家譜：祖父母、父母、子女、兄弟姐妹們等等。我們通常按層次結(jié)構(gòu)組織家譜。

上面的圖是我的家譜。Tossico 、Akikazu 、Hitomi 和 Takemi 是我的祖父母。

Toshiaki 和 Juliana 是我的父母。

TK 、Yuji 、Bruno 和 Kaio 是我父母的孩子(我和我的兄弟們)。

另一個(gè)層次結(jié)構(gòu)的例子是企業(yè)的組織結(jié)構(gòu)。

在 HTML 中，文檔對(duì)象模型(DOM)是樹形結(jié)構(gòu)的。

HTML 標(biāo)簽包含其他的標(biāo)簽。我們有一個(gè) head 標(biāo)簽和 body 標(biāo)簽。這些標(biāo)簽包含特點(diǎn)的元素。head 標(biāo)簽中有 meta 和 title 標(biāo)簽。body 標(biāo)簽中有在用戶界面展示的標(biāo)簽，如 h1 、a 、li 等等。

術(shù)語(yǔ)定義

樹是被稱為節(jié)點(diǎn)的元素的集合。節(jié)點(diǎn)通過邊連接。每個(gè)節(jié)點(diǎn)都有一個(gè)值或數(shù)據(jù)。每個(gè)節(jié)點(diǎn)也可能有或者沒有子節(jié)點(diǎn)。

樹的首節(jié)點(diǎn)是這個(gè)樹的根(root)節(jié)點(diǎn)。如果這個(gè)根節(jié)點(diǎn)連接了另一個(gè)節(jié)點(diǎn)，那么，另一個(gè)節(jié)點(diǎn)稱作這個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)。

所有樹節(jié)點(diǎn)都由邊連接。它是樹的重要組成部分, 因?yàn)樗芾砉?jié)點(diǎn)之間的關(guān)系。

葉節(jié)點(diǎn)是樹上的***一個(gè)節(jié)點(diǎn)。他們是沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)中的樹像真正的樹, 有根, 樹枝, 和葉子。

要理解的其他重要概念是樹的高度和深度。

樹的高度是葉節(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度。
節(jié)點(diǎn)的深度是從其到根的路徑的長(zhǎng)度。

術(shù)語(yǔ)摘要

根是樹的最頂端結(jié)點(diǎn)。
邊是兩個(gè)結(jié)點(diǎn)之間的連接。
子結(jié)點(diǎn)是具有父節(jié)點(diǎn)的結(jié)點(diǎn)。
父結(jié)點(diǎn)是與子節(jié)點(diǎn)有連接的結(jié)點(diǎn)。
葉子結(jié)點(diǎn)是樹中沒有子結(jié)點(diǎn)的結(jié)點(diǎn)。
高度是樹到葉子結(jié)點(diǎn)的長(zhǎng)度。
深度是結(jié)點(diǎn) 到根結(jié)點(diǎn)的長(zhǎng)度。

二叉樹

現(xiàn)在我們來(lái)討論一個(gè)特殊的樹類型。我們把它叫作二叉樹。

“在計(jì)算機(jī)科學(xué)領(lǐng)域，二叉樹是一種樹形數(shù)據(jù)結(jié)構(gòu)，它的每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子，被叫作左孩子和右孩”

我們來(lái)看一個(gè)二叉樹的例子。

我們來(lái)寫一個(gè)二叉樹

在實(shí)現(xiàn)一個(gè)二叉樹時(shí)，我們首先要注意的是，二叉樹是節(jié)點(diǎn)的集合。每一個(gè)節(jié)點(diǎn)有三個(gè)屬性：值(value)，左孩子( left_child) ，以及右孩子( right_child)。

那么我們?cè)趺床拍軐?shí)現(xiàn)一個(gè)有這三個(gè)屬性的簡(jiǎn)單二叉樹呢?

class BinaryTree: 
    def __init__(self, value): 
        self.value = value 
        self.left_child = None 
        self.right_child = None

好，這就是我們的二叉樹類。

當(dāng)我們實(shí)例化一個(gè)對(duì)象時(shí)，我們把值(節(jié)點(diǎn)的相關(guān)數(shù)據(jù))作為參數(shù)傳遞給類。看上面類的左孩子和右孩子。兩個(gè)都被賦值為None。

為什么?

因?yàn)楫?dāng)我們創(chuàng)建節(jié)點(diǎn)時(shí)，它還沒有孩子，只有節(jié)點(diǎn)數(shù)據(jù)。

測(cè)試下代碼。

tree = BinaryTree('a') 
print(tree.value) # a 
print(tree.left_child) # None 
print(tree.right_child) # None

好了。

我們可以將字符串'a'作為值傳給二叉樹節(jié)點(diǎn)。如果將值、左孩子、右孩子輸出的話，我們就可以看到這個(gè)值了。

下面開始插入部分的操作。那么我們需要做些什么工作呢?

有兩個(gè)要求：

如果當(dāng)前的節(jié)點(diǎn)沒有左孩子，我們就創(chuàng)建一個(gè)新節(jié)點(diǎn)，然后將其設(shè)置為當(dāng)前節(jié)點(diǎn)的左孩子。
如果已經(jīng)有了左孩子，我們就創(chuàng)建一個(gè)新節(jié)點(diǎn)，并將其放在當(dāng)前左孩子節(jié)點(diǎn)的位置。然后再將左孩子節(jié)點(diǎn)置為新節(jié)點(diǎn)的左孩子。

畫出來(lái)就像下面這樣。:)

下面是插入操作的代碼：

def insert_left(self, value): 
    if self.left_child == None: 
        self.left_child = BinaryTree(value) 
    else: 
        new_node = BinaryTree(value) 
        new_node.left_child = self.left_child 
        self.left_child = new_node

再次強(qiáng)調(diào)，如果當(dāng)前節(jié)點(diǎn)沒有左孩子，我們就創(chuàng)建一個(gè)新節(jié)點(diǎn)，并將其置為當(dāng)前節(jié)點(diǎn)的左孩子。否則，就將新節(jié)點(diǎn)放在左孩子的位置，再將原左孩子置為新節(jié)點(diǎn)的左孩子。

同樣，我們編寫插入右孩子的代碼。

def insert_right(self, value): 
    if self.right_child == None: 
        self.right_child = BinaryTree(value) 
    else: 
        new_node = BinaryTree(value) 
        new_node.right_child = self.right_child 
        self.right_child = new_node

好了。:)

但是這還不算完成。我們得測(cè)試一下。

我們來(lái)構(gòu)造一個(gè)像下面這樣的樹：

總結(jié)分析下這棵樹：

有一個(gè)根節(jié)點(diǎn)
b是左孩子
c是右孩子
b的右孩子是d(b沒有左孩子)
c的左孩子是e
c的右孩子是f
e和f都沒有孩子

下面是整棵樹的實(shí)現(xiàn)代碼：

a_node = BinaryTree('a') 
a_node.insert_left('b') 
a_node.insert_right('c') 
 
b_node = a_node.left_child 
b_node.insert_right('d') 
 
c_node = a_node.right_child 
c_node.insert_left('e') 
c_node.insert_right('f') 
 
d_node = b_node.right_child 
e_node = c_node.left_child 
f_node = c_node.right_child 
 
print(a_node.value) # a 
print(b_node.value) # b 
print(c_node.value) # c 
print(d_node.value) # d 
print(e_node.value) # e 
print(f_node.value) # f

好，插入結(jié)束。

現(xiàn)在，我們來(lái)思考一下樹的遍歷。

遍歷樹有兩種選擇：深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)。

DFS是用來(lái)遍歷或搜索樹數(shù)據(jù)結(jié)構(gòu)的算法。從根節(jié)點(diǎn)開始，在回溯之前沿著每一個(gè)分支盡可能遠(yuǎn)的探索。
BFS是用來(lái)遍歷或搜索樹數(shù)據(jù)結(jié)構(gòu)的算法。從根節(jié)點(diǎn)開始，在探索下一層鄰居節(jié)點(diǎn)前，首先探索同一層的鄰居節(jié)點(diǎn)。

下面，我們來(lái)深入了解每一種遍歷算法。

深度優(yōu)先搜索(Depth-First Search，DFS)

DFS 在回溯和搜索其他路徑之前找到一條到葉節(jié)點(diǎn)的路徑。讓我們看看這種類型的遍歷的示例。

此算法的結(jié)果是 1–2–3–4–5–6–7 。

為什么呢?

讓我們分解下。

從根節(jié)點(diǎn)(1)開始。輸出之。
進(jìn)入左孩子(2)。輸出之。
然后進(jìn)入左孩子(3)。輸出之。(此節(jié)點(diǎn)無(wú)子孩子)
回溯，并進(jìn)入右孩子(4)。輸出之。(此節(jié)點(diǎn)無(wú)子孩子)
回溯到根節(jié)點(diǎn)，然后進(jìn)入其右孩子(5)。輸出之。
進(jìn)入左孩子(6)。輸出之。(此節(jié)點(diǎn)無(wú)子孩子)
回溯，并進(jìn)入右孩子(7)。輸出之。(此節(jié)點(diǎn)無(wú)子孩子)
完成。

當(dāng)我們深入到葉節(jié)點(diǎn)時(shí)回溯，這就被稱為 DFS 算法。

既然我們對(duì)這種遍歷算法已經(jīng)熟悉了，我們將討論下 DFS 的類型：前序、中序和后序。

前序遍歷

這和我們?cè)谏鲜鍪纠械淖鞣ɑ绢愃啤?/p>

輸出節(jié)點(diǎn)的值。
進(jìn)入其左孩子并輸出之。當(dāng)且僅當(dāng)它擁有左孩子。
進(jìn)入右孩子并輸出之。當(dāng)且僅當(dāng)它擁有右孩子。

def pre_order(self): 
    print(self.value) 
 
    if self.left_child: 
        self.left_child.pre_order() 
 
    if self.right_child: 
        self.right_child.pre_order()

中序遍歷

示例中此樹的中序算法的結(jié)果是3–2–4–1–6–5–7。

左孩子優(yōu)先，之后是中間，***是右孩子。

現(xiàn)在讓我們編碼實(shí)現(xiàn)之。

def in_order(self): 
    if self.left_child: 
        self.left_child.in_order() 
 
    print(self.value) 
 
    if self.right_child: 
        self.right_child.in_order()

進(jìn)入左孩子并輸出之。當(dāng)且僅當(dāng)它有左孩子。
輸出節(jié)點(diǎn)的值。
進(jìn)入右孩子并輸出之。當(dāng)且僅當(dāng)它有右孩子。

后序遍歷

以此樹為例的后序算法的結(jié)果為 3–4–2–6–7–5–1 。

左孩子優(yōu)先，之后是右孩子，中間的***。

讓我們編碼實(shí)現(xiàn)吧。

def post_order(self): 
    if self.left_child: 
        self.left_child.post_order() 
 
    if self.right_child: 
        self.right_child.post_order() 
 
    print(self.value)