DSA 二叉樹
二叉樹
二叉樹是一種樹形資料結構，其中每個節點最多可以有兩個子節點：左子節點和右子節點。
這種每個節點最多有兩個子節點的限制，為我們帶來了許多好處。
- 遍歷、搜尋、插入和刪除等演算法更容易理解、實現和執行更快。
- 在二叉搜尋樹 (BST) 中保持資料排序，可以使搜尋非常高效。
- 使用有限數量的子節點更容易平衡樹，例如使用 AVL 二叉樹。
- 二叉樹可以表示為陣列，從而使樹更節省記憶體。
請使用下面的動畫來了解二叉樹的樣子，以及我們用來描述它的術語。
在二叉樹中，父節點或內部節點是具有一個或兩個子節點的節點。
左子節點是左側的子節點。
右子節點是右側的子節點。
樹的高度是從根節點到葉子節點的最大邊數。
二叉樹與陣列和連結串列比較
二叉樹相對於陣列和連結串列的優勢
- 陣列在直接訪問元素時速度很快，例如訪問包含 1000 個元素的陣列中的第 700 個元素。但是，插入和刪除元素需要移動其他元素以騰出新元素的位置，或者佔用已刪除元素的位置，這非常耗時。
- 連結串列在插入或刪除節點時速度很快，無需移動記憶體，但要訪問列表中的元素，必須遍歷整個列表，這需要時間。
- 與陣列和連結串列相比，二叉樹（如二叉搜尋樹和 AVL 樹）非常優秀，因為它們既能快速訪問節點，又能快速進行刪除或插入節點，且無需移動記憶體。
我們將在接下來的兩頁中詳細介紹二叉搜尋樹 (BST) 和 AVL 樹的工作原理，但首先我們將瞭解二叉樹的實現方式以及如何進行遍歷。
二叉樹的型別
有幾種不同的二叉樹變體或型別值得討論，以便更好地理解二叉樹的結構。
現在提及不同型別的二叉樹也很重要，因為這些術語和概念將在本教程的後續內容中使用。
下面是對不同型別二叉樹結構的簡要解釋，解釋下方附有這些結構的圖示，以便儘可能清晰易懂。
一個平衡的二叉樹，對於樹中的每個節點，其左右子樹的高度差最多為 1。
一個滿的二叉樹，除了最後一層外，所有層都已填滿節點，最後一層也可以是滿的，或者從左到右填滿。滿二叉樹的特性意味著它也是平衡的。
一個滿的二叉樹，是指每個節點要麼有 0 個子節點，要麼有 2 個子節點的樹。
一個完美的二叉樹，所有葉子節點都在同一層，這意味著所有層都已填滿節點，所有內部節點都有兩個子節點。完美二叉樹的特性意味著它也是滿的、平衡的和完整的。
二叉樹實現
讓我們來實現這個二叉樹。
上述二叉樹的實現方式與實現單向連結串列類似，只不過不是將每個節點連結到一個下一個節點，而是建立一種結構，使每個節點都可以連結到其左子節點和右子節點。
這就是二叉樹的實現方式
示例
Python
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
root = TreeNode('R')
nodeA = TreeNode('A')
nodeB = TreeNode('B')
nodeC = TreeNode('C')
nodeD = TreeNode('D')
nodeE = TreeNode('E')
nodeF = TreeNode('F')
nodeG = TreeNode('G')
root.left = nodeA
root.right = nodeB
nodeA.left = nodeC
nodeA.right = nodeD
nodeB.left = nodeE
nodeB.right = nodeF
nodeF.left = nodeG
# Test
print("root.right.left.data:", root.right.left.data)二叉樹遍歷
一次訪問一個節點地遍歷一棵樹，稱為遍歷。
由於陣列和連結串列是線性資料結構，它們只有一種明顯的遍歷方式：從第一個元素或節點開始，繼續訪問下一個，直到訪問完所有節點。
由於樹可以向不同方向分支（非線性），因此有不同的遍歷樹的方式。
樹的遍歷方法主要分為兩大類：
廣度優先搜尋 (BFS) 是指在訪問完同一層的節點後再訪問下一層的節點。這意味著樹的探索方向更偏向橫向。
深度優先搜尋 (DFS) 是指遍歷一直向下到葉子節點，然後逐個分支地向下探索樹。
DFS 遍歷有三種不同的型別：
這三種深度優先搜尋遍歷將在下一頁詳細介紹。
