Pokok Carian Binari dari Gores di Jawa-javaTutorial-php.cn

Pokok Carian Binari dari Gores di Jawa

WBOY

Lepaskan： 2024-07-17 22:19:03

asal

882 orang telah melayarinya

Binary Search Tree from Scratch in Java

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

Salin selepas log masuk

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

Salin selepas log masuk

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

Salin selepas log masuk

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.

Salin selepas log masuk

  50
 /
30

Salin selepas log masuk

  50
 /  \
30  70

Salin selepas log masuk

Salin selepas log masuk

Sisipkan 40:

Salin selepas log masuk

Sisipkan 60

  50
 /  \
30  70
/ \  /

Salin selepas log masuk

Sisipkan 80:

  50
 /  \
30  70
/ \  / \

Salin selepas log masuk

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

Salin selepas log masuk

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