Pertemuan 4 - Tree, Binary Tree & Expression Tree

Tree, Binary Tree & Expression Tree

Tree (Pohon)

Real World

Computer Scientist’s View

Definisi: 

- Kumpulan node yang saling terhubung secara hirarki.

- Hiarki = Bertingkat.

- Tiap node dapat berisi data dan link (penghubung) ke node lainnya.

- Tiap node memiliki satu induk, kecuali node root (akar) yang tidak memiliki induk.

- Tiap node dapat memiliki anak dalam jumlah berapapun.

CONTOH TREE

Linked list dan Tree:

- Linked list -> linear/serial data
   Contoh : nama-nama mahasiswa dalam satu kelas.

- Tree -> non linear/hierachically data
    Contoh : tingkatan pegawai dalam perusahaan.

Tree (Pohon)
- Root adalah node yang memiliki hirarki tertinggi.
- Subtree (pohon anak) adalah beberapa node yang tersusun hirarki yang ada dibawah root.

Tree (Pohon)
- Level adalah posisi hirarki dari sebuah node. Untuk root bisa diberikan level 0 atau 1.
- Leaf (Daun) adalah node yang tidak memiliki anak atau node yang berada pada hirarki paling bawah.
- Height (tinggi)/depth adalah jumlah level dari sebuah tree.

Istilah Tree (Pohon)

Ancestor (F) = C,A
Descendant (B) = D,E
Parent (I) = H
Child (A) = B,C
Sibling (F) = G,H
Size = 9
Height = ¾
Root = A
Leaf = D,E,F,G,I
Degree (C) = 3

Binary Tree
- Tiap node pada binary tree hanya boleh memiliki paling banyak dua child.
- Sehingga hanya ada dua subtree pada binary tree yang disebut sebagai left dan right subtrees.

Tree dan Binary Tree
- Pada binary tree nilai degree tidak lebih dari 2, sedangkan pada tree tidak terbatas.
- Sub tree pada binary harus terurut (ord

ered), sedangkan pada tree tidak (un-ordered).

Jenis Binary Tree
- Berdasarkan subtree binary tree dibedakan menjadi 4 jenis:
     1. Full Binary Tree
     2. Complete Binary Tree
     3. Incomplete Binary Tree (Unbalanced Tree)
     4. Skewed Binary Tree

Jenis Tree (Full Binary Tree)
- Semua node (kecuali leaf) memiliki nol atau 2 anak dan tiap subtree memiliki panjang path yang disebut juga maximum binary tree.

Penelusuran seluruh node pada binary tree.
Metode :
 - Preorder
 - Inorder
 - Postorder
 - Level order

PreOrder Traversal
1. Cetak data pada root
2. Secara rekursif mencetak seluruh data pada subpohon kiri
3. Secara rekursif mencetak seluruh data pada subpohon kanan

 

Inorder traversal
1. Secara rekursif mencetak seluruh data pada subpohon kiri
2. Cetak data pada root
3. Secara rekursif mencetak seluruh data pada subpohon kanan

Postorder traversal
1. Secara rekursif mencetak seluruh data pada subpohon kiri
2. Secara rekursif mencetak seluruh data pada subpohon kanan
3. Cetak data pada root

PreOrder, PostOrder, InOrder

Pre-order :
        - Node, left, right
        - Ekspresi Prefix : ++a*bc*+*defg
Post-order :
        - Node, left, right
        - Ekspresi Postfix : abc*+de*f+g*+
In-order :
        - Node, left, right
        - Ekspresi Infix : a+b*c+d*e+f*g