BAB VII POHON BINAR POHON Pohon atau tree adalah salah satu bentuk graph terhubung yang tidak mengandung sirkuit. Karena merupakan graph terhubung, maka pada pohon selalu terdapat path atau jalur yang menghubungkan setiap dua simpul dalam pohon. Kali ini kita sampai pada pembahasan terhadap suatu bentuk pohon yang dilengkapi dengan apa yang disebut AKAR atau ROOT. Pohon semacam ini disebut Pohon berakar atau Rooted Tree. Lebih khusus lagi tentang pohon berakar disebut pohon binar. 1. Pohon Umum ( General Tree) 2. Pohon berakar (Rooted Tree) - Pohon Binar Co 7 – 1 : Pohon berakar T : P
Q
R
T
S
U
V
W
Sifat utama sebuah pohon berakar adalah : 1. Jika pohon mempunyai simpul sebanyak n, maka banyaknya ruas atau edge adalah (n-1). Pada pohon T banyak simpul adalah n = 8, dan banyak edge (n-1) = 8-1 = 7
55
By : Anie
2. mempunyai simpul khusus yang disebut Root, jika simpul tersebut memiliki derajat ke luar >= 0, dan derajat masuk = 0. Simpul P merupakan root pada pohon T 3. Mempunyai simpul yang disebut sebagai daun atau leaf, jika simpul tersebut berderajat ke luar = 0 dan berderajat masuk = 1. Simpul R, S, V, W merupakan daun pada pohon T. 4. Setiap simpul mempunyai tingkatan atau level, yang dimulai dari root yang levelnya = 0, sampai dengan level n pada daun paling bawah. Pada pohon T :
P berLevel 0 Q dan T berlevel 1 R, S dan V berlevel 2 V dan W berlevel 3
Simpul yang berlevel sama disebut bersaudara atau Brother atau Stribling. 5. Pohon mempunyai ketinggian atau kedalaman atau height, yang merupakan level tertinggi + 1. Pohon T mempunyai = 3 + 1 = 4 6. Pohon mempunyai Weight atau berat atau bobot, yang merupakan banyaknya daun pada pohon. Pohon T mempunyai bobot 4 Istilah yang digunakan pada pohon Binar : 1. Root / Akar Suatu Simpul khusus yang memiliki derajat ke luar >= 0 dan derajat masuk = 0. 2. leaf / Daun / terminal Suatu simpul yang memiliki derajat ke luar = 0 dan derajat masuk = 1. 3. Simpul / Node Himpunan hingga elemen yang merupakan data pada pohon / tree. 4. Pohon Null / hampa Pohon yang tidak memiliki elemen / data. 5. Rekursif Sifat / definisi dari pohon berakar dimana menjelaskan didalam pohon terdapat pohon yang lain. 56
By : Anie
6. Suksessor (kanan / kiri) Merupakan turunan (descendant) dari root atau dikenal dengan anak / child 7. Predessor Merupakan Parent dari child / anak atau moyang (ancestor) 8. Similar Pohon yang memiliki bangun / susunan yang sama. Jika pohon mempunyai elemen yang sama pada simpul yang bersesuaian disebut salinan / copy 9. Complete / Lengkap Suatu pohon binar yang mengandung semua simpul untuk semua tingkat. 10. Almost Complete / Hampir Lengkap Suatu pohon binar yang tidak mengandung semua simpul untuk semua tingkat. 11. Simpul Internal Simpul dengan 2 anak, yang diberi simbol lingkaran 12. Simpul Eksternal Simpul tanpa anak, yang diberi simbol bujursangkar 13. Extended binary tree Pohon binar yang dikembangkan bila setiap simpul mempunyai 0 atau 2 anak. 14. Height Balanced Tree / Pohon ketinggian seimbang Pohon binar yang mempunyai sifat bahwa ketinggian subpohon kiri dan subpohon kanan dari pohon tersebut berbeda paling banyak 1. NOTASI PREFIX, INFIX DAN POSTFIX SERTA TRAVERSAL POHON Struktur pohon dipakai untuk menempatkan data, guna memudahkan pekerjaan cari (search). Pohon juga berguna untuk menyajikan koleksi data yang mempunyai struktur logik bercabang. Proses kunjungan dalam pohon dengan setiap simpul hanya dikunjungi tepat satu kali disebut traversal. Tiga kegiatan yang terdapat dalam traversal pohon binar adalah : 1. Mengunjungi simpul akar (root) 2. Melakukan traversal subpohon kiri 3. Melakukan traversal subpohon kanan
57
By : Anie
TRAVERSAL PRE ORDER 1. Kunjungi Simpul Akar 2. Lakukan traversal subpohon kiri secara pre-order 3. Lakukan traversal subpohon kanan secara pre-order Traversal pre – order akan menghasilkan Notasi prefix Co 7 – 2 : Perhatikan garis putus – putus yang mengambarkan traversal pre – order
+
*
C
E
D
Hasil yang diperoleh adalah : + * C D E
TRAVERSAL IN ORDER 1. Lakukan traversal subpohon kiri secara in-order 2. Kunjungi Simpul Akar 3. Lakukan traversal subpohon kanan secara in-order Traversal in – order akan menghasilkan Notasi infix
58
By : Anie
Co 7 – 3 : Perhatikan garis putus – putus yang mengambarkan traversal in – order
+
*
C
E
D
Hasil yang diperoleh adalah : C * D + E TRAVERSAL POST ORDER 1. Lakukan traversal subpohon kiri secara Post-order 2. Lakukan traversal subpohon kanan secara post-order 3. Kunjungi Simpul Akar Traversal post – order akan menghasilkan Notasi postfix Co 7 – 4 : Perhatikan garis putus – putus yang mengambarkan traversal post – order
+
*
C
E
D
Hasil yang diperoleh adalah : C D * E +
59
By : Anie
Lat 7 – 1 : Diketahui pohon binar berikut ini : /
+
+
*
+
A
D
C
E
*
F
G
B
Tentukanlah : 1. Root 2. Leaf 3. Height 4. Weight 5. Notasi Prefix, infix dan postfix
60
By : Anie
