Pertemuan ke 4 - Tree,Binary Tree and Expression Tree - 2101650026- Kenny Wijaya

Tree Concept

Tree adalah sejumlah nodes yang saling terhubung

Degree of Tree = 5

Degree of '10' = 4

Parent of '2' = 1

Children of '9' = 18,19

Sibling of '7' = 6

Ancestor of '12' = 1, 3, 6

Paling atas (No.1) = Root
Penghubung parent dengan child = Edge
Node yang tidak memiliki child = Leaf
Node yang memiliki parent yang sama = Sibling
Tingkatan dalam Tree = Level (Mulai dari 0) / Degree (Mulai dari 1)


Binary Tree adalah
      Maximal children hanya boleh 2, Dan minimum children boleh 0

Beberapa Jenis Binary Tree

Skewed Binary Tree

Complete Binary Tree

Cara menghitung Node Max pada binary Tree  = 2^h+1 - 1
h adalah heigh / level

Contoh pada gambar diatas:

h = 3

 2³⁺¹ - 1 =  2⁴ - 1 = 16 - 1 = 15

Minimum Height of Binary Tree n Nodes --> ²log(n)
Maximum Height of Binary Tree n Nodes --> n-1

Contoh :

ada 16 Node, Berapa Height max dan min suatu binary Tree?

Min. Height : ²log(16) = 4

Max. Height : 16-1 = 15

Expressions Tree Concept

Prefix = Print L R

Postfix = L R Print

Infix   = L Print R

Contoh pada gambar diatas ini

Infix =  ((2*3) / (2-1)) + (5*(4-1))

Prefix =  + / * 2 3 - 2 1 * 5 - 4 1

Postfix = 2 3 * 2 1 - / 5 * 4 1 - +