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