Pertemuan 4-Introduction to Tree, Binary Tree and Expression Tree-2101655475-Daniel Yuan Markus

TREE

Pengertian
Tree adalah  kumpulan satu / beberapa node yang saling terhubung satu sama lain yang membentuk suatu kesatuan layaknya struktur sebuah pohon.

Contoh 

Degree of Tree = 3
Height = 3
Parent of  B = A
Children of B = D, E
Sibling of G = H
Ancestor of F = A, C
Descendant of F =  G,H


Penjelasan :
- Root = Node yang berada paling atas
- Edge = Garis penghubung dari Parent ke Children
- Leaf = Node yang tidak memiliki Children
- Sibling =  Node yang memiliki Parent yang sama
- Degree = Banyaknya suatu child (sub tree) dalam suatu node
- Height = Banyaknya tingkatan dalam suatu tree
-  Jika ada 1 garis yang terhubung dari p ke q, maka p adalah Ancestor dari q. Sedangkan q adalah Descendant dari p


BINARY TREE CONCEPT

Pengertian
Binary Tree adalah Tree yang memiliki syarat bahwa tiap node hanya boleh memiliki maksimal 2 children yaitu Left Child dan Right Child

Kelebihan struktur Binary Tree :
- Mudah dalam penyusunan algoritma sorting
- Searching data relatif cepat
- Fleksibel dalam penambahan dan penghapusan data

Contoh Gambar :

Jenis dari Binary Tree :

- Perfect Binary Tree =  Binary Tree dimana setiap tingkatan memiliki kedalaman yang sama. Tiap node (kecuali leaf) memiliki 2 child (panjang path sama).

- Complete Binary Tree =  Mirip dengan Perfect Binary Tree, tetapi tiap sub tree boleh memiliki panjang path yang berbeda

- Skewed Binary Tree = Binary Tree yang semua nodenya hanya memiliki 1 child (kecuali leaf)

Property Binary Tree

- Maksimum number of  nodes di level k dari Binary Tree adalah  2^k

- Maksimum number of nodes dari Height h di Binary Tree adalah  2^h+1 - 1

- Minimum Height dari node di Binary Tree adalah ²log(n)

- Maksimum Height dari node di Binary Tree adalah n-1

Representation of Binary Tree

1. Implementation using array

- Index pada Array mewakili node number

- Index 0 adalah Root Node

- Index Left Child adalah 2p + 1 (P adalah Parent)

- Index Right Chilrd adalah 2p+2

- Index 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

Contoh Soal

Prefix = */+5z-8^42

Postfix = 5z+8-/42^*

Infix =  [ (5+z)/8- ]* (4^2)

Struktur untuk tiap Node di Tree

struct tnode {                 char chr;                 struct tnode *left;                 struct tnode *right; };

Membuat Expression Tree dari Prefix

Main function Struct tnode *root = newnode (s[0]); f(root);

Prefix Transversal

void prefix(struct tnode *curr) {                printf( “%c “, curr->chr );                if ( curr->left  != 0 ) prefix(curr->left);                if ( curr->right != 0 ) prefix(curr->right); }

Postfix Transversal

void postfix(struct tnode *curr) {               if ( curr->left  != 0 ) postfix(curr->left);               if ( curr->right != 0 ) postfix(curr->right);                 printf( “%c“, curr->chr ); }

Infix Transversal

void infix(struct tnode *curr) {                 if ( curr->left  != 0 ) infix(curr->left);                 printf( “%c“, curr->chr );                 if ( curr->right != 0 ) infix(curr->right); }