Pokok Carian Binari dari Gores di Jawa

Pengenalan
Pokok Carian Binari (BST) ialah sejenis pokok binari di mana setiap nod mempunyai paling banyak dua anak, dirujuk sebagai anak kiri dan anak kanan. Untuk setiap nod, subpohon kiri hanya mengandungi nod dengan nilai kurang daripada nilai nod, dan subpohon kanan mengandungi hanya nod dengan nilai lebih besar daripada nilai nod. BST digunakan untuk operasi carian, sisipan dan pemadaman yang cekap.

Mengapa Gunakan Pokok Carian Binari?
BST menawarkan beberapa kelebihan:

Pencarian Cekap: Purata kerumitan masa ialah O(log n) untuk carian, sisipan dan pemadaman.
Set Item Dinamik: Menyokong operasi dinamik, tidak seperti tatasusunan statik.
Elemen Tersusun: Traversal tertib BST menghasilkan elemen dalam susunan tersusun.
Panduan Langkah demi Langkah untuk Membina BST
Langkah 1: Takrifkan Struktur Nod
Langkah pertama adalah untuk menentukan struktur nod dalam pokok. Setiap nod akan mempunyai tiga atribut: nilai, rujukan kepada anak kiri dan rujukan kepada anak kanan.

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

Langkah 2: Cipta Kelas BST dengan Pembina
Seterusnya, kami mencipta kelas BST yang mengandungi rujukan kepada akar pokok dan kaedah untuk memasukkan elemen.

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }
}

Langkah 3: Laksanakan Kaedah Sisipan
Untuk memasukkan elemen ke dalam BST, kita perlu mencari kedudukan yang betul untuk nod baharu. Kaedah sisipan biasanya dilaksanakan sebagai fungsi rekursif.

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;
}

Visualisasi
Untuk lebih memahami cara sisipan berfungsi, mari kita pertimbangkan satu contoh. Katakan kita ingin memasukkan urutan nombor berikut ke dalam BST: 50, 30, 70, 20, 40, 60, 80.

50

  50
 /
30

  50
 /  \
30  70

50
 /  \
30  70
/

Sisipkan 40:

  50
 /  \
30  70
/ \

Sisipkan 60

  50
 /  \
30  70
/ \  /

Sisipkan 80:

  50
 /  \
30  70
/ \  / \

Kod Lengkap
Berikut ialah kod lengkap untuk mencipta BST dan memasukkan elemen:

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;
    }
}

Atas ialah kandungan terperinci Pokok Carian Binari dari Gores di Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!