Latihan 2
Latihan: Menghitung Kedalaman Pohon
Menggunakan rekursif untuk membandingkan dua cabang dan menemukan jalur terpanjang (kedalaman maksimum) dari sebuah Pohon Biner.
Menyiapkan Halaman
Butuh Bantuan Asisten?
Menggunakan rekursif untuk membandingkan dua cabang dan menemukan jalur terpanjang (kedalaman maksimum) dari sebuah Pohon Biner.
Melanjutkan tugas Anda di divisi HRD, kini Bos Anda ingin mengetahui seberapa "dalam" hierarki jabatan di perusahaan ini. Akar pohon (CEO) dihitung sebagai tingkat 1. Jika CEO memiliki Manajer (tingkat 2), dan Manajer memiliki staf (tingkat 3), maka kedalaman perusahaan tersebut adalah 3.
Dalam struktur data, panjang jalan maksimum dari akar hingga ke daun yang paling ujung disebut dengan Kedalaman (Depth) atau Tinggi Pohon.
Untuk menyelesaikannya, Anda tidak bisa sekadar menghitung total simpul. Anda harus meminta komputer menelusuri cabang kiri dan cabang kanan secara terpisah, lalu memilih mana cabang yang lebih panjang, dan menambahkannya dengan 1 (untuk menghitung simpul saat ini).
Lengkapi fungsi Tinggi(Node *P) menggunakan logika rekursif berikut :
IsTreeEmpty), maka tingginya pasti 0.Tinggi(P->left) dan simpan hasilnya di variabel tLeft. Lakukan hal yang sama untuk sub-pohon kanan dan simpan di tRight.tLeft dan tRight. Kembalikan nilai yang paling besar tersebut dan jangan lupa ditambah 1.Program akan mencetak satu baris teks berisi angka yang merepresentasikan tinggi atau kedalaman maksimum dari pohon yang disimulasikan.
Berdasarkan struktur pohon pada kode, cabang kiri mencapai simpul F (Level 4), sedangkan cabang kanan hanya berhenti di simpul C (Level 2). Oleh karena itu, kedalaman maksimumnya adalah 4.
Output:
=== ANALISIS KEDALAMAN POHON ===
Tinggi/Kedalaman Maksimum: 4 tingkatHint: Mengapa Harus Ditambah 1?
Fungsi ini bekerja dari bawah ke atas. Saat fungsi mencapai daun ujung (F), anak kirinya (NULL) mengembalikan 0, anak kanannya (NULL) mengembalikan 0. Nilai maksimumnya adalah 0.Daun F kemudian berkata: "Tinggiku adalah 1 + 0 = 1". Simpul E (induk F) akan menerima angka 1 dari F, lalu ia berkata: "Tinggiku adalah 1 + (tinggi anakku) = 2". Begitu seterusnya hingga mencapai Akar utama.