Panduan Lengkap Melintasi Pokok Binari: Kaedah, Contoh, dan Aplikasi

Informatec Digital » Algoritma » Panduan Lengkap Melintasi Pokok Binari: Kaedah, Contoh, dan Aplikasi

Pokok binari menduduki tempat asas dalam dunia sains komputer. Memahami cara merentasinya bukan sahaja perlu bagi pengaturcara dalam pelbagai bahasa, tetapi juga penting bagi mereka yang ingin mengoptimumkan carian, menyimpan data atau menyelesaikan masalah organisasi yang kompleks. Walaupun penampilannya mudah, terdapat beberapa cara untuk merentasi pokok binari, setiap satunya dengan kelebihan dan keistimewaannya sendiri. Jika anda pernah tertanya-tanya bagaimana untuk mendekati struktur data ini, anda telah datang ke tempat yang betul.

Artikel ini menyediakan penjelasan langkah demi langkah yang komprehensif, lengkap dengan contoh, tentang kaedah paling biasa untuk merentasi pokok binari. Kami bukan sahaja akan merangkumi konsep asas dan variasinya, tetapi juga pelaksanaannya dalam bahasa yang berbeza dan cara memilih merentasi yang paling sesuai untuk setiap situasi. Tambahan pula, kami telah memasukkan petikan kod yang jelas dan penyesuaian praktikal untuk membantu anda menyelesaikan sebarang soalan yang mungkin anda ada.

Apakah pokok binari dan mengapa ia digunakan?

Pokok ialah struktur data tak linear yang terdiri daripada nod yang dihubungkan oleh cabang . Dalam keluarga ini, pokok binari dicirikan oleh setiap nod yang mempunyai paling banyak dua subpokok atau anak : satu di kiri dan satu di kanan. Nod yang paling penting ialah akar , dari mana seluruh pokok berkembang. Bergantung pada susunan nodnya, ia boleh menjadi pokok yang seimbang sempurna atau yang lebih tidak sekata, bergantung pada data yang dimasukkan.

Mengapakah pokok binari digunakan? Ia amat berguna apabila saiz struktur tidak diketahui terlebih dahulu, atau apabila akses yang teratur dan cekap kepada elemen diperlukan. Ia digunakan secara meluas dalam enjin carian, pangkalan data, algoritma pemampatan dan sistem fail, antara lain.

Elemen utama pokok binari

• Node: Ia adalah unit asas, di mana data dan rujukan kepada kanak-kanak kiri dan kanan disimpan.
• Root: Nod utama pokok, tanpa ibu bapa.
• Daun: Nod tanpa kanak-kanak, iaitu terminal.
• Nod garpu: Nod dengan sekurang-kurangnya seorang anak.
• Grado: Bilangan cawangan yang keluar daripada nod (dalam binari, maksimum dua).
• Nivel: Jarak antara nod dan punca; punca berada pada tahap sifar.
• Ketinggian: Bilangan maksimum aras dalam pokok.

Setiap nod pokok binari boleh dianggap sebagai punca subpokok , yang memudahkan pembangunan algoritma rekursif secara semula jadi.

Kaedah traversal dalam pokok binari: Preorder, Inorder dan Postorder

Merentasi pokok binari bermaksud melawat semua nodnya dalam susunan tertentu. Tiga cara klasik untuk merentasi pokok binari ialah: prapesanan, dalampesanan dan pascapesanan . Setiap satu memenuhi keperluan yang berbeza:

• Prapesan (Akar, Kiri, Kanan): Akar dilawati dahulu, kemudian subpokok kiri, dan kemudian subpokok kanan.
• Tertib (Kiri, Akar, Kanan): Subpokok kiri dilalui dahulu, kemudian akar, dan akhirnya subpokok kanan. Ini ialah kaedah pilihan untuk memaparkan data dalam tertib menaik jika pepohon itu ialah pepohon carian.
• Pesanan Pos (Kiri, Kanan, Akar): Kedua-dua pokok kecil dilawati dahulu, dan akar dilawati terakhir. Ini berguna dalam aplikasi seperti pemadaman nod.

Lihat laluan sebagai cara yang berbeza untuk membaca pokok, dengan setiap varian mengutamakan bahagian tertentu dalam proses penerokaan.

Bagaimana lawatan dilaksanakan dalam amalan

Pelaksanaan traversal biasanya dilakukan menggunakan algoritma rekursif , kerana pokok itu sendiri sangat sesuai dengan paradigma membahagikan masalah kepada bahagian yang lebih kecil ( subpokok ).

Contoh konseptual fungsi traversal

