Data Structures

在這篇文章中，我們將分析和實現二元搜尋樹的資料結構。 樹 是一個有階層結構的表示法。通常我們可以通過想像一個家族的族譜樹來理解樹的概念。 二元搜尋樹是一種每個節點最多有兩個子節點的樹。 二元搜尋樹具有左節點的值小於右節點的值的特性。 這是我們在本文中要建構的資料結構。它是一個非常有用的資料結構，可以有效地存儲和索引數據，並且可以快速檢索數據。 詞彙定義： 根：樹的第 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 方法會打印出上述樹的可視化結果：...

佇列（Queue）和堆疊（Stack）相似，但插入點和移除點不同。 我們在佇列的一端新增項目，而在另一端移除項目。 這種結構被稱為「先進先出」（First In, First Out，FIFO）。 就像你可以想像的任何佇列，例如在餐廳、舞廳或者等待進入音樂會大廳時。 以下是使用JavaScript實現佇列的可能實作，使用私有類別欄位（Private Class Fields），內部儲存使用陣列： class Queue { #items = [] enqueue = (item) => this.#items.splice(0, 0, item) dequeue = () => this.#items.pop() isempty = () => this.#items.length === 0 empty = () => (this.#items.length = 0) size = () => this.#items.length } 以下是使用方式：首先從類別初始化一個物件，然後呼叫其方法： 使用 enqueue() 添加項目 使用 dequeue() 從佇列中取出項目 範例： const queue = new Queue() queue.enqueue(1) queue.enqueue(2) queue.enqueue(3) queue.size() //3 queue.dequeue() //1 queue.dequeue() //2 queue....

鏈結串列是你可以學習到的最重要的資料結構之一。 在鏈結串列中，每個項目都包含對其後繼項目的引用。 我們可以從串列的開始處，即「頭部」，開始迭代遍歷所有項目，直到達到末尾（即「尾部」）。 相較於陣列，在低階程式語言中，項目並不相鄰於實際的記憶體位置，且沒有索引可供我們隨機訪問陣列中的項目。 我們無法在不從開始的情況下引用列表中的中間項目，因為我們不知道如何引用它。 JavaScript本身並沒有鏈結串列的實作，因此我們現在將創建一個。 首先，我們創建一個會成為鏈結串列中每個項目的容器的Item類別： class Item { next = null value = null constructor(value) { this.value = value } } 我們有一個指向鏈結串列中下一個項目的指標，以及該項目的值。 然後，我們定義一個LinkedList類別，該類別將擁有兩個私有值：head和tail。 我們定義了一個append()方法，用於將項目添加到串列中。如果它是第一個添加的項目，該項目同時是串列的頭部和尾部。否則，我們創建該項目並將其分配給尾部項目的next屬性： class LinkedList { #head = null #tail = null append = (value) => { const item = new Item(value) if (!this.#head) { this.#head = item this.#tail = item return } this.#tail.next = item this.#tail = item } size = () => { let count = 1 let item = this....