TREE

Tree adalah sebuah struktur data yang berbentuk seperti pohon yang terdiri dari serangkaian node yang saling berhubungan.

picture1

 

Root adalah node teratas dari sebuah tree.

Parent adalah node yang berada diatas node lain secara langsung. Root juga termasuk parent.

Child/anak adalah cabang langsung dari sebuah node.

Leaf/Daun adalah node terakhir yang tidak memiliki child.

Derajat adalah tingkatan dalam tree, dimulai dari level 0 untuk root dan level 1 untuk child dibawahnya dan seterusnya.

Height adalah banyaknya tingkatan dalam suatu tree.

Size adalah banyaknya node dalam suatu tree.

Ancestor adalah seluruh node yang terletak sebelum node tertentu pada jalur yang sama.

Descendant adalah seluruh node yang terletak setelah node tertentu pada jalur yang sama.

Sibling adalah node-node yang memiliki parent yang sama.

 

BINARY TREE

Binary Tree adalah tree yang mempunyai maksimal hanya dua anak dan harus terpisah.

tree_binary

Tipe-tipe Binary Tree:

  • Perfect Binary Tree : masing-masing node mempunyai dua anak.

41

  • Complete Binary Tree : mirip dengan Perfect, tetapi setiap subtree boleh memiliki panjang path yang berbeda.

42

  • Skewed Binary Tree : masing-masing node kecuali leaf hanya mempunyai satu anak.

43

  • Balance Binary Tree : jarak dari root ke leave dibagian kiri dan kanan sama.

 

PROPERTY OF BINARY TREE

Jumlah max node dari level k dari sebuah binary tree adalah 2k

Jumlah max node dengan height h dari sebuah binary tree adalah 2h+1-1

Height minimum dari sebuah binary tree dari n node adalah 2logn

Height maksimum dari sebuah binary tree dari n node adalah n-1

 

REPRESENTATION OF BINARY TREE

  1. ARRAY

Picture1

Index pada array mewakili jumlah node

Index 0 adalah Root

Index Left Child = 2p + 1, dimana p = parent index

Index Right Child = 2p + 2

Index Parent = (p-1)/2

 

  • LINKED LIST

Picture2

struct node {

int data;

struct node *left;

struct node *right;

struct node *parent;

};

struct node *root = NULL;

 

EXPRESSION TREE CONCEPT

Picture3

PREFIX : print L R

Atas ke bawah, dengan kiri prioritas

*

*+

*+a

*+ab

*+ab/

*+ab/-

*+ab/-c

*+ab/-cd

*+ab/-cde

 

POSTFIX : L R print

Kiri ke kanan, atas ke bawah

a

ab

ab+

ab+c

ab+cd

ab+cd-

ab+cd-e

ab+cd-e/

ab+cd-e/*

 

INFIX : L print R

Bawah ke atas, kiri ke kanan

(a

(a+

(a+b)

(a+b)*

(a+b)*((c

(a+b)*((c-

(a+b)*((c-d)

(a+b)*((c-d)/

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