Pohon Biner dalam C: Panduan Lengkap untuk Pemula

Informatec Digital » Algoritma » Pohon Biner dalam C: Panduan Lengkap untuk Pemula

Selamat datang di panduan lengkap tentang pohon biner dalam bahasa C. Dalam artikel ini, kita akan membahas dasar-dasar pohon biner dan cara mengimplementasikannya dalam bahasa pemrograman C. Jika Anda seorang pemula dalam pemrograman atau hanya ingin meningkatkan keterampilan bahasa C Anda, panduan ini cocok untuk Anda.

Los pohon biner Mereka adalah struktur data fundamental dalam ilmu komputer dan digunakan dalam berbagai aplikasi. Memahami cara kerjanya dan cara menerapkannya akan membantu Anda memecahkan masalah rumit dengan lebih efisien dan elegan.

Sepanjang artikel ini, kita akan menjelajahi dasar-dasar pohon biner, termasuk strukturnya, penyisipan dan penghapusan node, traversal, dan pencarian elemen. Kami juga akan memberikan Anda contoh-contoh praktis dalam bahasa C sehingga Anda dapat melihat bagaimana konsep ini diterapkan dalam praktik.

Jadi mari kita mulai!

Apa itu pohon biner?

Pohon biner adalah struktur data hierarkis yang terdiri dari simpul-simpul yang saling terhubung. Setiap simpul dapat memiliki hingga dua simpul anak: satu di sebelah kiri dan satu di sebelah kanan. Struktur dua cabang inilah yang membedakan pohon biner dari struktur data lainnya.

Pada pohon biner, simpul pertama disebut simpul akar. Node anak disebut node anak, dan node tanpa anak disebut node daun. Node yang berada pada tingkat yang sama disebut node saudara.

Manfaat pohon biner

Pohon biner menawarkan beberapa keuntungan dalam hal penyimpanan dan pencarian data yang efisien. Beberapa manfaat utama meliputi:

1. Pencarian yang efisienPohon biner memungkinkan elemen dicari pada waktu proses lebih cepat daripada struktur data lain, seperti daftar tertaut. Hal ini dikarenakan struktur hierarki pohon dan kemampuannya mempartisi kumpulan data dengan cepat.
2. Pemasangan dan pelepasan yang fleksibelPohon biner sangat mudah beradaptasi dengan operasi penyisipan dan penghapusan simpul. Tidak seperti struktur data statis seperti array, pohon biner dapat tumbuh dan mengubah strukturnya secara dinamis.
3. Representasi hubungan hierarkisPohon biner sangat berguna untuk menggambarkan hubungan hierarkis antara elemen. Misalnya, dalam struktur direktori file, setiap direktori dapat direpresentasikan sebagai simpul di pohon, dengan subdirektori dan file sebagai simpul anaknya.

Struktur pohon biner

Sebelum kita menyelami implementasi pohon biner di C, penting untuk memahami struktur dasarnya. Setiap simpul pada pohon biner berisi nilai dan referensi ke simpul anak kiri dan kanannya, jika ada.

Tabel berikut menunjukkan struktur simpul dalam pohon biner:

simpul biner
keberanian
simpul kiri
simpul kanan

Setiap node dapat menyimpan jenis data apa pun, seperti bilangan bulat, karakter, atau struktur yang lebih kompleks. Simpul akar adalah titik awal pohon, dan dari situ kita dapat mengakses semua simpul lainnya.

Menerapkan pohon biner dalam C

Sekarang setelah kita memiliki pemahaman dasar tentang pohon biner, sekarang saatnya untuk menerapkannya di Bahasa pemrograman C.. Selanjutnya, kita akan melihat cara mendeklarasikan dan menggunakan struktur pohon biner di C.

Mendeklarasikan struktur pohon biner

Dalam C, kita dapat mendeklarasikan struktur pohon biner menggunakan struktur dan penunjuk. Berikut adalah deklarasi dasar strukturnya:

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

Dalam struktur ini, valor mewakili nilai yang disimpan di node, dan izquierdo y derecho adalah penunjuk ke simpul anak kiri dan kanan.

Membuat node baru

Untuk membuat simpul baru dalam pohon biner, kita perlu mengalokasikan memori untuk simpul tersebut dan menetapkan nilainya. Berikut adalah fungsi C yang membuat node baru:

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 itu malloc Digunakan untuk mengalokasikan memori dinamis ke node. Kemudian kita tetapkan nilai simpulnya dan kembalikan simpul yang sudah dibuat.

