Binary Tree

Syarat Binary Tree (Pohon Biner)

#  Setiap node hanya boleh memiliki maksimal 2 subtree, kedua subtree harus terpisah

#  Setiap node hanya boleh memiliki paling banyak 2 child

Jumlah maksimum node pada setiap tingkat = 2 ^{n - 1}

Jumlah maksimum node pada binary tree = 2 ⁿ - 1

n : tingkat

Contoh pada gambar disamping :
Jumlah maksimum node tingkat 1 = 2^{n - 1} = 2^{1 – 1} = 1

Jumlah maksimum node tingkat 2 = 2^{n - 1} = 2^{2 – 1} = 2

Jumlah maksimum node tingkat 3 = 2^{n - 1} = 2^{3 – 1} = 4

Jumlah maksimum node binary tree dengan 3 tingkat
= 2ⁿ – 1 = 2³ – 1 = 7

Operasi-operasi Tree

1. Insert

Menambah node ke dalam tree secara rekursif. Jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan. Jika data yang akan dimasukkan lebih kecil daripada elemen root, maka akan diletakkan di node sebelah kiri.

2. Find

Mencari node di dalam tree secara rekursif sampai node ditemukan. Syaratnya tree tidak boleh kosong.

3. Traverse

Kunjungan terhadap node-node dalam pohon dimana masing-masing node akan dikunjungi sekali.

4. Count

Menghitung jumlah node dalam tree.

5. Height

Mengetahui kedalaman sebuah tree.

6. Find Min dan Find Max

Mencari nilai terkecil dan terbesar pada tree.

7. Child

Mengetahui anak dari sebuah node (Jika punya).

Ilustrasi Insert

Soal 1
Buatlah sebuah pohon dari urutan node berikut :
8  9  11  15  19  20  21  7  3  2  1  5  6  4  13  14  10  12  17  16  18

Jenis Traverse (Kunjungan)
1. PreOrder
Cetak node yang dikunjungi, kunjungi left, kunjungi right.



















2. InOrder
Kunjungi left, cetak node yang dikunjungi, kunjungi right.

3. PostOrder
Kunjungi left, kunjungi riht, cetak node yang dikunjungi.

Contoh Implementasi :

\











Soal 2
Tentukan notasi prefix, infix, dan postfix dari ekspresi berikut :

Jawaban :
Prefix   : ^ - * + ABC - DE + FG
Infix     : ((A + B) * C - (D - E)) ^ (F + G)
Postfix : AB + C * DE - - FG + ^

Soal 3
Tentukan notasi prefix, infix, dan postfix dari ekspresi berikut :

Jawaban :

Prefix   : - ^ / - * 4 A B C D * / 1/2 ^ - E F 2
Infix     : ((((4 * A) - B) / (C * D)) ^ 1/2) - ((E - F) ^ 2)
Postfix : 4 A * B - C D * / 1/2 ^ E F - 2 ^ -

Soal 4 (UAS Struktur Data 2013/2014 Informatika UNDIP)
Diketahui A = 7, B = 4, C = 3, D = -2, E = 5
Hitung ekspresi prefix berikut :
a) * + A B - C D
b) / + * A B C - D E

Jawaban :
a) * + A B - C D = (A + B) * (C - D) = (7 + 4) * (3 - (-2)) = 55
b) / + * A B C - D E = ((A * B) + C) / (D - E) = ((7 * 4) + 3) / (-2 - 5) = -4,43


Metode Pencarian Node

1. Depth First Search (DFS)
Urutan pencarian : A-B-D-E-C-F-G

2. Breadth First Search (BFS)
Urutan pencarian : A-B-C-D-E-F-G




Penghapusan (Delete) Node
1. Jika yang di delete adalah leaf, maka bisa langsung di delete

2. Jika node yang di delete hanya memiliki satu anak, maka anak tersebut langsung menggantikan posisi parent-nya.

3. Jika yang di delete adalah node dengan 2 anak (subtree), maka node yang menggantikan node yang dihapus adalah :
#  Node yang akan dihapus adalah node (30), berada di sisi kiri.
#  Node yang ada di sisi kanan dari node yang akan dihapus adalah (40).
#  Telusuri sisi kiri, node (35).
    Sisi kiri (35) tidak ada (null), maka (35) menjadi induk dari (40).
#  Sisi kanan dari node (35) adalah (37), maka (37) menjadi sisi kiri dari node (40).
#  Sisi kanan dari node (40) adalah (45), posisinya tetap.

Penyajian Binary Tree Secara Berurutan