SIF42

P12 Binary Tree TIF42/SIF42

A. Sidiq P. Prodi teknik Informatika & Prodi Sistem Informasi

Fakultas Teknologi Informasi Universitas Mercu Buana Yogyakarta 1

Pembahasan • Struktur pohon biner • Operasi pohon biner • Aplikasi pohon biner

SQ - http://sidiq.mercubuana-yogya.ac.id - [email protected]

2

Operasi Pada Binary Tree • Menciptakan pohon biner kosong • Menyisipkan simpul • Menjelajahi pohon biner untuk mendapatkan isi keseluruhan • Mencari data pada sebuah simpul • Menghapus simpul


3

Membentuk BST • BST = Binary Search Tree • Ex : – Misal akan dimasukkan K,A,M,E,N,D,I,L dan U – Karakter yg pertama = akar pohon – Karakter berikutnya akan diletakkan pada posisi yg sesuai dengan melakukan satu atau beberapa pembanding Objek yg akan disisipkan < Nilai pada simpul sekarang • Ket : – Jika kondisi bernilai true = maka penyisipan akan dilakukan pada anak kiri – Jika kondisi bernilai false = penyisipan akan dilakukan pada anak kanan SQ - http://sidiq.mercubuana-yogya.ac.id - [email protected]

4

K

A

K

K A

E

M K A

K M

A

M E


5

N

D

K A

K M

E

I

A

N

M E

D

k A N

M E

D


N I

6

L

U

K A

M E

D

K

L I

A N

M E

D

L I


N U

7

• BST -> pohon biner yg terurutkan • Sifat : – setiap simpul memiliki nilai dan tidak ada simpul yg memiliki nilai yg sama – jika ada sub pohon kiri -> nilainya lebih kecil dari akarnya – jika ada sub pohon kanan -> nilainya lebih besar dari akarnya SQ - http://sidiq.mercubuana-yogya.ac.id - [email protected]

8

K A

M E

D Sub pohon kiri • semua nilai < dari nilai akar

L I

N U

Sub pohon kanan • semua nilai > dari nilai akar


9

• Step penyisipan nilai BST – cari posisi di pohon biner untuk menempatkan simpul – sisipkan simpul ke pohon biner Algoritma BST = Data -> Informasi yg akan disisipkan Step 1 : Jika Data < Akar.Data maka proses pada anak kiri Jika Data > Akar.Data maka proses pada anak kanan Step 2 : Ulangi step 2 sampai ditemukan sub pohon yg kosong yg memungkinkan diletakkan simpul baru yg berisi Data Step 3 : Selesai SQ - http://sidiq.mercubuana-yogya.ac.id - [email protected]

10

Contoh Program • • • •

Project Name : BinaryTree Header File Name = BT.h Other Class File Name = BT.cpp Main Class File Name = main.cpp


11

Header File (BT.h)


12

Other Class (BT.cpp)


13


14


15


16


17


18


19


20


21

Main Class (main.cpp)


22


23

Hasil


24

Evaluasi • Berdasarkan contoh program pada materi P13.


25

Soal • Modifikasilah Program tersebut, sehingga : – Data yang akan diInputkan (Ex : EsaRiskiAnanda) -> input keyboard (cin >>) – Data yang akan diDeletekan : (Ex : A, i, E) -> input keyboard (cin>>)

• Note : – Output harus menyertakan NIM dan Nama dibagian paling atas – Gunakan Nama Masing-masing SQ - http://sidiq.mercubuana-yogya.ac.id - [email protected]

26

Ketentuan • Tugas dikirim ke e-mail : • Subject : – TP13_SD21_NIM (Kelas 21) – TP13_SD22_NIM (Kelas 22)

• Ke : – [email protected] (21 & 22)

• Note : – Tugas dikumpul paling lambat tanggal 08 Januari 2015 SQ - http://sidiq.mercubuana-yogya.ac.id - [email protected]

27

Referensi • Munir. Rinaldi, “Algoritma & Pemrograman Dalam Bahasa Pascal dan C”, 2007, Bandung : Penerbit Informatika. • Utami, E., Raharjo, S., Sukrisno, "Struktur Data Konsep & Implementasinya Dalam Bahasa C & Free Pascal di GNU/Linux", 2007, Yogyakarta : Graha Ilmu. • Sianipar, R.H., Wiryajati, I.K., Mangiri, H.S., "Pemrograman & Struktur Data C", 2013, Bandung : Penerbit Informatika. • Hasbi, M., "Struktur Data dan Algoritma Dalam Pemrograman Turbo Pascal", 2003, Yogyakarta : Gava Media.


28


29

Thanks 4 Participating in My Class C U Next Time SQ - http://sidiq.mercubuana-yogya.ac.id - [email protected]

30

SIF42

Recommend Documents