Penjelasan terperinci tentang struktur pokok binari di Jawa

Pokok binari ialah struktur data biasa dalam sains komputer dan struktur data yang biasa digunakan dalam pengaturcaraan Java. Artikel ini akan memperkenalkan struktur pokok binari di Jawa secara terperinci.

1. Apakah pokok binari?

Dalam sains komputer, pokok binari ialah struktur pokok dengan setiap nod mempunyai paling banyak dua nod anak. Antaranya, nod anak kiri lebih kecil daripada nod induk, dan nod anak kanan lebih besar daripada nod induk. Dalam pengaturcaraan Java, pokok binari biasanya digunakan untuk mewakili pengisihan, mencari dan meningkatkan kecekapan pertanyaan data.

2. Pelaksanaan pokok binari di Jawa

Di Jawa, pelaksanaan pokok binari biasanya menggunakan kelas nod (Kelas Nod) dan kelas pokok binari (Kelas Pokok Binari). Kelas nod mewakili setiap nod dalam pepohon binari dan boleh mempunyai bait dan atribut untuk menyimpan data. Kelas pepohon binari mewakili keseluruhan struktur data pepohon perduaan dan mempunyai fungsi seperti memasukkan nod, memadamkan nod dan melintasi. Berikut ialah pelaksanaan pokok binari Java yang mudah:

public class Node {
    int key;
    String value;
    Node leftChild, rightChild;

    public Node(int key, String value) {
        this.key = key;
        this.value = value;
    }
}

public class BinaryTree {
    Node root;

    public void insert(int key, String value) {
        Node newNode = new Node(key, value);
        if (root == null) {
            root = newNode;
        } else {
            Node current = root;
            while (true) {
                if (key < current.key) {
                    if (current.leftChild == null) {
                        current.leftChild = newNode;
                        return;
                    }
                    current = current.leftChild;
                } else {
                    if (current.rightChild == null) {
                        current.rightChild = newNode;
                        return;
                    }
                    current = current.rightChild;
                }
            }
        }
    }

    public Node find(int key) {
        Node current = root;
        while (current.key != key) {
            if (key < current.key) {
                current = current.leftChild;
            } else {
                current = current.rightChild;
            }
            if (current == null) {
                return null;
            }
        }
        return current;
    }

    public void inOrderTraversal(Node node) {
        if (node != null) {
            inOrderTraversal(node.leftChild);
            System.out.println(node.key + ": " + node.value);
            inOrderTraversal(node.rightChild);
        }
    }

    public void preOrderTraversal(Node node) {
        if (node != null) {
            System.out.println(node.key + ": " + node.value);
            preOrderTraversal(node.leftChild);
            preOrderTraversal(node.rightChild);
        }
    }

    public void postOrderTraversal(Node node) {
        if (node != null) {
            postOrderTraversal(node.leftChild);
            postOrderTraversal(node.rightChild);
            System.out.println(node.key + ": " + node.value);
        }
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        tree.insert(50, "John");
        tree.insert(25, "Alice");
        tree.insert(75, "Bob");
        tree.insert(15, "Chris");
        tree.insert(33, "Diana");
        tree.insert(60, "Emily");
        tree.insert(90, "Fred");

        Node node = tree.find(33);
        System.out.println("Find key: " + node.key + ", value: " + node.value);

        System.out.println("In-order traversal:");
        tree.inOrderTraversal(tree.root);

        System.out.println("Pre-order traversal:");
        tree.preOrderTraversal(tree.root);

        System.out.println("Post-order traversal:");
        tree.postOrderTraversal(tree.root);
    }
}

Kod pokok binari di atas merangkumi tiga fungsi utama: memasukkan nod, mencari nod dan tiga kaedah traversal yang berbeza. Nod sisipan menggunakan gelung sementara untuk memasukkan data dalam susunan pepohon perduaan menggunakan gelung sementara untuk melintasi pepohon untuk mencari data sasaran dilaksanakan secara rekursif;

3. Kaedah traversal pokok binari

