Bagaimana untuk melaksanakan algoritma pepohon carian binari menggunakan java

Cara menggunakan Java untuk melaksanakan algoritma pepohon carian binari

Binary Search Tree (BST) ialah struktur data yang biasa digunakan yang boleh melaksanakan operasi dengan cekap seperti penyisipan, pemadaman dan carian. Artikel ini akan memperkenalkan cara menggunakan Java untuk melaksanakan pepohon carian binari dan memberikan contoh kod yang sepadan.

1. Definisi Pokok Carian Binari

Pepohon carian binari ialah pokok tersusun dengan ciri-ciri berikut:

1. Setiap nod mempunyai nilai kunci yang unik.
2. Nilai kunci subpokok kiri lebih kecil daripada nilai kunci nod dan nilai kunci subpokok kanan lebih besar daripada nilai kunci nod.
3. Subpokok kiri dan subpokok kanan juga merupakan pokok carian binari.

2. Laksanakan kelas nod pepohon carian binari

Pertama, kami mentakrifkan kelas nod pepohon carian binari, termasuk nilai utama dan rujukan kepada nod anak kiri dan kanan. Kodnya adalah seperti berikut:

class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

Dalam kelas nod ini, kami menyimpan rujukan nod anak kiri dan kanan melalui medan data字段保存节点的键值，left和right.

3. Laksanakan operasi sisipan pepohon carian binari

Seterusnya, kami melaksanakan operasi penyisipan pepohon carian binari. Operasi sisipan menentukan kedudukan sisipan nod dengan membandingkan saiz nilai kunci nod Jika nilai kunci lebih kecil daripada nod semasa, ia dimasukkan ke dalam subpokok kiri, jika tidak, ia dimasukkan ke dalam subpokok kanan. Kodnya adalah seperti berikut:

class BinarySearchTree {
    Node root;

    // 插入操作
    public void insert(int key) {
        root = insertRec(root, key);
    }

    private Node insertRec(Node root, int key) {
        // 如果树为空，创建一个新的节点
        if (root == null) {
            root = new Node(key);
            return root;
        }

        // 否则，递归地插入节点到左子树或右子树
        if (key < root.data)
            root.left = insertRec(root.left, key);
        else if (key > root.data)
            root.right = insertRec(root.right, key);

        return root;
    }
}

Dalam operasi sisipan, kita mula-mula menentukan sama ada pokok itu kosong Jika ia kosong, buat nod baharu sebagai nod akar. Jika tidak, masukkan secara rekursif ke dalam subpokok kiri atau subpokok kanan dengan membandingkan hubungan saiz antara nilai kunci dan nod semasa.

4. Laksanakan operasi carian pepohon carian binari

Operasi carian pepohon carian perduaan adalah agak mudah. ​​Ia membandingkan perhubungan saiz antara nilai kunci dan nod langkah demi langkah sehingga padanan ditemui atau kosong nod ditemui. Kodnya adalah seperti berikut:

class BinarySearchTree {
    ...

    // 查找操作
    public boolean contains(int key) {
        return containsRec(root, key);
    }

    private boolean containsRec(Node root, int key) {
        // 树为空或者找到匹配节点
        if (root == null || root.data == key)
            return (root != null);

        // 比较键值与当前节点
        if (key < root.data)
            return containsRec(root.left, key);
        else
            return containsRec(root.right, key);
    }
}

Dalam operasi carian, kami mula-mula menentukan sama ada pokok itu kosong atau sama ada nod semasa sepadan. Mengembalikan benar jika terdapat padanan, jika tidak, mencari subpokok kiri atau kanan secara rekursif dengan membandingkan saiz nilai kunci dengan nod semasa.

5. Kod untuk menguji pokok carian binari

Akhir sekali, kami menulis kod untuk menguji pokok carian binari yang kami laksanakan. Kodnya adalah seperti berikut:

public class Main {
    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();

        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        System.out.println(tree.contains(30));
        System.out.println(tree.contains(90));
    }
}

Hasil yang sedang dijalankan ialah:

true
false

Di sini kita masukkan beberapa nod ke dalam pepohon dengan memanggil operasi sisipan. Kemudian, kami memanggil operasi cari untuk mencari nod dengan nilai kunci masing-masing 30 dan 90. Keputusan yang dikembalikan ialah sama ada operasi pemasukan berjaya.

Melalui langkah di atas, kami berjaya melaksanakan algoritma pepohon carian binari menggunakan Java dan melaksanakan operasi sisipan dan carian. Dalam aplikasi praktikal, pepohon carian binari juga boleh menyokong fungsi seperti operasi pemadaman, prapesanan, rentas pesanan dan pasca pesanan. Pembaca boleh mengembangkan lagi pelaksanaan mengikut keperluan tertentu.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma pepohon carian binari menggunakan java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!