Kita telah melihat di beberapa bagian sebelumnya bagaimana objek bisa dikaitkan satu sama lain menjadi list berantai. Ketika suatu objek memiliki 2 pointer ke objek dengan tipe yang sama, kita bisa membuat struktur data yang lebih kompleks dari list berantai. Dalam bagian ini kita akan melihat salah satu struktur dasar dan paling berguna: pohon biner (binary tree).
Setiap objek dalam pohon biner memiliki dua pointer, yang biasa disebut kiri dan kanan. Selain itu, tentunya simpul pada pohon memiliki data yang bisa bertipe apa saja. Misalnya, pohon biner integer bisa dibuat dalam bentuk :
class SimpulPohon { int item; // Data pada simpul ini SimpulPohon kiri; // Pointer ke cabang sebelah kiri SimpulPohon kanan; // Pointer ke cabang sebelah kanan }
Pointer kiri dan kanan dalam SimpulPohon bisa beriis null atau menunjuk pada objek lain dengan tipe SimpulPohon. Simpul yang menunjuk pada simul lain disebut induk (parent), sedangkan yang ditunjuk disebut anak (child). Dalam gambar di atas, simpul 3 adalah induk dari simpul 6, dan simpul 4 dan 5 adalah anak dari simpul 2.
Tidak semua struktur yang terdiri dari simpul pohon merupakan pohon biner. Pohon biner harus memiliki sifat :
- Harus ada satu simpul di dalam pohon yang tidak memiliki induk. Simpul ini disebut simpul akar (root).
- Simpul lain harus memiliki hanya satu induk
- Tidak boleh ada perulangan dalam pohon biner, artinya tidak boleh ada rantai pointer yang dimulai dari satu simpul dan berakhir di simpul yang sama.
Simpul yang tidak memiliki anak disebut simpul daun (leaf). Simpul daun dapat dikenali karena kedua pointer kiri dan kanannya berisi null. Dalam ilustrasi suatu pohon biner, biasanya simpul akar terletak di atas dan simpul daun terletak di bawah -- tidak sama seperti pohon sungguhan. Akan tetapi, kita bisa melihat cabang-cabang, seperti pohon, yang merupakan cikal bakal nama pohon biner ini.
Misalnya, mari kita lihat suatu simpul pada pohon biner. Lihat simpul tersebut beserta seluruh simpul turunannya (yaitu anak, anak dari anaknya, dan seterusnya). Simpul-simpul ini juga membentuk pohon biner, yang disebut pohon cabang (subtree) dari pohon awalnya. Misalnya, pada gambar di atas, simpul 2, 4, dan 5 membentuk pohon cabang. Pohon cabang ini disebut pohon cabang sebelah kiri dari simpul akarnya. Hal yang sama, simpul 3 dan 6 adalah pohon cabang sebelah kanan dari simpul akarnya. Salah satu atau kedua pohon cabang bisa kosong. Ini adalah definisi rekursif. Jadi tidak heran apabila kita menerapkan subrutin rekursif untuk mengolah struktur data pohon.
Mari kita lihat bagaimana caranya menghitung banyaknya simpul di dalam pohon biner. Sebagai latihan, kita mungkin bisa membuat algoritma untuk menghitung simpul. Inti permasalahannya adalah, bagaimana melacak simpul mana yang belum dihitung. Ini bukan hal sepele. Dan mungkin kita tidak mungkin menyelesaikannya tanpa menggunakan tumpukan atau antrian.
Dengan rekursi, algoritmanya akan jauh lebih mudah. Suatu pohon bisa kosong, atau bisa terdiri dari akar dan dua pohon cabang. Jika pohon kosong, maka banyaknya simpul adalah nol. (Ini merupakan kasus dasar dari rekursi). Kemudian kita bisa menggunakan rekursi untuk menghitung jumlah simpul pada masing-masing pohon cabang. Jumlahkan hasil dari kedua cabang, kemudian tambah satu simpul akarnya. Ini adalah jumlah simpul di dalam pohon.
Dalam Java bisa kita tuliskan sebagai :
static int hitungSimpul( SimpulPohon akar ) { // Hitung berapa simpul yang dimiliki suatu pohon // biner, termasuk akarnya if ( akar == null ) return 0; // Pohon kosong, tidak ada simpul di dalamnya else { int jumlah = 1; // Mulai dengan menghitung akarnya // Tambahkan dengan simpul dari pohon cabang sebelah kiri jumlah += hitungSimpul(akar.kiri); // Tambahkan dengan simpul dari pohon cabang sebelah kanan jumlah += hitungSimpul(akar.kanan); return hitung; // Kembalikan jumlahnya } } // akhir hitungSimpul()
static void preorderCetak( SimpulPohon akar ) { // Cetak semua item di dalam pohon yang ditunjuk oleh akar. // Item pada akar dicetak dahulu, kemudian item di sebelah kiri // dan baru item di pohon cabang sebelah kanan if ( akar != null ) { // (Jika null, kita tidak melakukan apa-apa.) System.out.print( akar.item + " " ); // Print item akar preorderCetak( akar.kiri ); // Print item di pohon cabang kiri preorderCetak( akar.kanan ); // Print items di pohon cabang kanan } } // akhir preorderCetak()
Rutin ini disebut "preorderCetak" karena ia menelusuri pohon secara preorder. Dalam penelusuran preorder, simpul akan diproses terlebih dahulu, kemudian pohon cabang sebelah kiri ditelusuri, dan kemudian cabang sebelah kanan. Dalam penelusuran postorder, cabang kiri ditelusuri, kemudian cabang kanan, baru kemudian simpul akar. Dan dalam penelusuran inorder, cabang kiri dikunjungi dahulu, kemudian akar, dan kemudian cabang kanan.
Subrutin yang mencetak postorder dan inorder berbeda dengan preorder dalam urutan pencetakannya di layar :
static void postorderCetak( SimpulPohon akar ) { // Cetak semua item di dalam pohon yang ditunjuk oleh akar. // Cabang pohon sebelah kiri dicetak dahulu, kemudian kanan, // dan baru simpul akarnya if ( akar != null ) { // (Jika null, kita tidak melakukan apa-apa.) postorderCetak( akar.kiri ); // Print item di pohon cabang kiri postorderCetak( akar.kanan ); // Print items di pohon cabang kanan System.out.print( akar.item + " " ); // Print item akar } } // akhir postorderCetak() static void inorderCetak( SimpulPohon akar ) { // Cetak semua item di dalam pohon yang ditunjuk oleh akar. // Cabang pohon cabang sebelah kiri dicetak dahulu, // kemudian simpul akarnya, baru pohon cabang sebelah kanan if ( akar != null ) { // (Jika null, kita tidak melakukan apa-apa.) inorderCetak( akar.kiri ); // Print item di pohon cabang kiri System.out.print( akar.item + " " ); // Print item akar inorderCetak( akar.kanan ); // Print items di pohon cabang kanan } } // akhir inorderCetak()
preorderCetak mencetak: 1 2 4 5 3 6 postorderCetak mencetak: 4 5 2 6 3 1 inorderCetak mencetak: 4 2 5 1 3 6
Tidak ada komentar:
Posting Komentar