28 Maret 2016
TREE AND BINARY TREE



TREE
Root : Node paling pertama / paling atas
Edge : Garis yang menghubungkan dari parent -> child
Leaf : Node yang tidak mempunya child
Sibling : Node - node yang memiliki parent yang sama
Degree of Node : berapa banyak child dari node tersebut
Height : Maksimum edge dari node ke leaf dengan jarak terpanjang

BINARY TREE
Sebuah Tree dimana setiap node hanya memiliki dua child
dimana dua child ini dibagi left child & right child

Type-type Binary Tree

Perfect Binary Tree : Masing Masing punya dua Child dan Memiliki Level yang setara antara left dan right 




 Complete Binary Tree : Beberapa punya dua Child dan ada yang tidak punya Child dan hanya punya satu Child (Level nya Tidak Sama)





Skewed Binary Tree : Child hanya 1 sampai paling bawah 



Balanced Binary Tree : Left dan Right dari Root ke Leaf memilik Jarak yang sama





Rumus Binary Tree

Untuk Menghitung Jumlah Node : Level H =  2^H

Total Maximum Node dalam Binary Tree : 2^H+1 – 1

Tinggi Minimum : 2 Log (n) (Isi Masing masing dengan 2 child)

Tinggi Maximum : n - 1 ( Masing masing dengan 1 child)

Skewed Binary Tree punya tinggi maksimum






Index 0 = Root
Index Left = 2p + 1 (p = parent index)
Index Right = 2p + 2
Index parent = (c-2)/2 (c = Child Index)

Expression Tree Concept



Prefix = *+ab/-cde
Postfix =ab+cd-e/*
Infix = (a+b)*((c-d/e)) Dari kiri ke kanan

Infix = Left Print Right
Prefix = Print Left Right
Postfix = Left Right Print