Go 資料結構:二元搜尋樹
在這篇文章中,我們將分析和實現二元搜尋樹的資料結構。
樹 是一個有階層結構的表示法。通常我們可以通過想像一個家族的族譜樹來理解樹的概念。
二元搜尋樹是一種每個節點最多有兩個子節點的樹。
二元搜尋樹具有左節點的值小於右節點的值的特性。
這是我們在本文中要建構的資料結構。它是一個非常有用的資料結構,可以有效地存儲和索引數據,並且可以快速檢索數據。
詞彙定義:
- 根:樹的第 0 層
- 子節點:除了根節點以外的每個節點
- 內部節點:具有至少一個子節點的節點
- 葉節點:沒有子節點的每個節點
- 子樹:以特定節點為根的一組節點
預備信息:
一個二元搜尋樹資料結構將公開以下方法:
Insert(t)
:插入項目 t 到樹中Search(t)
:如果項目 t 存在於樹中,則返回 trueInOrderTraverse()
:按中序遍歷訪問所有節點PreOrderTraverse()
:按先序遍歷訪問所有節點PostOrderTraverse()
:按後序遍歷訪問所有節點Min()
:返回存儲在樹中的最小值項目Max()
:返回存儲在樹中的最大值項目Remove(t)
:從樹中刪除項目 tString()
:打印可讀取的樹形結構
我將創建一個 ItemBinarySearchTree
的泛型類型,並且支持併發,它可以通過使用 genny
來生成包含任何類型的樹,從而封裝了包含數據的實際值特定資料結構。
我將節點定義為:
1 | // 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
方法會打印出上述樹的可視化結果:
1 | ------------------------------------------------ |
下面是實現所需的代碼:
1 | // Package binarysearchtree 創建 ItemBinarySearchTree 的 Item 型資料結構 |
測試:
下面的測試描述了上述實現的用法。
1 | package binarysearchtree |
創建具體的樹資料結構:
您可以使用此泛型實現生成特定類型的樹,例如:
- 生成
IntBinarySearchTree
,其中元素的類型是int
:
1 | genny -in binarysearchtree.go -out binarysearchtree-int.go gen "Item=int" |
- 生成
StringBinarySearchTree
,其中元素的類型是string
:
1 | genny -in binarysearchtree.go -out binarysearchtree-string.go gen "Item=string" |
tags: [“Go”, “Data Structures”, “Binary Search Tree”, “Golang”]