Introduction to Tree, Binary Tree And Expression Tree
Tree
Apa yang dimaksud dengan tree?
Tree adalah pohon? Bukan namun tree yang akan dibahas ini merupakan kumpulan node.
Layaknya sebuah pohon, tree ini juga memiliki banyak bagian seperti akar, daun, dll.
Tree terdiri dari :
> Root : Bagian teratas dari tree
> Edge : Garis yang menghubungkan node-node yang ada
> Leaf : Bagian node yang tidak mempunyai anak (node) di bawahnya
Dari gambar diatas dapat diambil kesimpulan bahwa :
> 1 Merupakan root
> 8 dan 9 Merupakan sibling karena mempunyai parent yang sama, yaitu 4
> 8, 9, 5, 6, 7 Adalah Leaf
Binary Tree
Terdiri dari berbagai macam model seperti berikut :
Perfect Binary Tree
Sesuai dengan namanya perfect yang berarti sempurna, memiliki bentuk yang sempurna.
Complete Binary Tree
Tree jenis ini sudah memiliki bentuk yang lengkap. Maksudnya adalah memiliki jumlah node yang pas sampai pada node terakhir.
Skewed Tree
Tree ini termasuk tree yang bentuknya berantakan, sehingga tak heran orang-orang menyebutnya juga sebagai unbalanced tree, karena bentuknya yang lebih menjorok ke satu sisi (kanan/kiri).
Rumus yang dapat dikatakan ampuh untuk Binary Tree :
> Index untuk anak yang sebelah kiri
2p + 1 ; dimana p merupakan index dari parent
> Index untuk anak yang sebelah kanan
2p + 2
> Index untuk parent
(p – 1) / 2
Expression Tree
Berbeda dengan yang kita pelajari di tree dan binary tree, disini hanya dikenal 3 cara untuk menyatakan expression tree, yaitu :
> Prefix
> Postfix
> Infix
Dari ketiga hal diatas, yang paling kita sering gunakan dalam operasi matematika ialah infix.
– Infix adalah keadaan dimana operator (* / + -) berada di tengah-tengah angka.
Contoh Infix :
(A + B) / C
– Postfix adalah keadaan dimana operator berada setelah angka / diakhir.
Contoh Postfix:
A B + C /
– Prefix adalah keadaan dimana operator berada sebelum angka / diawal.
Contoh Prefix:
/ + A B C
Kalau masih kurang paham dengan contoh diatas, ada cara yang mudah untuk mengerjakannya.
> Infix : LVR
> Postfix : LRV
> Prefix : VLR