Binus Preview

Data Structure (Conclusion)

Binary Tree

Tree –> Kumpulan satu atau lebih Node.

• Degree –> Tingkat Level Node pada suatu Tree. (Semakin kebawah semakin besar levelnya)
• Height –> Tinggi suatu Tree.
• Parent –> Orangtua dari suatu anak (Children), berada tepat di atas 1 atau 2 node.
• Children –> Anak yang terletak tepat di bawah orangtua (Parent).
• Sibling –> Saudara node dari orangtua (Parent) yang sama.
• Ancestor –> Semua node-node yang ada diatas node yang ditunjuk.
• Descendant –> Semua node-node yang ada dibawah node yang ditunjuk.
• Root –> Node teratas.
• Edge –> Garis yang menghubungkan Node yang satu dengan yang lain.
• Leaf –> Node terbawah / yang tidak mempunyai anak (Children).

Binary Tree –> Tree yang mempunyai paling banyak 2 anak.

Type of Binary Tree

• PERFECT Binary Tree

• COMPLETE Binary Tree

• SKEWED Binary Tree

• BALANCED Binary Tree

Rumus – Rumus Penting

• Jumlah Maksimum node pada level k dari Binary Tree = 2^k
• Jumlah Maksimum node dari Binary Tree pada height h = 2^(h+1) – 1
• Jumlah Minimum tinggi Binary Tree sebanyak n node = ^2log(n)
• Jumlah Maksimum tinggi Binary Tree sebanyak n node = n – 1

Representasi Binary Tree

• Implementasi dengan Linked List

struct node {
int data;
struct node *left;
struct node *right;
struct node *parent;
};
struct node *root = NULL;
         

Expression Tree

• Prefix   : *+ab/-cde
• Postfix : ab+cd-e/*
• Infix     : (a+b)*((c-d)/e)

• Prefix       : * + a b / – c d e
  Print from Left to Right, Top to Bottom, Left Priority.
• Postfix     : a b + c d – e / *
  Print from Left to Right, Bottom to Top.
  (Children 1) (Children 2) (Parent) Format
• Infix         : (a + b) * ((c – d) / e)
  Print from Left to Right, Bottom to Top.
  (Children 1) (Parent) (Children 2) Format