Java 中從頭開始的二元搜尋樹

簡介
二元搜尋樹 (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中文網其他相關文章！