Tree and Binary Tree - 2101713241 - Claudia Anita Magdalena

Binary Tree Concept

Binary Tree adalah tree yang mempunyai syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. Maka, tiap node dalam binary tree hanya boleh memiliki paling banyak dua anak/child.

Macam - macam binary tree:

- Perfect Binary Tree

Perfect Binary Tree adalah binary tree yang setiap levelnya berada pada depth yang sama.

- Complete Binary Tree

Complete Binary Tree adalah binary tree yang setiap levelnya (kecuali yang terakhir), sudah terisi semua.

- Skewed Binary Tree

Skewed Binary Tree adalah binary tree yang masing-masing node mempunyai anak yang paling banyak satu.

- Balanced Binary Tree

Node dalam Binary Tree
Jumlah maksimun node pada tiap tingkat adalah 2<sup>n

Node pada binary tree maksimunnya berjumlah</sup> 2ⁿ -1

Representasi dari Binary Tree

- Implementasi menggunakan array

Index pada array merepresentasikan nomor node.

Index ke-0 adalah akar node.

Index pada left child = 2p+1, dimana p merupakan index parent

Index pada right child = 2p+2

Index parent = (p-1)/2

- Implementasi menggunakan linked list

struct node{

      int data;

      struct node *left;

      struct node *right;

      struct node *parent;

};

struct node *root = NULL;