簡介
二元搜尋樹 (BST) 是一種二元樹，其中每個節點最多有兩個子節點，稱為左子節點和右子節點。對於每個節點，左子樹僅包含值小於該節點值的節點，右子樹僅包含值大於該節點值的節點。 BST 用於高效率的搜尋、插入和刪除操作。
為什麼要使用二元搜尋樹？
BST 有幾個優點：
高效率搜尋：搜尋、插入、刪除的平均時間複雜度為 O(log n)。
動態項目集：與靜態陣列不同，支援動態操作。
有序元素：BST 的中序遍歷會產生按排序順序排列的元素。
建構 BST 的分步指南
步驟一：定義節點結構
第一步是定義樹中節點的結構。每個節點將有三個屬性：一個值、對左子節點的引用以及對右子節點的引用。
public class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
第 2 步：使用建構子建立 BST 類別
接下來，我們建立 BST 類，其中包含對樹根的引用以及插入元素的方法。
public class BinarySearchTree {
TreeNode root;
public BinarySearchTree() {
this.root = null;
}
}
第3步：實作插入方法
要將元素插入 BST，我們需要找到新節點的正確位置。插入方法通常作為遞歸函數實作。
public void insert(int value) {
root = insertRec(root, value);
}
private TreeNode insertRec(TreeNode root, int value) {
// Base case: if the tree is empty, return a new node
if (root == null) {
root = new TreeNode(value);
return root;
}
// Otherwise, recur down the tree
if (value < root.value) {
root.left = insertRec(root.left, value);
} else if (value > root.value) {
root.right = insertRec(root.right, value);
}
// Return the (unchanged) node pointer
return root;
}
可視化
為了更好地理解插入是如何運作的，讓我們考慮一個例子。假設我們要在 BST 中插入以下數字序列：50, 30, 70, 20, 40, 60, 80。
50
50 / 30
50 / \ 30 70
50 / \ 30 70 /
插入 40：
50 / \ 30 70 / \
插入 60
50 / \ 30 70 / \ /
插入 80：
50 / \ 30 70 / \ / \
完整程式碼
以下是建立 BST 和插入元素的完整程式碼：
public class BinarySearchTree {
TreeNode root;
public BinarySearchTree() {
this.root = null;
}
public void insert(int value) {
root = insertRec(root, value);
}
private TreeNode insertRec(TreeNode root, int value) {
if (root == null) {
root = new TreeNode(value);
return root;
}
if (value < root.value) {
root.left = insertRec(root.left, value);
} else if (value > root.value) {
root.right = insertRec(root.right, value);
}
return root;
}
// Additional methods for traversal, search, and delete can be added here
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
int[] values = {50, 30, 70, 20, 40, 60, 80};
for (int value : values) {
bst.insert(value);
}
// Add code to print or traverse the tree
}
}
class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
以上是Java 中從頭開始的二元搜尋樹的詳細內容。更多資訊請關注PHP中文網其他相關文章！