Dalam kod Java di atas, program ini melaksanakan tiga kaedah traversal pokok binari yang berbeza: traversal tertib, traversal prapesan dan traversal pasca pesanan. Bahagian ini akan memperkenalkan ketiga-tiga kaedah traversal ini satu persatu.

1. Traversal tertib

Traversal tertib melintasi nod dalam pokok mengikut tertib dari kecil ke besar. Dalam kod Java, pelaksanaan traversal tertib menggunakan rekursi: untuk setiap nod, mula-mula panggil nod kirinya sendiri, kemudian cetak data nod, dan akhirnya panggil nod kanannya sendiri. Dengan cara ini, semua nod dalam pokok boleh dilalui mengikut urutan dari kecil ke besar.

2. Prepesan traversal

Prapesan traversal merentasi nod dalam pepohon dalam susunan nod induk, nod kiri dan nod kanan. Dalam kod Java, pelaksanaan traversal prapesanan juga menggunakan rekursi: untuk setiap nod, mula-mula cetak data nod, kemudian panggil nod kirinya sendiri, dan akhirnya panggil nod kanannya sendiri. Dengan cara ini, semua nod dalam pokok boleh dilalui dalam susunan nod induk, nod kiri dan nod kanan.

3. Traversal pasca pesanan

Traversal pasca pesanan melintasi nod dalam pepohon dalam susunan nod kiri, nod kanan dan nod induk. Dalam kod Java, pelaksanaan traversal pasca pesanan juga menggunakan rekursi: untuk setiap nod, mula-mula panggil nod kirinya sendiri, kemudian panggil nod kanannya sendiri, dan akhirnya mencetak data nod. Dengan cara ini, semua nod dalam pokok boleh dilalui dalam susunan nod kiri, nod kanan dan nod induk.

4. Algoritma pokok binari yang biasa digunakan

Pokok binari ialah struktur data yang fleksibel dan sangat berguna Dalam pengaturcaraan Java, algoritma pokok binari sering digunakan. Berikut ialah algoritma pokok binari yang biasa digunakan:

1. Cari

Cari ialah salah satu fungsi pokok binari yang paling asas dan juga merupakan fungsi yang kerap digunakan. Dalam kod Java, pelaksanaan carian adalah sangat mudah: untuk setiap nod, dengan membandingkan saiz nilai nod dan nilai sasaran, cari ke bawah lapisan demi lapisan sehingga nilai sasaran ditemui atau keseluruhan pepohon dilalui.

2. Sisipan

Sisipan ialah fungsi menambah nod baharu pada pokok binari, dan nod baharu yang dimasukkan juga akan mengikut susunan penyisihan pokok binari. Dalam kod Java, pelaksanaan sisipan juga agak mudah: bandingkan saiz nod yang akan dimasukkan dengan nod semasa, dan masukkan nod baharu apabila kedudukan yang sesuai ditemui.

3. Padam

Pemadaman ialah fungsi mengalih keluar nod daripada pepohon binari Dalam kod Java, pelaksanaan pemadaman adalah lebih kompleks dan memerlukan lebih banyak pertimbangan. Jika nod yang dipadamkan tidak mempunyai nod anak, hanya padamkannya secara langsung jika terdapat hanya satu nod anak, hanya alihkan nod anak ke kedudukan nod yang dipadamkan itu mempunyai dua nod anak, anda perlu mencari minimum nilai nod anak kanan, menggantikan lokasi nod yang dipadamkan.

5. Ringkasan

Artikel ini memperkenalkan struktur data pokok binari di Jawa secara terperinci, termasuk definisi pokok binari, pelaksanaan nod dan kelas pokok binari, tiga kaedah traversal yang berbeza dan lazimnya menggunakan algoritma pokok binari. Pokok binari ialah struktur data yang digunakan secara meluas, dan Java menyediakan banyak fungsi dan perpustakaan kelas untuk membantu dalam pelaksanaan pokok binari. Apabila pengaturcaraan di Java, mahir dalam penggunaan dan pelaksanaan pepohon binari boleh meningkatkan kecekapan program dan ketepatan pertanyaan data.

Atas ialah kandungan terperinci Penjelasan terperinci tentang struktur pokok binari di Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!