Contoh pokok carian carian binari

Pokok carian binari (BST) adalah pokok binari di mana subtree kiri hanya mengandungi nod dengan nilai kurang daripada nilai nod, subtree yang betul mengandungi hanya nod dengan nilai lebih besar daripada nilai nod, dan kedua -dua subtrees juga mesti menjadi BST; 1. Pelaksanaan C termasuk struktur treenode dengan nilai, kiri, dan penunjuk kanan; 2. Kelas BST menyediakan operasi sisipan, carian, dan inorder menggunakan kaedah penolong rekursif; 3. Sisipan mengekalkan harta BST dengan membandingkan nilai dan mengelakkan pendua; 4. Carian beroperasi di O (log N) masa purata dengan menavigasi kiri atau kanan berdasarkan perbandingan; 5. Traversal In-Order mencetak nilai dalam urutan yang disusun dengan melawat kiri, akar, kemudian kanan; 6. Pertimbangan utama untuk pengeluaran termasuk menambah pemusnah untuk pembersihan memori, mengimbangi pokok menggunakan AVL atau logik hitam-hitam, dan melaksanakan kaedah berulang untuk mencegah limpahan timbunan, menjadikan contoh ini pemahaman asas BSTS dalam c.

Berikut adalah contoh praktikal C Search Tree (BST) dengan operasi asas: masukkan, cari, dan traversal dalam pesanan.

✅ Apakah pokok carian binari?

BST adalah pokok binari di mana:

• Subtree kiri nod mengandungi hanya nod dengan nilai kurang daripada nilai nod.
• Subtree yang betul mengandungi hanya nod dengan nilai yang lebih besar daripada nilai nod.
• Kedua -dua subtrees kiri dan kanan juga mesti menjadi pokok carian binari.

? C Contoh pelaksanaan

 #include <iostream>
menggunakan ruang nama STD;

// Tentukan struktur nod pokok
struct treenode {
    nilai int;
    Treenode* kiri;
    Treenode* betul;

    // Pembina
    Treenode (int val): nilai (val), kiri (nullptr), kanan (nullptr) {}
};

// kelas pokok carian binari
kelas BST {
awam:
    Treenode* root;

    // Pembina
    Bst (): root (nullptr) {}

    // fungsi memasukkan awam
    void sisipkan (nilai int) {
        root = InserTrecursive (root, nilai);
    }

    // fungsi carian awam
    carian bool (nilai int) {
        kembali SearchRecursive (root, nilai);
    }

    // traversal in-order (mencetak nilai dalam urutan yang disusun)
    void inorder () {
        inorderRecursive (root);
        cout << endl;
    }

Swasta:
    // penolong: masukkan nod secara rekursif
    Treenode* insertrecursive (treenode* node, int value) {
        // jika pokok kosong, buat nod baru
        jika (node == nullptr) {
            mengembalikan treenode baru (nilai);
        }

        // Jika tidak, berulang pokok
        jika (nilai <node-> nilai) {
            node-> kiri = instrecursive (node-> kiri, nilai);
        } else if (value> node-> value) {
            node-> right = instrecursive (node-> right, value);
        }
        // Abaikan pendua (nilai == nod-> nilai)

        Node kembali;
    }

    // pembantu: cari secara rekursif
    bool searchRecursive (treenode* node, int value) {
        jika (node == nullptr) {
            kembali palsu; // tidak dijumpai
        }
        jika (nod-> nilai == nilai) {
            kembali benar; // dijumpai
        }
        jika (nilai <node-> nilai) {
            kembali SearchRecursive (node-> kiri, nilai);
        } else {
            kembali SearchRecursive (Node-> Right, Value);
        }
    }

    // penolong: traversal dalam pesanan (kiri -> root -> kanan)
    void inorderRecursive (treenode* node) {
        jika (nod! = nullptr) {
            inorderRecursive (node-> kiri);
            cout << node-> value << "";
            inorderRecursive (node-> right);
        }
    }
};

// Contoh penggunaan
int main () {
    Pokok BST;

    // Masukkan nilai
    Tree.insert (50);
    Tree.insert (30);
    Tree.insert (70);
    Tree.insert (20);
    Tree.insert (40);
    Tree.insert (60);
    Tree.insert (80);

    // cetak traversal in-order (harus disusun)
    cout << "In-order traversal:";
    pokok.Inorder (); // output: 20 30 40 50 60 70 80

    // Cari nilai
    cout << "Cari 40:" << (Tree.Search (40)? "Ditemui": "tidak dijumpai") << endl;
    cout << "Cari 25:" << (Tree.Search (25)? "Ditemui": "tidak dijumpai") << endl;

    kembali 0;
}

? Output:

 Traversal In-Order: 20 30 40 50 60 70 80
Cari 40: dijumpai
Cari 25: Tidak dijumpai

✅ Mata Utama:

• Sisipan mengekalkan harta BST dengan membandingkan nilai.
• Carian adalah cekap (O (log n) secara purata) dengan pergi ke kiri/kanan.
• Traversal dalam pesanan memberikan output yang disusun-salah satu manfaat utama BST.
• Versi ini mengabaikan nilai pendua . Anda boleh mengubahnya untuk membolehkan pendua (contohnya, dengan menggunakan atau menyimpan kiraan).

⚠️ Nota:

Ini adalah pelaksanaan asas. Untuk kegunaan pengeluaran, pertimbangkan:

• Pembersihan memori (tambah pemusnah untuk memadam nod).
• Mengimbangi (gunakan AVL atau pokok merah hitam untuk mengelakkan pokok miring).
• Versi berulang untuk mengelakkan limpahan timbunan di pokok -pokok dalam.

Pada asasnya, contoh ini memberi anda asas yang kukuh untuk memahami bagaimana BST berfungsi dalam c.

Atas ialah kandungan terperinci Contoh pokok carian carian binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!