DIKTAT KULIAH ALGORITMA dan STRUKTUR DATA II
T R E E
Pertemuan 13 Waktu
: 135 menit
Tujuan Pembelajaran
: Mahasiswa mampu menjelaskan teknik pemrograman
menggunakan Tree.
: Tree
Substansi Materi
Tabulasi Kegiatan Perkuliahan No 1 2
3
Tahap Kegiatan Pengajar Kegiatan Pendahuluan 1. Membuka pertemuan 2. Mengulang materi pertemuan sebelumnya Penyajian 1. Pengertian Tree Materi 2. Jenis Tree 3. Binary Tree 4. Contoh program 5. Contoh soal Tree Penutup 1. Menyimpulkan materi pertemuan 2. Memberikan tugas kecil 3. Menutup pertemuan
Kegiatan Mahasiswa Menyimak Bertanya
Media & Alat
Waktu
Papan Tulis
20 Menit
Menyimak Bertanya Menjawab Pertanyaan
Papan Tulis
80 Menit
Menyimak
Papan tulis
35 Menit
M A T E R I K U L I A H
TREE Sebelumnya kita sudah mengenal struktur data list, yang berupa obyek‐obyek yang saling terkait. Dalam list, satu obyek hanya terkait dengan satu obyek berikutnya melalui sebuah pointer. List dapat dikembangkan menjadi struktur data yang lebih kompleks, misalnya dengan menambah jumlah pointer dalam obyek. Misal dengan penambahan satu pointer lagi. Artinya bahwa jika masing‐masing obyek memiliki dua pointer, ada dua obyek lain yang ditunjuknya. Struktur yang demikian dikenal sebagai binary tree atau dikenal juga sebagai Tree Node. V3/2009‐2010 1
DIKTAT KULIAH ALGORITMA dan STRUKTUR DATA II
T R E E
Gambar 1. Ilustrasi Binary Tree Istilah‐istilah umum dalam Binary Tree : •
Predecessor : node yang berada di atas node tertentu
•
Successor
: node yang berada dibawah node tertentu
•
Ancestor
: seluruh node yang terletak sebelum node tertentu dan terletak pada
jalur yang sama •
Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama
•
Parent
: predecessor satu level diatas suatu node
•
Child
: successor satu level diatas suatu node
•
Subtree
: bagian dari tree yang berupa suatu node beserta descendantnya dan
memiliki semua karakteristik dari tree tersebut •
Size
•
Height
: Banyaknya tingkatan / level dalam suatu tree
•
Root
: Satu‐satunya node khusus dalam tree yang tak punya predecessor
•
Leaf
: Node‐node dalam tree yang tak memiliki successor
•
Degree
: Banyaknya child yang dimiliki suatu node
: Banyaknya node dalam suatu tree
V3/2009‐2010 2
DIKTA AT KULIAH ALLGORITMA d dan STRUKTU UR DATA II
T R E E
Contoh :
A
Subtree
B
D
C E
F
G
Jenisjen nis Tree 1. Binary Tree B B Binary Tree adalah treee dengan syarat bah hwa tiap no ode hanya boleh mem miliki m maksimal du ua subtree dan kedua subtree tersebut haru us terpisah. Sesuai dengan definisi terseebut, makaa tiap node dalam binaary tree haanya boleh memiliki paling banyak dua cchild. Jeenis‐jenis Biinary Tree :: •
Full B Binary Tree Binarry Tree yan ng tiap nod denya (kecu uali leaf) memiliki duaa child dan tiap subtree harus meempunyai p panjang path h yang samaa.
•
plete Binary y Tree Comp Mirip dengan Fu ull Binary Tree, T namun n tiap subtrree boleh memiliki m pan njang path y yang berbed da. Node kecuali leaf m memiliki 0 attau 2 child.
•
Skewed Binary T Tree Yaknii Binary Tree yang sem mua noden nya (kecualii leaf) hany ya memiliki satu child. V3/200 09‐2010 3
DIKTAT KULIAH ALGORITMA dan STRUKTUR DATA II
T R E E
Deklarasi Binary Tree
Type Tree = ^node;
Node = record
Isi : TipeData;
Left, Right : Tree;
End;
Operasi‐operasi pada Binary Tree •
Create
: Membuat binary tree baru yang masih kosong
•
Clear
: Mengosongkan binary tree yang sudah ada
•
Empty
: Function untuk memeriksa apakah binary tree masih kosong.
•
Insert
: Memasukan sebuah node ke dalam tree. Ada tiga pilihan
insert, yaitu ROOT, LEFT CHILD, atau RIGHT CHILD. Khusus insert sebagai ROOT, TREE harus dalam keadaan kosong. •
Find
: Mencari root, parent, left child, atau right child dari suatu
node. Tree tidak boleh dalam kedaan kosong. •
Update
: Mengubah isi dari node yang ditunjuk oleh pointer current.
Tree tidak boleh dalam keadaan kosong. •
Retrieve
: Mengetahui isi dari node yang ditunjuk oleh pointer kosong.
Tree tidak boleh dalam kedaan kosong. •
DeleteSub
: Menghapus sebuah subtree (node beserta seluruh
descendant‐nya) yang ditunjuk oleh current. Tree tidak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang telah di hapus. •
Characteristic: Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average dari length‐nya. Tree tidak boleh kosong.
V3/2009‐2010 4
DIKTAT KULIAH ALGORITMA dan STRUKTUR DATA II
T R E E
•
Traverse
: Mengunjungi seluruh node‐node pada tree, masing‐masing
sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Ada tiga cara traverse : Pre Order, In Order, dan Post Order. Langkah melakukan traverse : ¾ PreOrder
: cetak isi node yang dikunjungi, kunjungi Left Child,
kunjungi Right Child. ¾ InOrder
: Kunjungi Left Child, cetak isi node yang dikunjungi,
kunjungi Right Child. ¾ PostOrder
: Kunjungi Left Child, kunjungi Right Child, cetak isi
node yang dikunjungi.
V3/2009‐2010 5
