JavaScript 中的二元搜尋樹

在 JavaScript 中實作二元搜尋樹

在這篇文章中，我們將探索如何在 JavaScript 中實作基本的二元搜尋樹 (BST)。我們將介紹插入節點和執行不同的樹遍歷方法 - 中序、前序和後序。

節點類
首先，我們定義一個 Node 類別來表示樹中的每個節點：

雷雷

每個 Node 物件都有三個屬性：

• value：節點中儲存的資料。
• left：指向左子節點的指標。
• right：指向右子節點的指標。

BinarySearchTree 類別

接下來，我們將定義一個 BinarySearchTree 類，它將管理節點並提供與樹互動的方法：

雷雷

關鍵方法：

• isEmpty()：檢查樹是否為空。
• insertNode(root, newNode)：在樹中插入新節點，保持二元搜尋樹屬性。
• search(root, value)：遞歸搜尋樹中的值。
• insert(value)：一種向樹中插入新值的便捷方法。

樹遍歷方法

一旦我們有一棵樹，我們經常需要遍歷它。以下是三種常見的遍歷方式：

中序遍歷

中序遍歷依照下列順序存取節點：Left、Root、Right。

雷雷

此遍歷以非降序列印二元搜尋樹的節點。

預購穿越

前序遍歷依照下列順序存取節點：Root、Left、Right。

雷雷

這種遍歷對於複製樹結構很有用。

後序遍歷

後序遍歷依照下列順序存取節點：Left、Right、Root。

雷雷

這種遍歷通常用於刪除或釋放節點。

用法範例

讓我們看看這些方法如何協同工作：

雷雷

結論

透過此實現，您現在可以在 JavaScript 中建立二元搜尋樹並與之互動。理解樹結構和遍歷方法對於許多演算法問題至關重要，尤其是在搜尋演算法、解析表達式和管理分層資料等領域。

以上是JavaScript 中的二元搜尋樹的詳細內容。更多資訊請關注PHP中文網其他相關文章！