Go 資料結構：二元搜尋樹
在這篇文章中，我們將分析和實現二元搜尋樹的資料結構。 樹 是一個有階層結構的表示法。通常我們可以通過想像一個家族的族譜樹來理解樹的概念。 二元搜尋樹是一種每個節點最多有兩個子節點的樹。 二元搜尋樹具有左節點的值小於右節點的值的特性。 這是我們在本文中要建構的資料結構。它是一個非常有用的資料結構，可以有效地存儲和索引數據，並且可以快速檢索數據。 詞彙定義： 根：樹的第 0 層 子節點：除了根節點以外的每個節點 內部節點：具有至少一個子節點的節點 葉節點：沒有子節點的每個節點 子樹：以特定節點為根的一組節點 預備信息： 一個二元搜尋樹資料結構將公開以下方法： Insert(t)：插入項目 t 到樹中 Search(t)：如果項目 t 存在於樹中，則返回 true InOrderTraverse()：按中序遍歷訪問所有節點 PreOrderTraverse()：按先序遍歷訪問所有節點 PostOrderTraverse()：按後序遍歷訪問所有節點 Min()：返回存儲在樹中的最小值項目 Max()：返回存儲在樹中的最大值項目 Remove(t)：從樹中刪除項目 t String()：打印可讀取的樹形結構 我將創建一個 ItemBinarySearchTree 的泛型類型，並且支持併發，它可以通過使用 genny 來生成包含任何類型的樹，從而封裝了包含數據的實際值特定資料結構。 我將節點定義為： // Node 組成樹的單個節點 type Node struct { key int value Item left *Node // 左節點 right *Node // 右節點 } 這個 key 值允許使用任何類型的項目，並且使用一個單獨的值來計算正確的位置。我實現它為整數，但它可以使用任何可以進行比較的類型。 將項目插入樹中需要使用遞歸，因為我們需要找到確定的位置來插入它。規則是，如果節點的鍵值小於當前節點的鍵值，我們將其作為左子節點插入，如果沒有左子節點。否則，我們使用左子節點作為基礎節點重新計算位置。對於右子節點也是同樣的原則。 遍歷是指遍歷樹的過程。我們實現三種不同的方法來遍歷，因為有三種不同的方法。以二元搜尋樹為例： 我們可以以以下方式進行遍歷： 中序遍歷：通過遵循最小鏈接來訪問所有節點，直到找到最左側的葉節點，然後處理該葉節點，通過進入與當前節點關聯的下一個最小鍵值來移動到其他節點。在上面的圖中，遍歷順序為：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11。 先序遍歷：在訪問子節點之前，先訪問節點本身。在上面的圖中，遍歷順序為：8 -> 4 -> 2 -> 1 -> 3 -> 6 -> 5 -> 7 -> 10 -> 9 -> 11。 後序遍歷：找到最小的葉節點（最左側的葉節點），然後處理它的兄弟節點和父節點，然後進入下一個子樹，並向上遍歷到父節點。在上面的圖中，遍歷順序為：1 -> 3 -> 2 -> 5 -> 7 -> 6 -> 4 -> 9 -> 11 -> 10 -> 8。 我們在測試中使用的 String 方法會打印出上述樹的可視化結果：...