Memasukkan node

Penyisipan simpul merupakan proses mendasar dalam pohon biner. Memungkinkan Anda menambahkan elemen baru ke pohon pada posisi yang benar berdasarkan nilai simpul. Berikut ini adalah fungsi C untuk memasukkan simpul ke dalam pohon biner:

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 petunjuk ke akar pohon dan nilai simpul yang akan disisipkan. Jika akarnya null, berarti pohonnya kosong dan kita membuat simpul baru di akar. Kalau tidak, kita bandingkan nilai simpul dengan nilai akar dan putuskan apakah akan menyisipkan simpul di sebelah kiri atau kanan.

Menghapus node

Menghapus simpul pada pohon biner bisa sedikit lebih rumit. Tergantung pada beberapa kasus, seperti apakah node yang akan dihapus mempunyai anak atau tidak. Berikut ini adalah fungsi C untuk menghapus simpul di pohon biner:

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 memeriksa apakah nilai simpul lebih kecil dari, lebih besar dari, atau sama dengan nilai akar saat ini. Tergantung pada kasusnya, kami melakukan tindakan berikut:

• Jika nilainya lebih kecil, kita ke kiri pohon.
• Jika nilainya lebih besar, kita ke sebelah kanan pohon.
• Jika nilainya sama, kita cari penerus terdekat dari simpul tersebut (simpul terkecil pada sub-pohon sebelah kanan) dan menggantinya dengan simpul saat ini. Lalu kita hapus penerusnya dari sub-pohon sebelah kanan.

Lintasan dalam pohon biner

Traversal adalah operasi yang memungkinkan kita mengunjungi semua simpul pohon biner dalam urutan tertentu. Ada tiga jenis tur umum:

Lintasan berurutan: Kunjungi sub-pohon kiri terlebih dahulu, lalu simpul saat ini, dan terakhir sub-pohon kanan. Berikut adalah fungsi C yang melakukan penelusuran inorder pada pohon biner:

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

Pra-pesan tur: Kunjungi simpul saat ini terlebih dahulu, kemudian sub-pohon kiri, dan terakhir sub-pohon kanan. Berikut adalah fungsi C yang melakukan penelusuran preorder pada pohon biner:

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

Lintasan pasca-pesanan: Kunjungi sub-pohon kiri terlebih dahulu, lalu sub-pohon kanan, dan terakhir simpul saat ini. Berikut adalah fungsi C yang melakukan penelusuran postorder pada pohon biner:

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

Pencarian elemen

Pencarian elemen dalam pohon biner memungkinkan kita untuk dengan cepat menemukan nilai tertentu dalam struktur data. Berikut adalah fungsi C untuk mencari elemen di pohon biner:

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 pencarian rekursif pada pohon biner. Jika nilai simpul saat ini sama dengan nilai yang dicari, simpul tersebut dikembalikan. Jika tidak, sub-pohon kiri atau kanan dicari berdasarkan nilai dan proses diulang hingga nilai ditemukan atau simpul nol tercapai.

Contoh penerapan pohon biner di C

Sekarang setelah kita membahas dasar-dasar pohon biner dan cara mengimplementasikannya dalam C, mari kita lihat beberapa contoh praktis.

Contoh 1: Membuat pohon biner

Misalkan kita ingin membuat pohon biner dengan nilai-nilai berikut: 10, 5, 15, 3, 7, 13, 18. Berikut ini cara melakukannya dalam bahasa 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, kita membuat pointer ke akar pohon dan kemudian menggunakan fungsi insertarNodo untuk menambahkan nilai ke pohon.

Contoh 2: Penjelajahan berurutan dari pohon biner

Untuk mencetak nilai pohon biner secara berurutan, kita dapat memanggil fungsi inOrden sebagai berikut:

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

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

    return 0;
}

Contoh ini akan mencetak nilai pada pohon dalam urutan menaik.

Pertanyaan yang sering diajukan

1. Apa perbedaan antara pohon biner dan pohon pencarian biner?

Pohon pencarian biner (BST) adalah jenis pohon biner khusus yang elemen-elemennya disusun sedemikian rupa sehingga nilai yang lebih kecil berada di sebelah kiri dan nilai yang lebih besar berada di sebelah kanan. Hal ini memungkinkan pencarian elemen yang lebih efisien dibandingkan dengan pohon biner biasa.

