Introduction to Tree, Binary Tree, and Expression Tree - 2101654913 - Stanley Rangga Rawung

Pertemuan Keempat

Tanggal : Selasa, 20 Maret 2018

Tentang : Introduction to Tree, Binary Tree, and Expression Tree

Nama : Stanley Rangga Rawung

NIM : 2101654913

Tree Concept
Tree adalah salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarkis (hubungan one to many) antara element-elemen. Tree juga bisa didefinisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebut Root.

Contohnya :

Height = 3
Parent of C = A
Children of A = B, C
Sibling of D = E
Ancestor of J = F,C,A
Decendant of A = B,C,D,E,F,G,H,I,J,K,L





Terdapat beberapa penjelasan mengenai Tree :
1. Root : Node yang berada paling atas
2. Edge : Garis penghubung antara Parent dan Children
3. Leaf : Node paling akhir atau node yang tidak memiliki children
4. Sibling : Node yang mempunyai parent yang sama
5. Height : Jumlah tingkatan sebuah Tree
6. Ancestor : Semua Parent yang berkaitan dengan leaf tersebut (contohnya ancestor of D = B,A )
7. Descendant : Apapun yang berada di bawah sebuah parent ( contohnya descendant of C = F,G,J,K )


Binary Tree Concept
Binary Tree adalah sebuah tree yang memiliki children tidak lebih dari 2.

Jenis-Jenis Binary Tree :
1. Perfect Binary Tree : Binary Tree yang memiliki node sama banyak di setiap levelnya.

2. Complete Binary Tree : Binary Tree yang memiliki node sama banyak di setiap level kecuali level akhir, karena boleh tidak sama. Perfect binary tree juga bisa disebut complete binary tree.















3. Skewed Binary Tree : Binary tree yang semua node memiliki 1 child (kecuali leaf karena tidak ada child).











4. Balanced Binary Tree : Binary Tree yang jumlah node kiri dan node kanan sama. Perfect binary tree juga bisa termasuk dalam balanced binary tree.

Property of Binary Tree :
1. Maksimum node di level k dari sebuah binary tree adalah 2k
2. Maksimum node dalam sebuah binary tree dengan Height h adalah 2h+1 - 1.

3. Minimun Height sebuah binary tree dari n nodes adalah  2log(n).

4. Maksimum Height sebuah binary tree dari n nodes adalah n - 1.

Representation of Binary Tree :

1. Implementation using Array

- Indeks pada array menunjukan node

- Indeks 0 merupakan Root node

- Indeks left child adalah 2p+1 dimana p merupakan indeks parent

- Indeks right child adalah 2p + 2 dimana p merupakan indeks parent

- Indeks parent adalah (p-1)/2

2. Implementation using linked list

struct node {

  int data;

  struct node *left;

  struct node *right;

  struct node *parent;

};

struct node *root = NULL;

Expression Tree Concept

Expression Tree merupakan sebuah tree yang bisa digunakan untuk notasi aritmatika (Prefix,Postfix,Infix)

Contohnya :

Prefix : *+ab/-cde

Postfix : ab+cd-e/*

Infix : (a+b)*((c-d)/e)

Referensi :
-Reema Thareja,. 2014. Data structures using C. OXFOR. New Delhi. ISBN:978-0-19-8099307 Chapter 9 & 10
-Definisi Tree