Pokok Carian Binari dalam Javascript

Melaksanakan Pokok Carian Binari dalam JavaScript

Dalam siaran ini, kami akan meneroka cara melaksanakan Pokok Carian Binari (BST) asas dalam JavaScript. Kami akan meliputi memasukkan nod dan melaksanakan kaedah rentas pokok yang berbeza—tertib, prapesanan dan pasca pesanan.

Kelas Nod
Mula-mula, mari kita tentukan kelas Nod untuk mewakili setiap nod dalam pepohon:

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

Setiap objek Nod mempunyai tiga sifat:

• nilai: Data yang disimpan dalam nod.
• kiri: Penunjuk ke nod anak kiri.
• kanan: Penunjuk ke nod anak kanan.

Kelas BinarySearchTree

Seterusnya, kami akan menentukan kelas BinarySearchTree yang akan mengurus nod dan menyediakan kaedah untuk berinteraksi dengan pepohon:

class BinarySearchTree {
    constructor() {
        this.root = null;
    }

    isEmpty() {
        return this.root === null;
    }

    insertNode(root, newNode) {
        if(newNode.value < root.value) {
            if(root.left === null) {
                root.left = newNode;
            } else {
                this.insertNode(root.left, newNode);
            }
        } else {
            if(root.right === null) {
                root.right = newNode;
            } else {
                this.insertNode(root.right, newNode);
            }
        }
    }

    search(root, value) {
        if(!root) {
            return false;
        }
        if(root.value === value) {
            return true;
        } else if(root.value > value) {
            return this.search(root.left, value);
        } else {
            return this.search(root.right, value);
        }
    }

    insert(value) {
        const newNode = new Node(value);
        if(this.isEmpty()) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }
}

Kaedah Utama:

• isEmpty(): Memeriksa sama ada pokok itu kosong.
• insertNode(root, newNode): Memasukkan nod baharu ke dalam pepohon, mengekalkan sifat pepohon carian binari.
• carian(akar, nilai): Secara rekursif mencari nilai dalam pepohon.
• masukkan(nilai): Kaedah mudah untuk memasukkan nilai baharu ke dalam pepohon.

Kaedah Traversal Pokok

Apabila kita mempunyai pokok, kita sering perlu melintasinya. Berikut ialah tiga kaedah traversal biasa:

Perjalanan Tertib

Perjalanan tertib melawati nod dalam susunan berikut: Kiri, Akar, Kanan.

inOrder(root) {
    if(root) {
        this.inOrder(root.left);
        console.log(root.value);
        this.inOrder(root.right);
    }
}

Traversal ini mencetak nod dalam susunan tidak menurun untuk pepohon carian binari.

Prapesan Traversal

Perjalanan prapesanan melawati nod dalam susunan berikut: Akar, Kiri, Kanan.

preOrder(root) {
    if(root) {
        console.log(root.value);
        this.preOrder(root.left);
        this.preOrder(root.right);
    }
}

Traversal ini berguna untuk menyalin struktur pokok.

Perjalanan pasca pesanan

Perjalanan pasca pesanan melawati nod dalam susunan berikut: Kiri, Kanan, Akar.

postOrder(root) {
    if(root) {
        this.postOrder(root.left);
        this.postOrder(root.right);
        console.log(root.value);
    }
}

Traversal ini selalunya digunakan untuk memadam atau membebaskan nod.

Contoh Penggunaan

Mari lihat cara kaedah ini berfungsi bersama:

const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(20);
bst.insert(3);
bst.insert(7);

console.log('In-order Traversal:');
bst.inOrder(bst.root);

console.log('Pre-order Traversal:');
bst.preOrder(bst.root);

console.log('Post-order Traversal:');
bst.postOrder(bst.root);

Kesimpulan

Dengan pelaksanaan ini, anda kini boleh membuat dan berinteraksi dengan Pokok Carian Binari dalam JavaScript. Memahami struktur pokok dan kaedah traversal adalah penting untuk banyak masalah algoritma, terutamanya dalam bidang seperti algoritma carian, ungkapan penghuraian dan mengurus data hierarki.

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