Pertemuan 4 - Introduction to Tree, Binary Tree and Expression Tree - 2101696973 - Rifqi Amru Bakti

Nama : Rifqi Amru Bakti
NIM    : 2101696973

Session 4
Introduction to Tree, Binary Tree and Expression Tree

Tree & Binary Tree:
- Konsep Tree 
- Konsep Binary Tree 
- Tipe-tipe Binary Tree 
- Properti Binary Tree 
- Representasi Binary Tree 
- Membuat Expresi Tree dari Prefix, Postfix dan Infix

Konsep Tree
Sebuah Tree adalah kumpulan dari satu atau lebih node.

- Note yang ada di paling atas dipanggil dengan Root
- Garis yang menyambungkan Node "Child" dengan Node "Parent" dipanggil          dengan Edge
- Node yang tidak memiliki anak dipanggil dengan Leaf Node
- Node yang memiliki "Parent" yang sama dipannggil dengan Sibling Node
- Degree node ialah total node anak yang ada di dalam Tree
- Height/Depth(Tinggi/Kedalaman) adalah Degree node maximal dalam            sebuah Tree
- Jika ada garis yang menghubungkan A ke B berarti B adalah                              Descendant(Keturunan) dari A dan A adalah Ancestor(Leluhur) dari B

Konsep Binary Tree
- Binary Tree adalah bentuk data structure pohon berakar dimana tiap Node        hanya memiliki anak paling banyak 2.
- Kedua anak tersebut dipanggil dengan Left Child(anak kiri) dan Right                Child(anak kanan).
- Node yang tidak memiliki anak dipanggil dengan Leaf.


Tipe-tipe Binary Tree
- Perfect Binary Tree
Perfect Binary Tree adalah tipe binary tree dimana tiap level memiliki              kedalaman(depth) yang sama.


- Complete Binary Tree
Complete Binary Tree adalah binary tree dimana pada tiap tingkat, kecuali        yang terakhir terisi penuh, dan semua Node sejauh mungkin terpisah. Binary Tree yang sempurna adalah Complete Binary Tree.


- Skewed Binary Tree
Skewed Binary Tree adalah bentuk binary tree dimana pada tiap node anak yang dimiliki paling banyak hanya satu.


- Balanced Binary Tree
Balanced Binary Tree adalah binary tree dimana tiada Leaf yang jauh dari Root daripada Leaf lainnya.


Properti Binary Tree
- Jumlah maximal node pada level k dari sebuah binary tree adalah 2^k.
- Jumlah maximal node pada binary tree dengan tinggi H adalah (2^(H+1))-1.
- Tinggi minimum dari sebuah binary tree dengan n Node adalah (2log(n)).
- Tinggi maximum dari sebuah binary tree dengan n Node adalah n-1.

Representasi Binary Tree

Representasi sebuah binary tree menggunakan Array dan Linked List
Membuat Expresi Tree dari Prefix, Postfix dan Infix

Prefix : F-B-A-D-C-E-G-I-H
Infix         : A-B-C-D-E-F-G-I-H
Postfix : A-C-E-D-B-H-I-G-F



Rifqi Amru Bakti-2101696973