• Pra-pesanan: Lawati akar, lalui subpokok kiri, dan kemudian subpokok kanan.
• Tidak teratur: melintasi subpokok kiri, melawati akar, dan akhirnya subpokok kanan.
• Postorder: melintasi subpokok kiri, kemudian subpokok kanan, dan melawat akar pada penghujungnya.

Dalam notasi singkatan mereka dinyatakan sebagai:

• Prapesan: R, L, R (Akar, Kiri, Kanan)
• Tertib: I, R, D (Kiri, Akar, Kanan)
• Pesanan pos: L, R, R (Kiri, Kanan, Akar)

Pelaksanaan dalam bahasa pengaturcaraan popular

Untuk lebih memahami konsep-konsep ini, tiada yang dapat menandingi melihat contoh kod. Berikut ialah anggaran bagaimana anda boleh menstruktur kelas dan kaedah untuk merentasi pokok binari menggunakan C# , tetapi pendekatan ini boleh diperluas kepada bahasa lain seperti Python atau Java.

Takrif asas Nod dan Pokok dalam C#

public class NodoArbol {
    public NodoArbol nodoIzquierdo;
    public NodoArbol nodoDerecho;
    public int datos;

    public NodoArbol(int datosNodo) {
        datos = datosNodo;
        nodoIzquierdo = nodoDerecho = null;
    }

    public void insertar(int valorInsertar) {
        if (valorInsertar < datos) { if (nodoIzquierdo == null) nodoIzquierdo = new NodoArbol(valorInsertar); else nodoIzquierdo.insertar(valorInsertar); } else if (valorInsertar > datos) {
            if (nodoDerecho == null)
                nodoDerecho = new NodoArbol(valorInsertar);
            else
                nodoDerecho.insertar(valorInsertar);
        }
    }
}

public class Arbol {
    public NodoArbol raiz;
    public Arbol() { raiz = null; }

    public void insertarNodo(int valorInsertar) {
        if (raiz == null)
            raiz = new NodoArbol(valorInsertar);
        else
            raiz.insertar(valorInsertar);
    }

    public void recorridoPreorden() { ayudantePreorden(raiz); }
    private void ayudantePreorden(NodoArbol nodo) {
        if (nodo == null) return;
        Console.WriteLine(nodo.datos + " ");
        ayudantePreorden(nodo.nodoIzquierdo);
        ayudantePreorden(nodo.nodoDerecho);
    }

    public void recorridoInorden() { ayudanteInorden(raiz); }
    private void ayudanteInorden(NodoArbol nodo) {
        if (nodo == null) return;
        ayudanteInorden(nodo.nodoIzquierdo);
        Console.WriteLine(nodo.datos + " ");
        ayudanteInorden(nodo.nodoDerecho);
    }

    public void recorridoPostorden() { ayudantePostorden(raiz); }
    private void ayudantePostorden(NodoArbol nodo) {
        if (nodo == null) return;
        ayudantePostorden(nodo.nodoIzquierdo);
        ayudantePostorden(nodo.nodoDerecho);
        Console.WriteLine(nodo.datos + " ");
    }
}

Struktur ini boleh diekstrapolasi ke Java , di mana rekursi juga membolehkan merentasi pokok dengan fungsi bersarang, memudahkan pemahaman proses tersebut.

Menggunakan rekursi adalah cara paling semula jadi untuk merentasi pokok binari , kerana setiap panggilan memberi tumpuan kepada pemprosesan satu nod dan kemudian mewakilkan kerja yang lain kepada anak masing-masing.

Perbandingan laluan dan aplikasi praktikal

Memilih satu atau kaedah laluan lain bergantung pada tugas yang perlu dilakukan:

• Prapesan: Sangat berguna untuk menyalin pokok atau untuk bersiri, kerana nod dilawati dalam susunan yang sama di mana ia akan dicipta semula.
• Tertib: Penting dalam pepohon carian binari apabila anda ingin mendapatkan senarai tersusun bagi nilai yang disimpan.
• Pesanan pos: Sesuai untuk mengalih keluar semua nod daripada pokok, kerana ia mula-mula mengeluarkan anak-anak sebelum meneruskan kepada ibu bapa.

Apabila melaksanakan fungsi ini, penting untuk diingat bahawa rekursi mesti mengendalikan kes asas (nod nol) untuk mengelakkan gelung atau ralat yang tidak terhingga. Untuk pokok yang sangat besar, pendekatan berulang mungkin dinasihatkan untuk mengelakkan limpahan tindanan.

Dalam pokok binari, setiap nod boleh menjadi punca bagi subpokok. Konsep subpokok kiri dan kanan adalah penting, kerana setiap traversal sangat bergantung pada bagaimana subpokok ini diterokai. Tambahan pula, terdapat pokok binari khas seperti pokok binari carian (di mana semua elemen dalam subpokok kiri adalah kurang daripada punca, dan elemen dalam subpokok kanan adalah lebih besar) dan pokok seimbang (di mana ketinggian subpokok tidak berbeza lebih daripada satu).

Apa yang berlaku jika pokok itu kosong? Kebanyakan pelaksanaan mempertimbangkan kes di mana akarnya adalah null, dan dalam kes sedemikian, traversal tidak memproses sebarang nod.

Petua untuk melaksanakan dan menganalisis traversal pokok binari

• Mentakrifkan fungsi traversal dengan jelas, membezakan pemprosesan akar dan pokok kecil.
• Uji dengan pokok kecil dan bekas tepi (cth. satu nod atau pokok kosong) sebelum bersisik ke pokok besar.
• Gunakan ujian automatik (seperti QuickCheck dalam Haskell) untuk menyemak bahawa traversal mengembalikan bilangan nod yang betul.
• Fikirkan tentang kecekapan: Untuk pokok besar, pertimbangkan kedalaman rekursi dan kemungkinan menggunakan tindanan eksplisit untuk mengelakkan limpahan.

Contoh langkah demi langkah: mencipta dan memasukkan ke dalam pokok binari

Di bawah ialah gambar rajah menggunakan C#:

// Crear un árbol vacío
Arbol arbol = new Arbol();

// Insertar diez valores
for (int i = 0; i <= 10; i++) {
    int valor = int.Parse(Console.ReadLine());
    arbol.insertarNodo(valor);
}

// Mostrar los recorridos
Console.WriteLine("Recorrido Preorden:");
arbol.recorridoPreorden();
Console.WriteLine("Recorrido Inorden:");
arbol.recorridoInorden();
Console.WriteLine("Recorrido Postorden:");
arbol.recorridoPostorden();

Dengan pendekatan ini, adalah mungkin untuk menggambarkan dengan jelas dan teratur bagaimana pokok itu dibina dan dilalui menggunakan kaedah yang berbeza.

Lawatan dalam bahasa lain dan alternatif

Selain C# dan Python, bahasa seperti JavaScript mempunyai fungsi khusus dan berkuasa untuk bekerja dengan pokok:

• Di Java, kaedah akan sangat serupa dengan yang dilihat dalam C#, menggantikan sintaks kelas dan kaedah.
• Dalam Haskell, traversals ditakrifkan secara fungsional dan membolehkan penciptaan traversal kompleks dengan kod yang sangat sedikit. Adalah lazim untuk menyemak, menggunakan alatan seperti QuickCheck, bahawa saiz senarai yang dikembalikan oleh traversals sepadan dengan bilangan nod tambah daun.

Menyesuaikan logik traversal kepada setiap bahasa adalah satu perkara untuk menterjemahkan idea utama. Rekursi, kes asas (pokok kosong), dan pemprosesan tersusun adalah universal dalam kebanyakan bahasa.

Kesilapan biasa dan cara mengelakkannya

• Tidak menyemak sama ada nod itu batal sebelum cuba mengakses anak-anaknya.
• Terlupa untuk mengembalikan kawalan apabila dipanggil secara rekursif, yang boleh mengakibatkan nod melangkau atau kehilangan data.
• Dalam pokok yang tidak seimbang atau sangat dalam, melebihi had rekursi sesetengah bahasa.

Pastikan kod anda bersih, didokumentasikan dengan baik dan uji setiap fungsi rekursif dengan contoh mudah untuk memastikan ia berfungsi dengan betul.

Aplikasi praktikal dan visualisasi

Jejak pokok binari digunakan secara meluas dalam pencarian maklumat, penghuraian, organisasi data hierarki dan pemprosesan ekspresi matematik . Tambahan pula, terdapat sumber visual yang membantu dalam memahami bagaimana jejak ini berlaku dalam masa nyata, menjadikannya sesuai untuk pelajar dan pembangun yang mempelajari struktur tersebut.

Akhir sekali, perlu diingat bahawa terdapat animasi dan simulator interaktif tersedia dalam talian, sesuai untuk mempraktikkan teori dan melihat cara kaedah traversal yang berbeza bertindak dengan pokok yang berbeza saiz dan bentuk.

Menguasai traversal pokok binari adalah kemahiran asas untuk banyak bidang sains komputer dan pengaturcaraan. Memahami cara kaedah prapesanan, susun atur dan pascapesanan berfungsi, serta pelaksanaannya dalam bahasa yang berbeza, akan membolehkan anda menangani cabaran penyimpanan data dan organisasi yang kompleks. Memilih laluan yang betul, mengelakkan kesilapan biasa dan berlatih dengan contoh praktikal adalah asas untuk memanfaatkan sepenuhnya struktur data serba boleh ini.