Intro Tree , B

Tree Concept

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




Node yang teratas dipanggil dengan root
Garis yang tersambung dengan node yang dibawahnya disebut edge
Node yang tidak memiliki anak disebut leaf.
Node yang mempunyai parent dipanggil sibling.
Degree dari node adalah total dari sub tree node tersebut
Height/Depth adalah maximal degree dari node node dalam sebuah tree.
Jika ada garis yang menyambung p ke q , maka p dipanggil Ancestor dari q
, dan q adalah descendant dari p.

Binary Tree Concept
Binary Tree adalah tree data struktur yang di root dimana node hanya boleh memiliki 2 anak.

2 anak tersebut biasanya disebut anak kiri dan anak kanan.

Node yang tidak ada anak dipanggil leaf.

Leaves adalah node yang berisi 9 , 12 ,10 , dan 23.











Type of Binary Tree
PERFECT binary tree adalah binary tree yang masing-masing levelnya berada di depth yang sama.

COMPLETE binary tree adalah binary tree yang masing-masing level kecuali yang terakhir , terisi penuh dan semua node yang paling kiri. sebuah perfect binary tree adalah sebuah complete binary tree.

SKEWED binary tree adalah binary tree dimana masing-masing node ada memiliki paling banyak 1 anak.

BALANCED binary tree adalah binary tree yang tidak memiliki  leaf yang paling jauh dari root dengan leaf yang lain.

PERFECT Binary Tree

COMPLETE Binary Tree

sebuah perfect binary tree juga adalah sebuah complete binary tree.
SKEWED Binary Tree

Property of Binary Tree
Maximal node-node yng berada di level k pada binary tree 2k.

Maximal node dari binary tree pada height 3 

=1+2+4+8

=2⁰ + 2¹ + 2² + 2³

=2⁴-1

=15

Minimal height dari binary tree dari node n adalah ² log(n).

Maximal height dari binary tree dari node n adalah n - 1.

Skewed binary trees
memiliki height maximal

Representation of Binary Tree

Implementasi dengan menggunakan array

Index pada array menunjukan angka node

Index 0 adalah node Root

Indext Left Child adalah 2p + 1, dimana p adalah parent index

Index Right Child adalah 2p + 2

Index Parent is (p-1)/2

Implementasi dengan menggunakan linked list

struct node {

  int data;

  struct node *left;

  struct node *right;

  struct node *parent;

};

•

struct node *root = NULL;

Expression Tree Concept

Prefix : *+ab/-cde

Postfix : ab+cd-e/*

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

Kita akan menggunakan structure ini utk masing masing node di dalam tree:

struct tnode {

  char chr;

  struct tnode *left;

  struct tnode *right;
};

Ini adalah binary tree.

Create Expression Tree from Prefix

Kita bisa membuat sebuah expression tree dari sebuah prefix dengan cara recursive.

•

•

char s[MAXN];

int  p = 0;

void f(struct tnode *curr) {

  if ( is_operator(s[p]) ) {

  p++; curr->left  = newnode(s[p]);

  f(curr->left);

  p++; curr->right = newnode(s[p]);

  f(curr->right);

  }

main function

struct tnode *root = newnode(s[0]);

f(root);

Prefix Traversal

Membuat sebuah prefix atau postfix traversal didalam expression tree itu simple.

void prefix(struct tnode *curr) {

  printf( “%c “, curr->chr );

  if ( curr->left  != 0 ) prefix(curr->left);

  if ( curr->right != 0 ) prefix(curr->right);
}

Di perfix, kamu harus print/process sebelum child di proses.

Infix Traversal

Gimana dengan infix? Apakah kita bisa membuat seperti kode dibawah ini?

void infix(struct tnode *curr) {

  if ( curr->left  != 0 ) infix(curr->left);

  printf( “%c“, curr->chr );

  if ( curr->right != 0 ) infix(curr->right);
}

Itu kelihatan benar, tetapi infix memungkinkan operator precedence yang ambigu tanpa brackets.

Sebagai contoh * + a b c di prefix dalam bentuk code infix maka a + b * c dengan kode sebelumnya , sedangkan infix yang benar adalah (a + b) * c.

a + b * c : b dikalikan dengan c dan ditambah dengan a

(a + b) * c : a ditambah dengan b dan dikalikan dengan c

Prefix  : *+abc

Postfix  : ab+c*

Infix salah  : a+b*c

Infix benar : (a+b)*c

Untuk membenarkannya , maka kita bisa menambahkan brackets () saat menyatakan operator.

void infix(tnode *curr) {

  if ( is_operator(curr->chr) ) putchar( '(' );

  if ( curr->left != 0 ) infix(curr->left);

  printf( "%c", curr->chr );

  if ( curr->right != 0 ) infix(curr->right);

  if ( is_operator(curr->chr) ) putchar( ')' );

}

jadi * + a b c dalam prefix bisa di codingkan menjadi  ((a + b) * c)  dalam infix , yang benar.