Pertemuan 5 - Introduction Tree, Binary Tree & Expression Tree (2)

Introduction to Tree, Binary Tree And Expression Tree 

KONSEP TREE

Tree adalah kumpulan dari satu atau beberapa node.

 Dari contoh gambar di atas, dapat disimpulkan :

• Degree dari C =3

• Heigth =4

• Parent dari B = A

• Children dari C = F, G, dan H

• Sibling dari D = C dan B

• Ancestor dari G = C dan A

• Descendant dari D = I dan J

Penjelasan :

• Node (simpul) yang paling atas disebut root (akar).

• Garis yang menghubungkan parent (orang tua) ke child (anak) adalah edge.

• Node yang tidak memiliki chlid disebut leaf (daun).

• Node yang memiliki parent yang sama disebut sibling (saudara).

• Degree (derajad) dari sebuah node adalah total sub tree dari node tersebut.

• Height / depth (tinggi) adalah derajad maksimum dari node dalam tree tersebut.

• Jika ada garis yang menghubungkan p ke q, maka p disebutancestor (nenek moyang) dari q, dan q adalah descendant(keturunan) dari p.

 Beberapa jenis tree :

1. Unary Tree (memiliki paling banyak 1 anak)

2. Binary Tree (memiliki paling banyak 2 anak)

3. Ternary Tree (memiliki banyak anak, lebih dari 2)

BINARY TREE

 

Binary tree adalah struktur data pohon berakar yang setiap nodenya memiliki paling banyak 2 anak (Biasa disebut dengan anak kiri dan anak kanan).

Tipe-tipe binary tree :

1. Balanced binary tree, di mana tidak ada daun yang jauh lebih jauh dari akarnya bila dibandingkan dengan daun yang lain.

2. Perfect binary tree, di mana setiap level memiliki depth yang sama.

3. Complete binary tree, di mana setiap tingkat, kecuali mungkin yang terakhir, benar-benar terisi penuh. Perfect binary tree merupakan complete binary tree.

4. Skewed binary tree, di mana setiap simpul memiliki paling banyak 1 anak.

Cara menghitung :

• Jumlah max node pada level k binary tree : 2k

• Jumlah max node pada binary tree dari ketinggian h : 2h+1 - 1

• Tinggi max binary tree dari n node : n - 1

• Ketinggian min binary tree dari n node : 2log(n)

EKSPRESI TREE

• Prefix : * + a b / - c d e

• Infix   : ( a + b ) * ( ( c - d ) / e

• Postfix: a b + c d - e / *

Contoh-Contoh :

1).  2 + a + ( b / 2 ) * 3

• Prefix : + 2 + a * / b 2 3

• P0ostfix: 2 a b 2 / 3 * + +

2).  3 / ( a + b ) - 2

• Prefix : - / 3 + a b 2

•  Postfix: 3 a b + / 2 -

3).  a + ( b / 2 ) * 3 / 2

• Prefix : + a / * / b 2 3 2

• Postfix: a b 2 / 3 * 2 / +