Pokok Binari dalam C: Panduan Lengkap Pemula

Informatec Digital » Algoritma » Pokok Perduaan dalam C: Panduan Lengkap untuk Pemula

Selamat datang ke panduan komprehensif tentang pokok binari dalam C. Dalam artikel ini, kami akan meneroka asas pokok binari dan cara melaksanakannya dalam bahasa pengaturcaraan C Jika anda seorang pemula dalam pengaturcaraan atau hanya ingin meningkatkan kemahiran C anda, panduan ini adalah untuk anda.

Pokok binari merupakan struktur data asas dalam sains komputer dan digunakan dalam pelbagai aplikasi. Memahami cara ia berfungsi dan cara melaksanakannya akan membantu anda menyelesaikan masalah yang kompleks dengan lebih cekap dan elegan.

Sepanjang artikel ini, kita akan meneroka asas-asas pokok binari, termasuk strukturnya, penyisipan dan pemadaman nod, traversal dan carian elemen. Kami juga akan menyediakan contoh praktikal dalam bahasa pengaturcaraan C supaya anda dapat melihat bagaimana konsep-konsep ini diaplikasikan dalam praktik.

Jadi mari kita mulakan!

Apakah pokok binari?

Pokok binari ialah struktur data hierarki yang terdiri daripada nod yang saling berkaitan. Setiap nod boleh mempunyai sehingga dua nod anak: satu di sebelah kiri dan satu di sebelah kanan. Struktur dua cawangan inilah yang membezakan pokok binari daripada struktur data lain.

Dalam pokok binari, nod pertama dipanggil nod akar. Nod anak dipanggil nod anak, dan nod tanpa anak dipanggil nod daun. Nod pada tahap yang sama dipanggil nod adik-beradik.

Faedah pokok binari

Pokok binari menawarkan beberapa kelebihan dari segi penyimpanan dan pencarian data yang cekap. Beberapa faedah utama termasuk:

1. Pencarian yang cekapPepohon binari membenarkan elemen dicari pada masa jalan lebih cepat daripada struktur data lain, seperti senarai terpaut. Ini disebabkan oleh struktur hierarki pokok dan keupayaannya untuk membahagikan set data dengan cepat.
2. Sisipan dan penyingkiran fleksibelPokok binari sangat mudah disesuaikan dengan operasi pemadaman dan pemadaman nod. Tidak seperti struktur data statik seperti tatasusunan, pokok binari boleh berkembang dan mengubah strukturnya secara dinamik.
3. Perwakilan hubungan hierarkiPokok binari amat berguna untuk mewakili hubungan hierarki antara unsur. Sebagai contoh, dalam struktur direktori fail, setiap direktori boleh diwakili sebagai nod dalam pepohon, dengan subdirektori dan fail sebagai nod anaknya.

Struktur pokok binari

Sebelum kita menyelami pelaksanaan pokok binari dalam C, adalah penting untuk memahami struktur asasnya. Setiap nod dalam pepohon binari mengandungi nilai dan rujukan kepada nod anak kiri dan kanannya, jika ia mempunyai sebarang.

Jadual berikut menunjukkan struktur nod dalam pokok binari:

nod binari
Valor
Nod kiri
Nod kanan

Setiap nod boleh menyimpan sebarang jenis data, seperti integer, aksara atau struktur yang lebih kompleks. Nod akar ialah titik permulaan pokok, dan daripadanya kita boleh mengakses semua nod lain.

Melaksanakan pokok binari dalam C

Sekarang kita mempunyai pemahaman asas tentang pokok binari, tiba masanya untuk melaksanakannya dalam bahasa pengaturcaraan C. Seterusnya, kita akan melihat cara mengisytiharkan dan menggunakan struktur pokok binari dalam C.

Mengisytiharkan struktur pokok binari

Dalam C, kita boleh mengisytiharkan struktur pokok binari menggunakan struktur dan penunjuk. Berikut ialah pengisytiharan asas struktur:

struct NodoArbol {
    int valor;
    struct NodoArbol* izquierdo;
    struct NodoArbol* derecho;
};

Dalam struktur ini, valor mewakili nilai yang disimpan dalam nod, dan izquierdo y derecho ialah penunjuk ke nod anak kiri dan kanan, masing-masing.

Mencipta nod baharu

Untuk mencipta nod baharu dalam pokok binari, kita perlu memperuntukkan memori untuk nod dan menetapkan nilainya. Berikut ialah fungsi C yang mencipta nod baharu:

struct NodoArbol* crearNodo(int valor) {
    struct NodoArbol* nodo = (struct NodoArbol*)malloc(sizeof(struct NodoArbol));
    nodo->valor = valor;
    nodo->izquierdo = NULL;
    nodo->derecho = NULL;
    return nodo;
}

Fungsi ini malloc Ia digunakan untuk memperuntukkan memori dinamik kepada nod. Kami kemudian menetapkan nilai nod dan mengembalikan nod yang dibuat.

Memasukkan nod

Sisipan nod ialah proses asas dalam pokok binari. Membolehkan anda menambah elemen baharu pada pokok pada kedudukan yang betul berdasarkan nilai nod. Di bawah ialah fungsi C untuk memasukkan nod ke dalam pokok binari:

struct NodoArbol* insertarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return crearNodo(valor);
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = insertarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = insertarNodo(raiz->derecho, valor);
    }

    return raiz;
}

Fungsi ini menerima penunjuk kepada akar pokok dan nilai nod untuk dimasukkan. Jika akar adalah nol, ia bermakna pokok itu kosong dan kami mencipta nod baharu pada akar. Jika tidak, kami membandingkan nilai nod dengan nilai punca dan memutuskan sama ada untuk memasukkan nod ke kiri atau kanan.

Memadam nod

Memadamkan nod dalam pokok binari boleh menjadi lebih kompleks. Ia bergantung pada beberapa kes, seperti sama ada nod yang akan dipadamkan mempunyai anak atau tidak. Di bawah ialah fungsi C untuk memadam nod dalam pokok binari:

struct NodoArbol* eliminarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return raiz;
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = eliminarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = eliminarNodo(raiz->derecho, valor);
    } else {
        if (raiz->izquierdo == NULL) {
            struct NodoArbol* temp = raiz->derecho;
            free(raiz);
            return temp;
        } else if (raiz->derecho == NULL) {
            struct NodoArbol* temp = raiz->izquierdo;
            free(raiz);
            return temp;
        }

        struct NodoArbol* sucesor = encontrarSucesor(raiz->derecho);
        raiz->valor = sucesor->valor;
        raiz->derecho = eliminarNodo(raiz->derecho, sucesor->valor);
    }

    return raiz;
}

Dalam fungsi ini, kita menyemak sama ada nilai nod adalah kurang daripada, lebih besar daripada, atau sama dengan nilai punca semasa. Bergantung pada kes, kami menjalankan tindakan berikut:

• Jika nilainya lebih kecil, kita pergi ke kiri pokok.
• Jika nilai lebih besar, kita pergi ke kanan pokok.
• Jika nilainya sama, kita mencari pengganti terdekat nod (nod terkecil dalam subpohon kanan) dan menggantikannya dengan nod semasa. Kemudian kami mengalih keluar pengganti dari subpokok kanan.

Traversals dalam pokok binari

Traversals ialah operasi yang membolehkan kita melawati semua nod pokok binari dalam susunan tertentu. Terdapat tiga jenis lawatan biasa:

Penjejakan dalam tertib : Melawat subpokok kiri dahulu, kemudian nod semasa, dan akhirnya subpokok kanan. Berikut ialah fungsi C yang melakukan penjejakan dalam tertib bagi pokok binari:

void inOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        inOrden(raiz->izquierdo);
        printf("%d ", raiz->valor);
        inOrden(raiz->derecho);
    }
}

Penjejakan pra-pesanan : Melawat nod semasa dahulu, kemudian subpokok kiri, dan akhirnya subpokok kanan. Berikut ialah fungsi C yang melakukan penjejakan pra-pesanan bagi pokok binari:

void preOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        printf("%d ", raiz->valor);
        preOrden(raiz->izquierdo);
        preOrden(raiz->derecho);
    }
}

Penjejakan pasca-tertib : Melawat subpokok kiri dahulu, kemudian subpokok kanan, dan akhirnya nod semasa. Berikut ialah fungsi C yang melakukan penjejakan pasca-tertib bagi pokok binari:

void postOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        postOrden(raiz->izquierdo);
        postOrden(raiz->derecho);
        printf("%d ", raiz->valor);
    }
}

Cari elemen

Mencari elemen dalam pokok binari membolehkan kami mencari nilai tertentu dengan cepat dalam struktur data. Berikut ialah fungsi C untuk mencari elemen dalam pokok binari:

struct NodoArbol* buscarElemento(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL || raiz->valor == valor) {
        return raiz;
    }

    if (valor < raiz->valor) {
        return buscarElemento(raiz->izquierdo, valor);
    } else {
        return buscarElemento(raiz->derecho, valor);
    }
}

Fungsi ini melakukan carian rekursif dalam pokok binari. Jika nilai nod semasa adalah sama dengan nilai yang dicari, nod dikembalikan. Jika tidak, subpokok kiri atau kanan dicari berdasarkan nilai dan proses diulang sehingga nilai ditemui atau nod nol dicapai.

Contoh pelaksanaan pokok binari dalam C

Sekarang kita telah membincangkan asas pokok binari dan cara melaksanakannya dalam C, mari kita lihat beberapa contoh praktikal.

Contoh 1: Mencipta pokok binari

Katakan kita ingin mencipta pokok binari dengan nilai berikut: 10, 5, 15, 3, 7, 13, 18. Berikut ialah cara kita boleh melakukannya dalam C:

int main() {
    struct NodoArbol* raiz = NULL;

    raiz = insertarNodo(raiz, 10);
    raiz = insertarNodo(raiz, 5);
    raiz = insertarNodo(raiz, 15);
    raiz = insertarNodo(raiz, 3);
    raiz = insertarNodo(raiz, 7);
    raiz = insertarNodo(raiz, 13);
    raiz = insertarNodo(raiz, 18);

    return 0;
}

