Bagaimana untuk melaksanakan pokok binari dalam php (contoh kod)

Pokok binari ialah struktur data asas dalam sains komputer dan merupakan struktur pokok yang paling biasa, seperti digunakan dalam sains komputer untuk mencari dan mengisih, dan digunakan dalam banyak bidang lain dalam sains komputer. PHP ialah bahasa skrip bahagian pelayan yang digunakan secara meluas yang menyokong pembangunan web dinamik. Dalam artikel ini, kami akan memperkenalkan cara untuk melaksanakan pokok binari menggunakan PHP.

Apakah pokok binari?

Pokok binari terdiri daripada beberapa nod, setiap nod mempunyai paling banyak dua nod anak. Ia mempunyai tiga atribut:

• Nilai nod
• Penunjuk subpokok kiri
• Penunjuk subpokok kanan

Pokok binari dibahagikan kepada Kelas berikut:

• Pokok binari penuh: Kecuali nod daun, nod lain mempunyai dua nod anak
• Pokok binari lengkap: Jika kedalaman pokok binari ialah d, kecuali untuk lapisan dth, semua lapisan lain adalah Penuh, dan pada tahap dth, semua nod daun berada dalam kedudukan berterusan di sebelah kiri
• Pokok carian binari: semua nod dalam subpokok kiri mempunyai nilai kurang daripada nod akar , dan semua nod dalam subpokok kanan mempunyai nilai yang lebih besar daripada Nilai nod akar

Melaksanakan Pokok Binari

Kita boleh menggunakan kelas untuk mentakrifkan struktur pokok binari. Setiap nod ialah objek dan mengandungi atribut berikut:

• nilai: nilai nod
• kiri: penunjuk subpokok kiri
• kanan: penunjuk subpokok kanan

Buat kelas untuk mewakili nod.

class Node {
    public $value;
    public $left;
    public $right;
    function __construct($value){
        $this -> value = $value;
        $this -> left = null;
        $this -> right = null;
    }
}

Seterusnya, kita perlu mencipta kelas untuk mewakili pokok binari.

class BinarySearchTree {
    public $root;
    function __construct() {
        $this -> root = null;
    }
}

Seterusnya, kami akan mentakrifkan kaedah pokok binari berikut:

• masukkan(nilai): masukkan nilai ke dalam pokok binari
• carian(nilai ): carian Nilai dalam pepohon binari
• padam(nilai): Padam nilai daripada pepohon binari

Sisipkan nod

Kaedah sisipan nod akan memasukkan nod baharu ke kedudukan yang betul. Jika pokok itu kosong, nod baharu ialah nod akar. Jika tidak, kita mula membandingkan nilai nod semasa daripada nod akar.

• Jika nilai nod baharu kurang daripada nilai nod semasa, maka kami masukkan nod baharu ke dalam subpokok kiri.
• Jika nilai nod baharu lebih besar daripada nilai nod semasa, maka kami masukkan nod baharu ke dalam subpokok kanan.
• Jika nilai nod baharu adalah sama dengan nilai nod semasa, nod sudah wujud dan tidak perlu dimasukkan.

Ini ialah kod untuk kaedah sisipan:

function insert($value) {
    $newNode = new Node($value);
    if ($this -> root == null) {
        $this -> root = $newNode;
    } else {
        $current = $this -> root;
        while (true) {
            if ($value < $current -> value) {
                if ($current -> left == null) {
                    $current -> left = $newNode;
                    return;
                } else {
                    $current = $current -> left;
                }
            } else if ($value > $current -> value) {
                if ($current -> right == null) {
                    $current -> right = $newNode;
                    return;
                } else {
                    $current = $current -> right;
                }
            } else {
                return;
            }
        }
    }
}

Cari Nod

Kaedah Cari Nod ialah kaedah rekursif yang mudah. Bandingkan nilai nod bermula dari nod akar. Jika nilainya sama, kembalikan nod semasa. Jika tidak, jika nilai nod kurang daripada nilai yang anda cari, teruskan mencari subpokok kiri. Jika nilai lebih besar daripada nilai yang anda cari, teruskan mencari subpokok yang betul.

Ini ialah kod untuk kaedah cari:

function search($value) {
    $current = $this -> root;
    while ($current != null) {
        if ($value == $current -> value) {
            return $current;
        } else if ($value < $current -> value) {
            $current = $current -> left;
        } else {
            $current = $current -> right;
        }
    }
    return null;
}

Padam Nod

Kaedah padam nod ialah salah satu kaedah paling kompleks dalam keseluruhan pelaksanaan. Cara nod dipadamkan bergantung pada bilangan anak nod itu. Terdapat situasi berikut:

• nod ialah nod daun dan tidak mempunyai nod anak. Padamkan nod secara langsung. Nod
• hanya mempunyai satu nod anak. Gantikan nod anak dengan nod ini. Nod
• mempunyai dua nod anak. Cari nilai minimum dalam subpokok kanan nod, gantikan nilai minimum dengan nod itu dan keluarkan nilai minimum daripada subpohon kanan.

Ini ialah kod untuk kaedah pemadaman:

function delete($value) {
    $current = $this -> root;
    $parent = null;
    while ($current != null) {
        if ($value == $current -> value) {
            if ($current -> left == null && $current -> right == null) {
                if ($parent == null) {
                    $this -> root = null;
                } else {
                    if ($parent -> left == $current) {
                        $parent -> left = null;
                    } else {
                        $parent -> right = null;
                    }
                }
            } else if ($current -> left == null) {
                if ($parent == null) {
                    $this -> root = $current -> right;
                } else {
                    if ($parent -> left == $current) {
                        $parent -> left = $current -> right;
                    } else {
                        $parent -> right = $current -> right;
                    }
                }
            } else if ($current -> right == null) {
                if ($parent == null) {
                    $this -> root = $current -> left;
                } else {
                    if ($parent -> left == $current) {
                        $parent -> left = $current -> left;
                    } else {
                        $parent -> right = $current -> left;
                    }
                }
            } else {
                $replacementNode = $current -> right;
                while ($replacementNode -> left != null) {
                    $replacementNode = $replacementNode -> left;
                }
                $removeValue = $replacementNode -> value;
                $this -> delete($replacementNode -> value);
                $current -> value = $removeValue;
            }
            return;
        } else if ($value < $current -> value) {
            $parent = $current;
            $current = $current -> left;
        } else {
            $parent = $current;
            $current = $current -> right;
        }
    }
}

Kesimpulan

Sekarang, kita telah belajar bagaimana untuk melaksanakan pokok binari dalam php. Pokok binari ialah struktur data asas dalam sains komputer, dan banyak algoritma dan aplikasi melibatkannya. Kami telah mempelajari cara memasukkan nod, mencari nod dan memadam nod. Kami juga boleh melanjutkan kelas ini untuk melaksanakan kaedah praktikal yang lain.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan pokok binari dalam php (contoh kod). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!