2. Bisakah saya memiliki node dengan nilai duplikat di pohon biner?

Ya, dimungkinkan untuk memiliki simpul dengan nilai duplikat dalam pohon biner. Namun, bergantung pada implementasi dan aturan spesifik pohon biner, mungkin ada cara berbeda untuk menangani node duplikat. Beberapa implementasi mungkin mengizinkan duplikat dan menyimpannya dalam urutan apa pun, sementara yang lain mungkin mengharuskan nilai duplikat ditangani secara khusus atau dibuang.

3. Bagaimana cara menghapus simpul tertentu dari pohon biner?

Untuk menghapus simpul tertentu dari pohon biner, Anda perlu mengikuti langkah-langkah berikut:

1. Temukan simpul yang ingin Anda hapus menggunakan pencarian pohon.
2. Pertimbangkan berbagai kasus eliminasi:
   • Jika node tersebut tidak memiliki anak, Anda cukup menghapusnya dan mengosongkan memorinya.
   • Jika node tersebut hanya memiliki satu anak, Anda dapat mengganti node tersebut dengan anaknya.
   • Jika simpul tersebut memiliki dua anak, Anda harus menemukan penerus terdekat (simpul terkecil pada sub-pohon kanan) dan mengganti nilai simpul yang akan dihapus dengan nilai penerus. Lalu hapus penerusnya dari pohon.
3. Menyesuaikan tautan dan petunjuk sebagaimana diperlukan untuk mempertahankan struktur pohon yang benar.

4. Apa itu pohon biner penuh?

Pohon biner penuh merupakan jenis pohon biner khusus yang semua tingkatnya, kecuali mungkin tingkat terakhir, terisi penuh, dan simpul pada tingkat terakhir berlokasi sejauh mungkin ke kiri. Artinya semua node mempunyai dua anak, kecuali mungkin node pada tingkat terakhir, yang boleh jadi mempunyai satu anak atau tidak mempunyai anak sama sekali.

5. Berapakah tinggi pohon biner?

Tinggi pohon biner adalah panjang jalur terpanjang dari akar ke daun. Dengan kata lain, ini adalah jumlah tepi maksimum antara akar dan daun mana pun di pohon. Tinggi diukur berdasarkan jumlah tingkat, jadi pohon dengan hanya satu simpul memiliki tinggi 0, dan pohon kosong tidak memiliki tinggi.

6. Kapan saya harus menggunakan pohon biner dalam program saya?

Pohon biner berguna dalam berbagai situasi. Beberapa kasus umum di mana Anda mungkin menggunakan pohon biner meliputi:

• Pencarian elemen yang efisien: Jika Anda perlu mencari elemen dengan cepat dalam suatu struktur data, pohon biner dapat menyediakan akses yang efisien ke data tersebut.
• Mewakili hubungan hierarkis: Pohon biner ideal untuk mewakili hubungan hierarkis, seperti struktur direktori dalam sistem file.
• Penyortiran Data: Anda dapat menggunakan pohon pencarian biner untuk mengurutkan data secara efisien dan melakukan pencarian, penyisipan, dan penghapusan dalam waktu logaritmik.

Ingatlah untuk mengevaluasi kebutuhan Anda dan mempertimbangkan kompleksitas operasi pada pohon biner sebelum memutuskan untuk menggunakannya dalam program Anda.

Kesimpulan

Dalam panduan komprehensif ini, kami telah menjelajahi konsep dasar pohon biner dalam bahasa C. Kami telah mempelajari tentang strukturnya, cara memasukkan dan menghapus simpul, melakukan penelusuran, dan mencari elemen dalam pohon biner.

Kami harap panduan ini memberi Anda pemahaman mendalam tentang pohon biner dan cara mengimplementasikannya dalam C. Pohon biner adalah struktur data serbaguna dan canggih yang dapat membantu Anda memecahkan berbagai masalah dalam pemrograman.

Jangan lupa berlatih dan bereksperimen dengan contoh-contoh yang diberikan untuk memperkuat pemahaman Anda tentang pohon biner dalam bahasa C. Semoga berhasil dalam perjalanan pembelajaran dan pengembangan perangkat lunak Anda!