Latihan 4

UAS — Tree

Latihan rekonstruksi Pohon Biner dan tracing fungsi rekursif dari naskah UAS ASD 2022 dan 2023.

Info

Soal-soal Tree pada UAS berbobot sangat tinggi (35-50 Poin) dan sangat menguji kemampuan berpikir visual serta tracing matematika di dalam fungsi rekursif. Naskah soal untuk materi Tree pada tahun 2022 dan 2023 ternyata 100% identik, baik dari segi gambar pohon maupun logika kodenya!

Soal 1: Rekonstruksi Pohon Biner

Terdapat sebuah pohon biner yang bagian sisi kanannya belum lengkap (berisi simpul kosong berlabel huruf). Diketahui simpul 55 adalah akar (root).

Daftar Latihan|Kembali ke Materi

Aturan utama In-Order adalah KIRI - AKAR - KANAN. Karena 55 adalah Akar utamanya, maka potong daftar angkanya tepat di angka 55 untuk membedakan secara instan kubu kiri dan kubu kanan!

Cabang Kiri: 8, 12, 28, 29, 30, 37, 42 (Sudah lengkap di gambar)
Cabang Kanan: 57, 63, 74, 83, 91, 97

Dengan mencocokkan sisa angka cabang kanan terhadap template simpul kosong di gambar (Kiri-Akar-Kanan), maka kita dapatkan susunan utuhnya (bagian hijau adalah simpul yang berhasil direkonstruksi):

Output: 2743

Langkah Penelusuran (Tracing):

Bongkar Fungsi Aneh: Jika Anda telusuri, fungsi Aneh sesungguhnya adalah fungsi klasik untuk menghitung Height (Kedalaman Maksimum) dari sebuah cabang pohon, dengan nilai daun = 1.
Hitung Tinggi (Aneh) masing-masing cabang dari Akar 55:
- Aneh(Kiri 55) = Aneh(28) -> Kedalaman maksimumnya menelusuri 4 simpul (28->37->30->29). Maka Height = 4.
- Aneh(Kanan 55) = Aneh(74) -> Kedalaman maksimumnya menelusuri 3 simpul (misal 74->91->97). Maka Height = 3.
Jalankan Hitung(55)
- Apakah Aneh(74) > Aneh(28)? -> 3 > 4 (SALAH).
- Masuk blok else: return (55 + Hitung(28))
Jalankan Hitung(28)
- Apakah Aneh(37) > Aneh(12)? -> 3 > 2 (BENAR).
- Masuk blok if: return (28 * Hitung(37))
Jalankan Hitung(37)
- Apakah Aneh(42) > Aneh(30)? -> 1 > 2 (SALAH).
- Masuk blok else: return (37 + Hitung(30))
Jalankan Hitung(30)
- Apakah Aneh(NULL) > Aneh(29)? -> 0 > 1 (SALAH).
- Masuk blok else: return (30 + Hitung(29))
Jalankan Hitung(29)
- Karena 29 adalah simpul Daun (IsTreeOneElmt), kembalikan isinya: 29.

Hasil Akhir (Penjumlahan Mundur):

Hitung(30) = 30 + 29 = 59
Hitung(37) = 37 + 59 = 96
Hitung(28) = 28 * 96 = 2688
Hitung(55) = 55 + 2688 = 2743

Soal 1: Rekonstruksi Pohon Biner

Soal 2: Tracing Rekursif Lanjut