4-"Tree and Binary Tree"-2101707900-Kana Hayalia Ahmad

TREE

1. Konsep Tree:

Di dalam tree terdapat beberapa istilah, seperti berikut(Perhatikan gambar di atas):

a. Root (akar) adalah node yang berada di paling atas/top. Berdasarkan gambar diatas rootnya adalah 1.

b. Leaf(daun) adalah node yang tidak bercabang(children). Berdasarkan gambar diatas leafnya adalah 7.

c. Degree(derajat/level)

Ex:

- Degree of tree = 4.

- Degree of 7=3.

d. Height (Tinggi dari tree)

Tree di atas tersebut memiliki tinggi 4. Cara menentukannya dengan melihat levelnya.

e. Parent

Ex:

- Parent of 5=3.

- Parent of 7=6.

f. Children

Ex:

- Children of 8=9,10.

- Children of 2=3.

g. Sibling(saudara)

Ex:

- Sibling of 6=2.

h. Ancestor(leluhur, kita telurusi setiap node yang segaris dengan pernyataan sampai mengarah ke root)

Ex:

- Ancestor of 9=1,6,8.

- Ancestor of 2=1.

i. Descendant (Keturunannya, semua node dibawahnya disebutkan)

Ex :

- Descendant of 6=7,8,9,10.

2. Penerapan Konsep Tree:

Cara menentukan:

a. Prefix (Dibaca dari atas) : +*xy*2-z3

b. Postfix (Dibaca dari bawah) : xy*z32-*+

c. Infix (Dibaca dari bawah bagian kiri kemudian ke tengah atas kemudian bawah bagian kanan, tapi tetep dibagian kanan maupun kiri cara membacanya dari sebelah kiri : x*y+2*(z-3)

BINARY TREE

1. Konsep:

Binary tree adalah tree dimana nodenya mempunyai children maksimal 2. Dimana kedua anak tersebut dibagi menjadi anak kanan dan anak kiri.

Pembagian Binary Tree:

a. Perfect Binary Tree

Perfect Binary tree adalah tree dimana setiap nodenya mempunyai children tepat berjumlah 2.

Gambar:

b. Complete Binary Tree

Complete Binary Tree adalah tree dimana setiap node terisis penuh, kecuali node terakhir/bawah. Perfect Binary tree juga termasuk complete binary tree juga.

Gambar:

c. Skewed Binary Tree

Skewed Binary Tree adalah tree dimana setiap nodenya hanya mempunyai satu children.

Gambar:

Proses Aritmatika di Binary Tree:

1. Cara menghitungnya maksimum node disetiap level (k) =2k.

2. Cara menghitung maksimum node berdasarkan tinggi (h) = 2h+1 - 1

3. Cara menghitung minimum tingginya berdasarkan jumlah node (n) = 2log(n).

2. Penerapan Konsep Binary Tree:

Binary Tree menggunakan konsep double linked list. Terdapat tiga pointer.

Berdasarakan gambar diatas terdapat 3 jenis pointer yaitu *parent,*left,*right.