pohon biner · penelusuran pohon biner preorder untuk penelusuran preorder, urutannya adalah :...

Pohon Biner

Membaca Pohon

Membaca pohon biner dapat dilakukan dengan dua cara :

1. Membaca pohon biner level per level urut nomor simpul.

2. Membaca atau mencari sebuah simpul dengan nomor tertentu.

Membaca pohon biner level per level urut nomor simpul

Perhatikan Pohon biner berikut :


Pohon biner tersebut bila dibaca dan dicetak simpul persimpul, dengan pembacaan level per level urutnomor simpul, maka :

A B C D E F G H I J K L M N O P Q


Perhatikan Pohon biner berikut :


Pohon biner tersebut bila dibaca dan dicetaksimpul per simpul, dengan pembacaan levelper level urut nomor simpul, maka :

A B C D E G I J K N


• Perhatikan Pohon biner berikut :



A B C E F G J K M N



A B C E J K

Membaca atau mencari sebuah simpul dengan nomor tertentu

Contoh :

Jika ada sebuah pohon biner, jumlah simpul dan kedalaman pohon tidak diketahui.

Penelusuran Pohon Biner

Penelusuran (traverse atau traserval) pohonbiner, maksudnya membaca atau mengunjungi(visit) simpul – simpul pohon biner denganurutan tertentu. Ada tiga macam penelusuranyang apabila ditambah dengan kebalikannyamenjadi enam penelusuran sebagai berikut :


1. Preorder (atau depth – first order)

2. Inorder

3. Postorder

4. Inverse Preorder

5. Inverse Inorder

6. Inverse Postorder

Penelusuran Pohon Biner Preorder

Untuk penelusuran Preorder, urutannya adalah :ambil akar, kemudian telusuri secara preordersubpohon kiri, dan setelah selesaipenelusuran ke subpohon kiri, kemudiandilanjutkan dengan penelusuran secarapreorder ke subpohon kanan. Jadipenelusuran sendiri bersifat recursive.

Penelusuran Pohon

Agar mudah diingat, prosesnya ketiganya dapat disingkat sebagai berikut :

Untuk Preorder AKAR, KIRI, KANAN

Untuk Inorder KIRI, AKAR, KANAN

Untuk Postorder KIRI, KANAN, AKAR

Penelusuran Pohon Biner Preorder


Penelusuran Preorder A B C

Penelusuran Pohon Biner Inorder


Penelusuran Inorder B A C

Penelusuran Pohon Biner Postorder


Penelusuran Postorder B C A


• Buatlah penelusuran Preorder, Inorder, dan Postorder, dari pohon biner berikut.


Untuk Pre AKAR, KIRI, KANAN

Untuk In KIRI, AKAR, KANAN

Untuk Post KIRI, KANAN, AKAR

• Pre : A B D E C F

• In : D B E A F C

• Post : D E B F C A

Latihan Penelusuran1

1. Buatlah penelusuran Preorder, Inorder, dan Postorder, dari pohon biner berikut.

Jawab




• Pre : A B D H E J K C F M G

• In : H D B J E K A F M C G

• Post : H D J K E B M F G C A

Latihan Penelusuran2

1. Buatlah penelusuran Preorder, Inorder, dan Postorder, dari pohon biner berikut.

Jawab :




• Pre : A B D H E J K V W C F M G

• In : H D B J E V K W A F M C G

• Post : H D J V W K E B M F G C A

Pohon Pencarian – Biner (Binary Search Tree)

• Dari definisi pohon binary search terlihatbahwa pada setiap simpul, maka simpulcabang kiri (left) nilainya lebih kecil dari akar,sedangkan simpul cabang kanan (right)nilainya lebih besar atau sama dengan simpulakar.


• Sama dengan pohon pada umumnya, makasimpul pertama yang dibuat adalah simpulakar. Untuk data yang sama, maka bentukpohon binary search akan berbeda bila urutanpemasukan data berbeda.


Bila urutan data yang diinput :

60 44 75 20 55 66 84

75 60 84 44 66 20 55

44 20 60 55 75 66 84


a. Bila urutan data yang diinput :

60 44 75 20 55 66 84

Maka gambar Binary Search Tree – nya adalah

