Blog untuk Tugas

Nama: Wilson Nursalim
NIM: 1901516495

Rangkuman Pertemuan 4

www.binus.ac.id
www.skyconnectiva.com

Tree adalah kumpulan dari nodes.

Saya akan menjelaskan Konsep Tree dengan gambar ini:

ROOT = Node yang terletak paling atas pada suatu Tree  (Root pada Tree di atas adalah F).
DEGREE = Jumlah anak yang dimiliki suatu node  (cth: Degree of D = 2, Degree of H =0)
HEIGHT = Jumlah node yang dilalui oleh suatu path dari Root menuju ke node paling dalam pada suatu Tree
(Height Tree di atas = 4).
LEAF = Node yang tidak memiliki anak. (A, C, E, & H adalah Leaf).
SIBLING = Nodes yang memiliki orangtua yang sama (C dan E adalah Sibling)
EDGE = Garis yang menghubungkan orangtua ke anaknya.

Binary tree = Suatu Tree yang tiap Node-nya hanya memiliki paling banyak 2 anak.

Tipe-tipe Binary Tree:

• Perfect Binary Tree 
  Binary Tree yang tiap node-nya memiliki tepat 2 anak dan semua leaf harus berada pada level yang sama.
  
• Complete Binary Tree
  Binary Tree yang tiap levelnya terisi penuh dengan node (kecuali mungkin level paling bawah) dan semua node memenuhi bagian kiri terlebih dahulu. Sebuah Perfect Binary Tree otomatis adalah Complete Binary Tree.
  
• Skewed Binary Tree
  Binary Tree yang tiap node-nya hanya memiliki paling banyak 1 anak.
  

1. Rumus untuk mencari jumlah node maksimal yang terletak pada suatu level = 2^k              (k = level)cth:        Jumlah node maksimal pada level ke-3 suatu binary tree adalah 8
   2^3 = 8
2. Rumus untuk mencari jumlah node maksimal yang bisa dimiliki suatu binary tree = 2^(h+1) – 1        (h=height)cth:        Binary tree dengan height 3, maksimal memiliki 15 node
   2^(3+1)-1   =  2^4-1
   =  16-1
   =  15

IMPLEMENTASI dengan Array:

IMPLEMENTASI dengan Linked List:

Binary Tree dapat digunakan untuk menyimpan notasi aritmetika (baik dalam bentuk prefix, infix, maupun postfix).

-> Pada Prefix, operator dicetak lebih dulu baru operand (parent dulu baru children)
-> Pada Postfix, operand dicetak lebih dulu baru operator (children dulu baru parent)