Session 4: Introduction to Tree, Binary Tree And Expression Tree

Tree, apa itu tree? Tree merupakan kumpulan satu atau lebih node.

Tree memiliki 8 konsep, yaitu:

- Node di bagian atas disebut sebagai root.

- Garis yang menghubungkan orang tua anak itu adalah edge.

- Node yang tidak mempunyai anak adalah leaf.

- Node yang memiliki orang tua yang sama di sebut sibling.

- Degree dari node adalah banyak sub node dari degree tersebut.

- Height/Depth adalah tingkat maksimum dari node dalam sebuah pohon.

- Jika ada garis yang menghubungkan P untuk Q, lalu p disebut leluhur-Q, dan q adalah keturunan dari  P.

Tree

Dari gambar di atas di simpulkan:
Degree of tree = 3
Degree of C = 2
Height = 3
Parent of C = A
Children of A = B, C, D
Sibling of F = G
Ancestor of F = A, C
Descendant of C = F, G

Binary Tree Concept

- Pohon biner adalah sebuah struktur data pohon berakar di mana setiap node telah di paling dua anak-anak.
- Kedua-dua anak biasanya dibedakan kiri dan kanan anak anak.

- Node yang tidak memiliki anak disebut leaf.

Binary Tree

Di atas adalah contoh pohon biner yang memiliki 9 node,berakar pada simpul yang berisi 18.
Jika tidak berakar disebut juga daun node. yang berisi nomor 9, 12, 10 dan 23.


Berikut adalah tipe - tipe pada binary tree :
1. Perfect Binary Tree : dimana setiap tingkatan memiliki kedalaman yang sama.

2. Complete binary tree : pohon yang memiliki tipe yang sempurna.tetapi kesempurnaan tidak seharusnya memiliki kelengkapan.!

3. Skewed Binary Tree : setiap node/simpul yang memiliki 1 anak/hanya berakar 1

 

Ada beberapa peraturan di dalam sebuah binary tree yaitu:
- Tingkat 0 : max nodenya hanya 1
- Tingkat 1 : max nodenya hanya 2
- Tingkat 2 : max nodenya hanya 4
- Tingkat 3 : max nodenya hanya 8
- Dalam beberapa literatur, tingkat pohon biner dimulai dengan 1 (root).
- Rumus binary tree yaitu 2k.

Representasi Binary Tree
- implementasi menggunakan array

*Index 0 adalah simpul akar.
*Index anak sebelah kiri : 2p + 1
*Index anak sebelah kanan : 2p + 2
*Dan,index orang tua : (p – 1)/2

Implementasi dengan menggunakan link list

Ekspresi pada tree concept
Prefix : *+ab/-cde
Postfix : ab+cd-e/*
Infix : (a+b)*((c-d)/e)
Gambarnya :

Jika mengecek sebuah Infix,Prefix,Postfix bisa menggunakan rumus seperti berikut :
LVR => untuk cek Infix
LRV => untuk cek postfix
VLR => untuk mengecek prefix

www.binus.edu