Struktur Data - Python : Tree

Assalamu'alaikum sobat kodingers 😁, gimana nih kabar kalian? semoga dalam keadaan sehat dan selalu kuat ngoding yah 😂. Setelah lumayan lama tidak posting, kali ini kami kembali dengan postingan baru yang akkan membahas tentang "Tree" dalam struktur data. Kira-kira tree itu apa ya kok seperti pohon? 😂. Untuk lebih jelasnya yuk langsung saja kita simak 👂.

Tree

Pada postingan-postingan sebelumnya kita telah belajar mengenai menyimpanan data secara linear, seperti hasing, stack, queue dan linked list. Pada postingan kali ini kita akan mempelajari Tree yang memiliki cara penyimpanan data non-linear melainkan secara hierarki. Bagaimana maksudnya? Untuk mempermudahnya kita bayangkan saja susunan keluarga yang kita miliki. Jika diperhatikan dalam susunan tersebut kita akan menemukan siapa kakek kita, orang tua kita, saudara orang tua atau paman kita, sepepupu kita, saudara kita, atau bahkan cucu kita bukan? Begitulah kira - kira penggambarannya dari pengertian Tree penyimpanan data secara hierarki yang tersusun secara urut dari kakek hingga cucu. Berikut atribut - atribut yang terdapat dalam Tree :

1. Node: Serupa dengan simpul, node merupakan kerangka dasar dari sebuah tree (pohon), kadang disebut sebagai "key". Sebuah node dapat mengandung informasi tambahan (atau payload), meskipun informasi dalam node ini tidak wajib tetapi sangat penting dalam implementasi struktur data tree.
2. Edge: Garis penghubung antara dua buah node yang menunjukkan adanya relasi (hubungan) diantara kedua node. Setiap node (kecuali node root) terhubung dengan satu penguhubung yang menuju ke dalam node dan beberapa penghubung yang mengarah keluar dari node.
3. Root: Satu-datunya node dalam tree yang tidak memiliki garis penghubung (edge) yang mengarah ke dalam root, edge yang menghubungkan root semua mengarah ke luar dari node. (cikal-bakal)
4. Path: Jalur yang menghubungkan antara satu node dengan node yang lain, dapat dterdiri dari beberapa node dan edge yang berkesinambungan.
5. Children: Node yang terhubung dengan edge yang mengarah ke dalam node disebut children (selalu memiliki parent)
6. Parent: Node yang terhubung dengan edge yang mengarah keluar (memiliki anak).
7. Sibling: Node-node yang memiliki parent yang sama.
8. Subtree: Sekelompok node beserta turunnanya (anak-anaknya).
9. Sebuah node yang tidak memiliki children (anak)

Berikut implementasinya dalam bahasa pemrograman Python beserta penjelasannya pada beberapa baris : 

Output :

Dari output di atas dapat diartikan bahwa "a" bertindak sebagai parent/root, "b" merupakan anak kiri dan "c" merupakan anak kanan. Sebagai tambahan referensi, ada 3 metode penelurusan Tree yang dikenal dengan Tree Traversal yang akan kita bahas secara singkat saja. Yuk langsung saja ek tkp 😁.

Tree Traversal

Ada tiga pola umum yang digunkaan untuk mengunjungi semua node dalam tree. Perbedaan antara 3 pola ini adalah urutan kunjungan terhadap node. Kunjungan   ini dinamakan “traversal.”, yaitu preorder, inorder dan postorder. Berikut ini adalah definisinya :

• Preorder: Penelusuran node berawal dari ROOT, kemudian berlanjut ke turunan dari sebelah kiri, jika sedah jalur kiri sudah tidak ada anak lagi, diteruskan ke jalur turunan sebelah kanan, terus berlanjut sampai akhir node. Atau pertama menujuke node ROOT kemudian secara recursive mealkukan preorder pada subtree sebelah kiri, diikuti dengan traversal preorder secara recursive ke subtree sebelah kanan.
• Inorder: Melakukan traversal inorder secara recursive pada subtree sebelah kiri, menuju ke node ROOT, dan terakhir melakukan traversal inorder secara recursive pada subtree sebelah kanan.
• Postorder: Melakukan traversal postorder secara recursive pada subtree bagian kiri dan kanan diikuti dengan berkunjung ke node ROOT.

Implementasi algoritma ketiganya dalam Python seperti berikut :

Kira - kira seperti itulah materi yang bisa kami sampaikan hari ini 😁 mengenai Tree. Stay tuned pada postingan - postingan selanjutnya karena masih ada materi yang akan kami bagikan. Semoga bermanfaat, sampai jumpaaaa gaes 😁. Wassalamu'alaikum Wr. Wb.