Rabu, 14 Desember 2011

Pohon Biner (Struktur Data Berantai-Java)


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()
Juga, mari kita lihat bagaimana mencetak isi item di dalam pohon biner. Jika pohon kosong, kita tidak melakukan apa-apa. Jika pohon tidak kosong, maka mungkin ia berisi akar dan dua pohon cabangnya. Cetak item pada akarnya, dan gunakan rekursi untuk mencetak item di dalam pohon cabangnya. Berikut ini adalah subrutin untuk mencetak semua item dalam satu baris cetakan.
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()
Subrutin ini bisa dijalankan pada pohon biner yang diilustrasikan di awal bagian ini. Urutan item ketika dicetak akan berbeda, di mana :
preorderCetak mencetak:   1  2  4  5  3  6
 
postorderCetak mencetak:  4  5  2  6  3  1
 
inorderCetak mencetak:    4  2  5  1  3  6
Dalam preorderCetak misalnya, itam pada akar pohon, yaitu 1, dicetak paling awal. Akan tetapi urutan preorder juga dilakukan untuk setiap pohon cabangnya. Simpul akar pada pohon cabang sebelah kiri, yaitu 2, dicetak terlebih dahulu sebelum pohon cabangnya 4 dan 5. Sedangkan untuk cabang sebelah kanan, akarnya 3 akan dicetak sebelum 6. Penelusuran preorder dilakukan pada semua cabang pohon. Urutan penelusuran yang lainnya bisa dianalisis dengan cara yang sama.

Tidak ada komentar:

Posting Komentar