Thursday 8 January 2015
POHON
1 ISTILAH-ISTILAH DASARSecara sederhana pohon bisa didefinisikan sebagai kumpulan elemen yang salah satu elemennya disebut akar (root), dan sisa elemen yang lain (disebut simpul) terpecah menjadi sejumlah himpunan yang saling tidak berhubungan satu sama lain, yang disebut dengan subpohon (subtree), atau juga disebut dengan cabang.
Beberapa istilah dalam pohon :
- • Tingkat (level) suatu simpul ditentukan dengan pertama kali menentukan akar sebagai bertingkat 1. Jika suatu simpul dinyatakan sebagai tingkat N, maka simpul-simpul yang merupakan anaknya dikatakan berada dalam tingkat N + 1.
- • Derajat (degree) suatu simpul dinyatakan sebagai banyaknya anak atau turunan dari simpul tersebut. Simpul yang berderajat nol disebut dengan daun (leaf).
- • Tinggi (height) atau kedalaman (depth) dari suatu pohon adalah tingkat maksimum dari dari suatu simpul dalam pohon tersebut dikurangi dengan 1.
- • Ancestor suatu simpul adalah semua simpul yang terletak dalam satu jalur dengan simpul tersebut dari akar sampai simpul yang ditinjau.
- • Hutan (forest) adalah kumpulan sejumlah pohon yang tidak saling berhubungan.
Ada beberapa cara untuk menggambarkan bentuk pohon :
=> 1. Dengan cara simpul
=> 2. Diagram Venn
=> 3. Notasi Kurung :
( A ( B ( D, E ( I, J ) ), C (F, G, H ) ) )
=> 4. Notasi Bertingkat
2 POHON BINER
Pohon biner (binary tree) bisa didefinisikan sebagai suatu kumpulan simpul yang mungkin kosong atau mempunyai akar dan dua subpohon yang saling terpisah yang disebut dengan subpohon kiri (left subtree), dan subpohon kanan (right subtree). Subpohon juga disebut dengan cabang.
Istilah-istilah dalam pohon biner :
• Full Binary Tree : Semua node (kecuali daun) pasti memiliki 2 anak dan setiap subtree memiliki panjang jalur (path) yang sama.
• Complete Binary Tree : Mirip dengan full binary tree, tapi tiap subtree boleh memiliki panjang path yang berbeda, tiap node (kecuali daun) memiliki 2 anak.
• Skewed Binary Tree : binary tree yang semua nodenya (kecuali daun) hanya memiliki 1 anak .
3 KUNJUNGAN PADA POHON BINER
Atas sebuah pohon biner bisa dilakukan sejumlah operasi. Salah satu operasi yang paling sering dilakukan adalah melakukan kunjungan pada setiap simpul pada suatu pohon biner tepat satu kali (binary tree traversal). Kunjungan dapat dilakukan dengan tiga cara, yaitu kunjungan secara preorder, inorder, dan postorder. Selain itu berdasarkan kedudukan setiap simpul dalam pohon juga bisa dilakukan kunjungan secara levelorder.
Kunjungan pada pohon biner, secara singkat bisa dijelaskan sebagai berikut :
1. Kunjungan Preorder (depth first order), menggunakan urutan :
• Cetak isi simpul yang dikunjungi
• Kunjungi cabang kiri
• Kunjungi cabang kanan
2. Kunjungan Inorder (symetric order), menggunakan urutan :
• Kunjungi cabang kiri
• Cetak isi simpul yang dikunjungi
• Kunjungi cabang kanan
3. Kunjungan Postorder, menggunakan urutan :
• Kunjungi cabang kiri
• Kunjungi cabang kanan
• Cetak isi simpul yang dikunjungi
4 MENGUBAH POHON MENJADI POHON BINER
Untuk mengubah struktur pohon secara umum menjadi struktur pohon biner, dapat dilakukan dengan langkah-langkah sebagai berikut :
1. Tentukan pohon yang akan diubah menjadi pohon biner.
2. Simpul-simpul yang mempunyai tingkat yang sama saling dihubungkan satu sama lain, dan cabang pohon digambarkan pada tingkat yang lebih tinggi.
3. Ambil sembarang simpul, simpul yang terletak tepat dibawahnya akan dipasang sebagai cabang kiri, dan simpul yang tepat disebelah kanannya akan dipasang sebagai cabang kanan.
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment