pertemuan 4



Tree

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebut root atau akar.

Binary Tree

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

ada beberapa jenis dari binary tree yatu : 

a) Full Binary Treeb

Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

      

b) Complete Binary Tree

    Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

c) Skewed Binary Tree

Skewdi Binary Tree adalah tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

Rumus untuk mencari node pada tree :

- mengambil yang bagian kiri      = 2p+1

- mengambil yang bagian kana n = 2p+2

- mengambil parentnya               = (p-1)/2

Expresion Tree Concept

infix     = a + c * b (a+b)

postfix  =-a * cb (+ab)

prefix    =abc-* (ab+)

contoh soal  

c/a*2+3/12+21 tentukan infix, postfix dan prefix

infix     =c/a*2+3/12+21

postfix =++*/ca2/3 12 21

prefix   =21 3 12 /2ca/*++

Setiawan Faisal.K

1701307501

www.binus.ac.id || www.skyconnectiva.com