Pertemuan ke 5 - Tree and Binary Tree - 2101682242 - Mohammad Refardy

Sub Topics

Tree & Binary Tree:

-        Type of Binary Tree

-        Property of Binary Tree

-        Representation of Binary Tree

-        Threaded Binary Tree Concept

Binary Tree Concept

Contoh binary tree

dari 9 node, yang di-root

simpul yang berisi 18.

leaves adalah simpul yang mana

mengandung 9, 12, 10, dan 23

 

Type of Binary Tree

PERFECT binary tree adalah pohon biner di mana setiap tingkat berada pada kedalaman yang sama.

COMPLETE binary tree adalah pohon biner di mana setiap tingkat, kecuali mungkin yang terakhir, benar-benar terisi, dan semua node berada paling kiri mungkin. Pohon biner yang sempurna adalah pohon biner lengkap.

SKEWED binary tree adalah pohon biner di mana setiap simpul memiliki paling banyak satu anak.

BALANCED binary tree adalah pohon biner di mana tidak ada daun yang lebih jauh dari akar daripada daun lainnya (skema keseimbangan yang berbeda memungkinkan definisi yang berbeda dari "jauh lebih jauh").

SKEWED Binary tree:

COMPLETE Binary Tree:

Jadi sebenarnya perfect binary tree juga bias kita samakan dengan complete binary tree.

SKEWED Binary Tree:

BALANCED Binary tree:

Property of Binary Tree

Jumlah maksimum simpul pada tingkat k dari binary tree adalah 2k.

Dalam beberapa literatur, tingkat pohon biner dimulai dengan 1 (root).

Jumlah maksimum simpul pada binary tree tinggi h adalah

2 jam + 1 - 1.

Node maksimum dari binary tree tinggi 3

= 1 + 2 + 4 + 8

= 20 + 21 + 22 + 23

= 24 - 1

= 15

Representation of Binary Tree

•   Implementation using linked list

    

struct node {

               int data;

               struct node *left;

               struct node *right;

               struct node *parent;

};

struct node *root = NULL;

Threaded Binary Tree Concept

Sebuah pohon biner berulir sama seperti pohon biner tetapi dengan perbedaan dalam menyimpan pointer NULL.

Binary Tree:

Binary tree tanpa garis atau profil

Berhubungan dengan  perwakilan dari binary tree