Pertemuan 4 - Introduction to Tree, Binary Tree and Expression Tree - 2101657966 - Vincent Wuliango

Tree Concept
Tree adalah kumpula dari 1 atau lebih node.


  • Node pertama atau teratas disebut root.
  • Garis yang terhubung antara induk ke anak lainnya disebut edge.
  • Node yang tidak mempunyai anak disebut leaf.
  • Node yang mempunyai induk yang sama disebut sibling.
  • Degree of node disebut total sub tree of node.
  • Height/Depth adalah max degree pada node di pohon.
  • Garis/busur yang menghubungkan p dan q, p disebut ancestor dari q ,dan q disebut descendant dari p.
Binary Tree Concept
Binary tree adalah struktur data pohon berakar yang dimana setiap node memiliki maksimal 2 anak.
 Type of Binary Tree
  • Perfect Binary Tree adalah pohon biner yang dimana setiap level berada pada kedalaman yang sama.
  • Complete Binary Tree adalah pohon biner yang dimana setiap level, kecuali yang terakhir ,sudah terisi semua, dan semua node sebelah kiri lebih panjang. Perfect binery tree sama dengan complete binary tree.
  • SKEWED Binary Tree adalah pohon biner yang dimana tiap node hanya mempunyai 1 anak, condong ke kanan atau condong ke kiri.
  • Balanced Binary Tree adalah pohon biner yang tidak ada leaf, jadi kedalamannya sejajar.

Property of Binary Tree
  • Max jumlah node pada k dari sebuah pohon biner adalah 2^k.
  • Max jumlah node pada panjang sebuah pohon biner h adalah 2^h+1-1.
  • Max panjang dari sebuah pohon biner n adalah 2log(n) atau n-1.
Representation of Binary Tree

  
Expression Tree Concept
   Contoh kodingan : 
*Untuk membuat tiap node di pohon
struct Node{
   char kata;
   struct Node *left;
   struct Node *right;
};

*Prefix dengan rekursif
char s = [maxn];
int p = 0;

void f(struct Node *curr){
  if(is_operator(s[p])){
  p++;curr->left = newnode(s[p]));
  f(curr->left);
  p++;curr->right = newnode(s[p]);
  f(curr->right);
}
}

Prefix Traversal
Progamnya simple.
 void prefix(struct Node *curr){
  printf("%c",curr->char);
  if(curr->left != 0) prefix(curr->left);
  if(curr->right != 0) prefix(curr->right);
}
Yang penting print dulu,baru diproses anak"nya.

Postfix Traversal
 void postfix(struct Node *curr){
  if(curr->left != 0) prefix(curr->left);
  if(curr->right != 0) prefix(curr->right);
  printf("%c",curr->char);
}
Proses anak"nya dulu,baru print.

Infix Traversal
Kita bisa koding seperti ini
 void postfix(struct Node *curr){
 if(curr->left != 0) prefix(curr->left);
 printf("%c",curr->char);
 if(curr->right != 0) prefix(curr->right);
} 

Create Exp-Tree From Postfix
kuncinya: scan dari kanan ke kiri.


Komentar

Posting Komentar