數(shù)據(jù)結(jié)構(gòu)中你需要知道的關(guān)于樹的一切
當(dāng)你剛開始學(xué)習(xí)編程的時候，將數(shù)組作為“主要數(shù)據(jù)結(jié)構(gòu)”來學(xué)習(xí)是很常見的。
最終，你也會學(xué)習(xí)到哈希表。如果你正在攻讀計算機(jī)科學(xué)學(xué)位，你肯定需要參加一門數(shù)據(jù)結(jié)構(gòu)的課程。在課上你將會學(xué)到鄰接鏈表、隊列和棧。這些數(shù)據(jù)結(jié)構(gòu)都被稱作是“線性”的，因為他們都有邏輯上的起點(diǎn)和終點(diǎn)。
當(dāng)我們開始學(xué)習(xí)樹和圖的時候，這兩個數(shù)據(jù)結(jié)構(gòu)確實會讓人困惑，因為它們存儲數(shù)據(jù)不是線性方式了。這兩種數(shù)據(jù)結(jié)構(gòu)都用特定的方式存儲數(shù)據(jù)。
這篇文章幫助你更好的理解樹形數(shù)據(jù)結(jié)構(gòu)并幫你弄清楚你對它的疑問。
本篇文章我們將會學(xué)習(xí)到：
- 樹是什么?
- 樹的例子
- 樹的術(shù)語及其工作原理
- 如何用代碼實現(xiàn)樹形結(jié)構(gòu)
讓我們開始學(xué)習(xí)之旅吧。:)
定義
當(dāng)開始編程時，人們更容易理解線性數(shù)據(jù)結(jié)構(gòu)，而不是像樹和圖這樣的數(shù)據(jù)結(jié)構(gòu)。
樹是眾所周知的非線性數(shù)據(jù)結(jié)構(gòu)。它們不以線性方式存儲數(shù)據(jù)，而是按層次組織數(shù)據(jù)。
讓我們舉個現(xiàn)實生活中的例子
當(dāng)我說層次方式意味著什么?
想象一個有所有輩分關(guān)系的家譜：祖父母、父母、子女、兄弟姐妹們等等。我們通常按層次結(jié)構(gòu)組織家譜。
上面的圖是我的家譜。Tossico 、Akikazu 、Hitomi 和 Takemi 是我的祖父母。
Toshiaki 和 Juliana 是我的父母。
TK 、Yuji 、Bruno 和 Kaio 是我父母的孩子(我和我的兄弟們)。
另一個層次結(jié)構(gòu)的例子是企業(yè)的組織結(jié)構(gòu)。
在 HTML 中，文檔對象模型(DOM)是樹形結(jié)構(gòu)的。
HTML 標(biāo)簽包含其他的標(biāo)簽。我們有一個 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ù)語定義
樹是被稱為節(jié)點(diǎn)的元素的集合。節(jié)點(diǎn)通過邊連接。每個節(jié)點(diǎn)都有一個值或數(shù)據(jù)。每個節(jié)點(diǎn)也可能有或者沒有子節(jié)點(diǎn)。
樹的首節(jié)點(diǎn)是這個樹的根(root)節(jié)點(diǎn)。如果這個根節(jié)點(diǎn)連接了另一個節(jié)點(diǎn)，那么，另一個節(jié)點(diǎn)稱作這個節(jié)點(diǎn)的子節(jié)點(diǎn)。
所有樹節(jié)點(diǎn)都由邊連接。它是樹的重要組成部分, 因為它管理節(jié)點(diǎn)之間的關(guān)系。
葉節(jié)點(diǎn)是樹上的***一個節(jié)點(diǎn)。他們是沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)中的樹像真正的樹, 有根, 樹枝, 和葉子。
要理解的其他重要概念是樹的高度和深度。
- 樹的高度是葉節(jié)點(diǎn)的最長路徑的長度。
- 節(jié)點(diǎn)的深度是從其到根的路徑的長度。
術(shù)語摘要
- 根是樹的最頂端結(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)。
- 高度是 樹 到葉子結(jié)點(diǎn)的長度。
- 深度是 結(jié)點(diǎn) 到根結(jié)點(diǎn)的長度。
二叉樹
現(xiàn)在我們來討論一個特殊的樹類型。我們把它叫作二叉樹。
“在計算機(jī)科學(xué)領(lǐng)域，二叉樹是一種樹形數(shù)據(jù)結(jié)構(gòu)，它的每個節(jié)點(diǎn)最多有兩個孩子，被叫作左孩子和右孩”
我們來看一個二叉樹的例子。
我們來寫一個二叉樹
在實現(xiàn)一個二叉樹時，我們首先要注意的是，二叉樹是節(jié)點(diǎn)的集合。每一個節(jié)點(diǎn)有三個屬性：值(value)， 左孩子( left_child) ，以及右孩子( right_child)。
那么我們怎么才能實現(xiàn)一個有這三個屬性的簡單二叉樹呢?
- class BinaryTree:
- def __init__(self, value):
- self.value = value
- self.left_child = None
- self.right_child = None
好，這就是我們的二叉樹類。
當(dāng)我們實例化一個對象時，我們把值(節(jié)點(diǎn)的相關(guān)數(shù)據(jù))作為參數(shù)傳遞給類?？瓷厦骖惖淖蠛⒆雍陀液⒆?。兩個都被賦值為None。
為什么?
因為當(dāng)我們創(chuàng)建節(jié)點(diǎn)時，它還沒有孩子，只有節(jié)點(diǎn)數(shù)據(jù)。
測試下代碼。
- tree = BinaryTree('a')
- print(tree.value) # a
- print(tree.left_child) # None
- print(tree.right_child) # None
好了。
我們可以將字符串'a'作為值傳給二叉樹節(jié)點(diǎn)。如果將值、左孩子、右孩子輸出的話，我們就可以看到這個值了。
下面開始插入部分的操作。那么我們需要做些什么工作呢?
有兩個要求：
- 如果當(dāng)前的節(jié)點(diǎn)沒有左孩子，我們就創(chuàng)建一個新節(jié)點(diǎn)，然后將其設(shè)置為當(dāng)前節(jié)點(diǎn)的左孩子。
- 如果已經(jīng)有了左孩子，我們就創(chuàng)建一個新節(jié)點(diǎn)，并將其放在當(dāng)前左孩子節(jié)點(diǎn)的位置。然后再將左孩子節(jié)點(diǎn)置為新節(jié)點(diǎn)的左孩子。
畫出來就像下面這樣。:)
下面是插入操作的代碼：
- 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)建一個新節(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
好了。:)
但是這還不算完成。我們得測試一下。
我們來構(gòu)造一個像下面這樣的樹：
總結(jié)分析下這棵樹：
- 有一個根節(jié)點(diǎn)
- b是左孩子
- c是右孩子
- b的右孩子是d(b沒有左孩子)
- c的左孩子是e
- c的右孩子是f
- e和f都沒有孩子
下面是整棵樹的實現(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)在，我們來思考一下樹的遍歷。
遍歷樹有兩種選擇：深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)。
- DFS是用來遍歷或搜索樹數(shù)據(jù)結(jié)構(gòu)的算法。從根節(jié)點(diǎn)開始，在回溯之前沿著每一個分支盡可能遠(yuǎn)的探索。
- BFS是用來遍歷或搜索樹數(shù)據(jù)結(jié)構(gòu)的算法。從根節(jié)點(diǎn)開始，在探索下一層鄰居節(jié)點(diǎn)前，首先探索同一層的鄰居節(jié)點(diǎn)。
下面，我們來深入了解每一種遍歷算法。
深度優(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)無子孩子)
- 回溯，并進(jìn)入右孩子(4)。輸出之。(此節(jié)點(diǎn)無子孩子)
- 回溯到根節(jié)點(diǎn)，然后進(jìn)入其右孩子(5)。輸出之。
- 進(jìn)入左孩子(6)。輸出之。(此節(jié)點(diǎn)無子孩子)
- 回溯，并進(jìn)入右孩子(7)。輸出之。(此節(jié)點(diǎn)無子孩子)
- 完成。
當(dāng)我們深入到葉節(jié)點(diǎn)時回溯，這就被稱為 DFS 算法。
既然我們對這種遍歷算法已經(jīng)熟悉了，我們將討論下 DFS 的類型：前序、中序和后序。
前序遍歷
這和我們在上述示例中的作法基本類似。
- 輸出節(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)在讓我們編碼實現(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)先，之后是右孩子，中間的***。
讓我們編碼實現(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)
- 進(jìn)入左孩子并輸出之。這當(dāng)且僅當(dāng)它擁有左孩子。
- 進(jìn)入右孩子并輸出之。這當(dāng)且僅當(dāng)它擁有右孩子。
- 輸出節(jié)點(diǎn)的值。
