Skip navigation


Beberapa hari lalu gw mengumpulkan tugas kuliah Algoritma dan Pemrograman (yap, untuk S2). Salah satu bagian dari tugasnya adalah untuk memodelkan sebuah pohon n-er (n-ary tree).  Sebuah pohon n-er adalah seperti yang digambarkan di bawah.

N-ary tree

Berbeda dengan pohon biner yang setiap simpul memiliki paling banyak 2 simpul anak, maka sebuah simpul pada pohon di atas dapat memiliki simpul anak yang jumlahnya tidak tentu. Karena jumlah anaknya tidak dapat ditentukan maka representasi larik statis untuk mencatat setiap anak dari sebuah simpul bukan lah merupakan pilihan yang baik, apalagi menggunakan larik 2 dimensi yang berisi matriks ketetanggaan (yang jelas untuk masalah representasi pohon akan memakan banyak sekali ruang). Yang jelas pilihan yang cukup masuk akal adalah menggunakan senarai dinamis.

N-ary tree dengan list

Ilustrasinya dapat dilihat di gambar atas. Setiap simpul akan memiliki sebuah senarai yang akan mencatat simpul-simpul anak. Karena simpul-simpul anak dapat bertambah maka akan sangat nyaman menggunakan senarai.

Tapi karena tugasnya diwajibkan menggunakan C, gw merasa agak kecewa karena di saat publikasi tugas mata gw sudah berbinar-binar akan menggunakan fitur senarai generik pada STL. Dengan senarai generik tersebut gw tinggal membuat sebuah struktur simpul yang memiliki sebuah senarai simpul. Rasanya agak malas kalau harus mengkode senarai berkait lagi seperti yang dilakukan saat masih di tahun kedua kuliah sarjana. Apalagi Bu Inggriani Liem selalu berpesan bahwa seorang programmer harus selalu bisa menulis kode senarai kapanpun dibutuhkan. LOL.

Untungnya teman sekelompok sudah bersedia membuatkan representasi pohon. Tapi yang cukup menarik, representasi ini merupakan representasi senarai yang sudah sangat disederhanakan. Idenya sangat mirip dengan ide pohon biner.

Pohon biner

Pada pohon biner, sebuah simpul mempunyai dua buah simpul anak: anak kiri dan anak kanan. Representasi ini dimodifikasi sehingga dapat merepresentasikan pohon n-ary. Anak kiri akan dianggap sebagai simpul anak sedangkan anak kanan dapat dianggap sebagai simpul saudara. Pohon yang ada pada gambar paling atas akan direpresentasikan sebagai berikut.

Pohon n-ary dengan representasi biner

Jika diuraikan sebagai pohon biner maka akan terlihat seperti berikut.

Representasi pohon biner

Menarik juga🙂

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: