TREE
STRUCTURE (Struktur Pohon)
Dalam ilmu komputer, tree adalah sebuah struktur data yang
secara bentuk menyerupai sebuah pohon, yang terdiri dari serangkaian node
(simpul) yang saling berhubungan. Node-node tersebut dihubungkan oleh sebuah
vektor. Setiap node dapat memiliki 0 atau lebih node anak (child). Sebuah node
yang memiliki node anak disebut node induk (parent). Sebuah node anak hanya
memiliki satu node induk. Sesuai konvensi ilmu komputer, tree bertumbuh ke
bawah, tidak seperti pohon di dunia nyata yang tumbuh ke atas. Dengan demikian
node anak akan digambarkan berada di bawah node induknya.
Node yang berada di pangkal tree disebut node root (akar),
sedangkan node yang berada paling ujung pada piramida tree disebut node leaf
(daun).
Ilustrasi
Tree:
Binary Tree (Pohon Biner)
Dalam mata kuliah struktur
data, secara khusus akan dipelajari mengenai pohon biner. Pohon biner adalah
sebuah tree yang pada masing-masing simpulnya hanya dapat memiliki maksimum 2
(dua) simpul anak. Tidak boleh lebih. Pada pohon biner, umumnya kedua node anak
disebut dengan
posisinya,
yaitu kiri dan kanan.
Beberapa
istilah pada pohon biner:
•
Size (ukuran): jumlah total node yang terdapat pada pohon biner
tersebut.
• Depth
(kedalaman): panjang jalur yang menghubungkan sebuah node sampai ke node
anaknya yang paling ujung (leaf). Depth biasa juga disebut height.
Full Binary Tree (Pohon Biner Penuh) adalah pohon biner yang
setiap nodenya pasti memiliki 0 atau 2 node anak.
Perfect Binary Tree (Pohon Biner Sempurna) adalah pohon
biner yang semua node leafnya berada pada kedalaman yang sama dari node root.
Juga disebut sebagai Complete Binary Tree (Pohon Biner Lengkap)
Almost
Complete Binary Tree (Pohon Biner Hampir Lengkap) adalah pohon biner yang
setiap nodenya dapat memiliki 0 node anak, atau memiliki kiri, atau jika
memiliki kanan harus memiliki kiri. Tidak boleh memiliki kanan saja.
Ilustrasi
Binary Tree:
Implementasi
Implementasi
dalam pemrograman, dalam pokok bahasan ini akan dibicarakan untuk pohon biner
saja. Asumsi awal adalah data yang hendak dimasukkan ke dalam node, bertipe
data integer.
1. Deklarasi Tree
Karena tree tersusun oleh node-node, maka yang perlu kita
deklarasikan adalah komponen node itu sendiri. Dalam contoh dibawah, akan kita
namai Node.
Sebelumnya perlu kita lihat bahwa untuk mewujudkan implementasi
node ke dalam bahasa pemrograman, diperlukan sebuah struktur yang memiliki
susunan berikut ini:
Variabel data digunakan untuk menyimpan nilai angka node
tersebut, sedangkan kiri dan kanan, bertipe pointer, masing-masing mewakili
vektor yang akan menunjuk ke node anak kiri dan kanan.
2. Inisialisasi Tree
Untuk
pertama kali, saat kita akan membuat sebuah pohon biner, asumsi awal adalah
pohon itu belum bertumbuh, belum memiliki node sama sekali, sehingga masih
kosong. Oleh karena itu perlu kita tambahkan kode berikut pada baris awal
fungsi Main:
Kita mendeklarasikan sebuah pointer yang akan menunjuk ke
akar pohon yang kita buat, dengan nama *pohon.
Pointer ini ditujukan untuk menunjuk struktur bertipe Node, yang telah dibuat
pada bagian 1. Karena pohon tersebut sama sekali belum memiliki node, maka
pointer *pohon ditunjukkan ke NULL.
3. Menambahkan Node
Pada Tree
Karena pohon yang kita buat merupakan sebuah pohon biner,
maka untuk menambahkan sebuah node, secara otomatis penambahan tersebut
mengikuti aturan penambahan node pada pohon biner:
1.
Jika pohon kosong, maka node baru ditempatkan sebagai akar pohon.
2.
Jika pohon tidak kosong, maka dimulai dari node akar,
dilakukan proses pengecekan berikut:
a.
Jika nilai node baru lebih kecil
dari nilai node yang sedang dicek, maka lihat ke kiri node tersebut. Jika kiri
node tersebut kosong (belum memiliki kiri), maka node baru menjadi kiri node
yang sedang dicek. Seandainya kiri node sudah terisi, lakukan kembali
pengecekan a dan b terhadap node kiri tersebut. Pengecekan ini dilakukan
seterusnya hingga node baru dapat ditempatkan.
b.
Jika nilai node baru lebih besar
dari nilai node yang sedang dicek, maka lihat ke kanan node tersebut. Jika
kanan node tersebut kosong (belum memiliki kanan), maka node baru menjadi kanan
node yang sedang dicek. Seandainya kanan node sudah terisi, lakukan kembali pengecekan
a dan b terhadap node kanan tersebut. Pengecekan ini dilakukan seterusnya
hingga node baru dapat ditempatkan.
Proses
penambahan ini diimplementasikan secara rekursif pada fungsi berikut:
Variabel **root menunjukkan node mana yang sedang dicek saat
ini, untuk itu saat pemanggilan fungsi ini, variabel **root kita beri nilai
pointer yang menunjuk ke node akar, yaitu pohon.
Untuk
selengkapnya dapat dilihat pada bagian 5, kode program lengkap.
4. Membaca dan
Menampilkan Node Pada Tree
Untuk
membaca dan menampilkan seluruh node yang terdapat pada pohon biner, terdapat 3
macam cara, atau yang biasa disebut kunjungan (visit). Semua kunjungan diawali
dengan mengunjungi akar pohon. Karena proses kunjungan ini memerlukan
perulangan proses yang sama namun untuk depth (kedalaman) yang berbeda, maka
ketiganya diimplementasikan dengan fungsi rekursif.
a.
Kunjungan Pre-Order.
Kunjungan pre-order dilakukan mulai
dari akar pohon, dengan urutan:
1. Cetak isi (data) node yang
sedang dikunjungi
2. Kunjungi
kiri node tersebut,
- Jika kiri
bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut.
- Jika kiri
kosong (NULL), lanjut ke
langkah ketiga.
3. Kunjungi
kanan node tersebut,
• Jika
kanan bukan kosong (tidak NULL)
mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.
• Jika
kanan kosong (NULL),
proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang
dikunjungi sebelumnya.
b.
Kunjungan In-Order.
1. Kunjungi
kiri node tersebut,
-
Jika kiri bukan kosong (tidak NULL)
mulai lagi dari langkah pertama, terapkan untuk kiri tersebut.
- Jika kiri
kosong (NULL), lanjut ke
langkah kedua.
2. Cetak isi (data) node yang
sedang dikunjungi
3. Kunjungi
kanan node tersebut,
- Jika
kanan bukan kosong (tidak NULL)
mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.
-
Jika kanan kosong (NULL),
proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang
dikunjungi sebelumnya.
c.
Kunjungan Post-Order.
1. Kunjungi
kiri node tersebut,
• Jika
kiri bukan kosong (tidak NULL)
mulai lagi dari langkah pertama, terapkan untuk kiri tersebut.
•
Jika kiri kosong (NULL), lanjut ke
langkah kedua.
2. Kunjungi
kanan node tersebut,
• Jika
kanan bukan kosong (tidak NULL)
mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.
•
Jika kanan kosong (NULL), lanjut ke
langkah ketiga.
3. Cetak
isi (data) node yang sedang dikunjungi.
Proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang
dikunjungi sebelumnya.
Variabel **root
pada setiap fungsi diatas menunjukkan node mana yang sedang dikunjungi saat
ini, untuk itu saat pemanggilan, variabel **root
kita beri nilai pointer yang menunjuk ke node akar, yaitu pohon.