Dalam contoh ini, kami mencipta penunjuk ke akar pokok dan kemudian menggunakan fungsi tersebut insertarNodo untuk menambah nilai pada pokok.

Contoh 2: Traversal tertib bagi pokok binari

Untuk mencetak nilai pokok binari dalam susunan, kita boleh memanggil fungsi inOrden seperti berikut:

int main() {
    // Crear el árbol binario

    printf("Recorrido en orden: ");
    inOrden(raiz);
    printf("\n");

    return 0;
}

Contoh ini akan mencetak nilai dalam pokok dalam susunan menaik.

Soalan yang kerap ditanya

1. Apakah perbezaan antara pokok binari dan pokok carian binari?

Pokok carian binari (BST) ialah jenis pokok binari khas di mana elemen disusun supaya nilai yang lebih kecil berada di sebelah kiri dan nilai yang lebih besar berada di sebelah kanan. Ini membolehkan pencarian elemen yang lebih cekap berbanding dengan pokok binari biasa.

2. Bolehkah saya mempunyai nod dengan nilai pendua dalam pokok binari?

Ya, adalah mungkin untuk mempunyai nod dengan nilai pendua dalam pokok binari. Walau bagaimanapun, bergantung pada pelaksanaan dan peraturan khusus pokok binari, mungkin terdapat cara yang berbeza untuk menangani nod pendua. Sesetengah pelaksanaan mungkin membenarkan pendua dan menyimpannya dalam sebarang susunan, manakala yang lain mungkin memerlukan nilai pendua dikendalikan secara khusus atau dibuang.

3. Bagaimanakah saya boleh mengalih keluar nod tertentu daripada pokok binari?

Untuk mengalih keluar nod tertentu daripada pokok binari, anda perlu mengikuti langkah berikut:

1. Cari nod yang anda mahu padamkan menggunakan carian pokok.
2. Pertimbangkan kes penyingkiran yang berbeza:
   • Jika nod tidak mempunyai anak, anda boleh memadamkannya dan membebaskan memorinya.
   • Jika nod hanya mempunyai seorang anak, anda boleh menggantikan nod dengan anaknya.
   • Jika nod mempunyai dua anak, anda mesti mencari pengganti terdekat (nod terkecil dalam subpokok kanan) dan menggantikan nilai nod yang akan dipadamkan dengan nilai pengganti. Kemudian keluarkan pengganti dari pokok itu.
3. Laraskan pautan dan penunjuk seperti yang diperlukan untuk mengekalkan struktur pokok yang betul.

4. Apakah pokok binari penuh?

Pokok binari penuh ialah jenis pokok binari khas di mana semua peringkat, kecuali mungkin yang terakhir, diisi sepenuhnya, dan nod peringkat terakhir terletak sejauh ke kiri yang mungkin. Ini bermakna semua nod mempunyai dua anak, kecuali mungkin nod pada tahap terakhir, yang mungkin mempunyai satu atau tiada anak.

5. Berapakah ketinggian pokok binari?

Ketinggian pokok binari ialah panjang laluan terpanjang dari akar ke daun. Dalam erti kata lain, ia adalah bilangan maksimum tepi antara akar dan mana-mana daun dalam pokok. Ketinggian diukur dari segi bilangan tahap, jadi pokok dengan hanya satu nod mempunyai ketinggian 0, dan pokok kosong tidak mempunyai ketinggian.

6. Bilakah saya harus menggunakan pokok binari dalam program saya?

Pokok binari berguna dalam pelbagai situasi. Beberapa kes biasa di mana anda mungkin menggunakan pokok binari termasuk:

• Carian elemen yang cekap: Jika anda perlu mencari elemen dalam struktur data dengan cepat, pepohon binari boleh menyediakan akses yang cekap kepada data.
• Mewakili perhubungan hierarki: Pokok binari sesuai untuk mewakili perhubungan hierarki, seperti struktur direktori dalam sistem fail.
• Pengisihan Data: Anda boleh menggunakan pepohon carian binari untuk mengisih data dengan cekap dan melakukan carian, sisipan dan pemadaman dalam masa logaritma.

Ingat untuk menilai keperluan anda dan pertimbangkan kerumitan operasi pada pokok binari sebelum memutuskan untuk menggunakannya dalam program anda.

Kesimpulan

Dalam panduan komprehensif ini, kami telah meneroka konsep asas pokok binari dalam C. Kami telah mempelajari tentang strukturnya, cara memasukkan dan mengalih keluar nod, melakukan traversal dan mencari unsur dalam pokok binari.

Kami berharap panduan ini telah memberi anda pemahaman yang kukuh tentang pokok binari dan cara melaksanakannya dalam C. Pokok binari adalah struktur data yang serba boleh dan berkuasa yang boleh membantu anda menyelesaikan pelbagai masalah dalam pengaturcaraan.

Ingatlah untuk berlatih dan bereksperimen dengan contoh yang disediakan untuk mengukuhkan pemahaman anda tentang pokok binari dalam C. Semoga berjaya dalam perjalanan pembelajaran dan pembangunan perisian anda!