Hasil Penelusuran Inorder : 20 44 55 60 66 75 84


b. Bila urutan data yang diinput :

75 60 84 44 66 20 55




c. Bila urutan data yang diinput :

44 20 60 55 75 66 84




• Bila urutan data yang diinput :

60 44 75 66 20 55 84


Hasil penelusuran Inorder : 20 44 66 60 55 75 84

Penelusuran / Pencarian Biner

• Kekhususan Binary Search Tree (BST) adalah kalau ditelusuri secara inorder, maka hasilnya berupa nilai urut menaik (ascending).


• Penelusuran secara Inorder : 20 44 50 55 60


• Penelusuran secara Inorder : 20 44 50 52 55 58 60 66 75 80 84


• Penelusuran secara Inorder : 60 66 75 80 84 86 90 96


• Penelusuran secara Inorder : 60 75 84 90 96


• Binary Search Tree dibuat dengan tujuan agar dalam pencarian data, atau penelusuran dapat dilakukan pencarian secara biner.

• Pencarian atau penelusuran secara binermaksudnya seluruh data yang akan ditelusuri,dikelompokkan menjadi dua kelompok.Kemudian data dicari hanya pada salah satukelompok yang diperkirakan data tersebutada.

Menghapus sebuah simpul pada BST

Simpul sebuah pohon biner dapat dihapus.

Menghapus sebuah simpul memang dapatmembuat pohon tersebut tidak seimbang.

Terlepas dari kondisi tersebut, prosesmenghapus sebuah simpul dalam pohon bineradalah :


a. Apabila yang dihapus adalah simpul daun, takperlu dilakukan penyesuaian

b. Bila simpul yang dihapus mempunyai hanya satucabang, baik kiri maupun kanan, hanya anaksimpul tersebut diangkat keatas menggantikansimpul yang dihapus.

c. Bila simpul yang dihapus mempunyai cabang kiridan cabang kanan, maka simpul sucessor dalamurutan inorder yang akan menggantikan simpulyang dihapus.


• Perhatikan Pohon Biner berikut


• Bila simpul 50 yang dihapus tak perlupenyesuaian


• Bila simpul 75 yang dihapus perlu penyesuaian


• Simpul 80, yang menggantikan 75, karenasecara inorder, 80 adalah successor dari 75(sesudah 75 adalah 80)


• Bila simpul 60 yang dihapus.


• Simpul 71 yang akan menggantikan 60 karenasecara inorder, 71 adalah successor darisimpul 60


• Bila simpul 84 yang dihapus


• Simpul 90 yang akan menggantikan 84 karenasecara inorder, 90 adalah successor darisimpul 84

Ada Pertanyaan???

Tugas

Perhatikan Pohon Biner Berikut :

Tugas

1. Bacalah pohon biner tersebut simpul persimpul, dengan pembacaan level per levelurut nomor simpul.

2. Buatlah penelusuran Preorder, Inorder, danPostorder.

Jawab

1. Membaca Pohon Biner Secara Urut Level Per Level :

A B C D E F G H J K M V W

2. Penelusuran

a. Pre : A B D H E J K V W C F M G

b. In : H D B J E V K W A F M C G

c. Post : H D J V W K E B M F G C A

Tugas

Perhatikan Pohon binary search berikut :

Tugas

3. Buatlah penelusuran BST tersebut secara :

a. Preorder

b. Inorder

c. Post Order

Jawab

3. Buatlah penelusuran BST tersebut secara :

a. Preorder

66 54 50 62 55 84 75 95

b. Inorder

50 54 55 62 66 75 84 95

c. PostOrder

50 55 62 54 75 95 84 66

Tugas

Perhatikan Pohon binary search berikut :

Tugas

4. Berdasarkan BST tersebut, maka andadiminta untuk membuat BST penyesuaianjika :

a. Simpul 84 dihapus

b. Simpul 50 dihapus

c. Simpul 66 dihapus

Jawab

4. Menghapus simpul di BST

a. Hapus simpul 84

Jawab


b. Hapus simpul 50

Jawab


c. Hapus simpul 66

pohon biner · penelusuran pohon biner preorder untuk penelusuran preorder, urutannya adalah :...

Documents