Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas metode traversal pohon yang disebut pre-order, di mana langkah pertamanya dimulai dari akar pohon dan dilanjutkan ke sub-tree. Proses pre-order traversal ini mengunjungi setiap node dalam urutan tertentu, yang kemudian dapat dijabarkan menjadi daftar urutan kunjungan node. Dengan contoh pohon berlabel A-P, penjelasan ini memandu cara menyusun daftar kunjungan node secara berurutan dari kiri ke kanan. Melalui proses ini, dapat dibangun kembali struktur pohon aslinya dari daftar urutan traversal yang telah disusun.

Ada lagi yang kita sebut traversalnya itu pre-order, jadi algoritmanya itu adalah langkah satunya kita ada di akar.

Nah kemudian berikutnya lagi adalah di situ si akar itu punya sub-tree ya, jadi punya anak yang nanti punya cucu dan seterusnya itu tree-nya kita sebut sebagai T1, T2 sampai Tn di sini.

Nah itu nanti akan di kunjungi dalam bentuk pre-order, jadi ordernya itu misalnya seperti ini.

Jadi kita punya pohon yang dikasih label A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P tergantung mulai dari akar terus level 1 dari kiri ke kanan, level 2 dari kiri ke kanan dan seterusnya.

Ini tidak menggunakan label dari orang tuanya ya, tapi kita ngurutnya dari kiri ke kanan.

Nah gimana kita mau menjabarkan ini menjadi kayak suatu daftar.

Jadi kita lihat di sini, pertama kita kunjungi A-nya, jadi kita taruh A di sini.

Yang berikutnya kita punya ada sub-pohon yang akarnya jadi B, kemudian C itu kebetulan tidak punya anak jadi dia sendiri, kemudian D yang punya anak cucu juga ya, jadi dia adalah sub-tree.

Nah setelah itu kita urut di sini ada A-B, kita ambil B, nanti yang berikutnya ada sub-tree-nya yang ini, jadi dipindah ke sini, terus F gitu ya, terus C.

Jadi dari B itu tidak langsung C tapi kita melihat ke anaknya dulu, anaknya dari B ya kalau ada anaknya.

Karena C tidak punya anak maka kita teruskan dengan D dan kemudian anaknya.

Di sini anaknya ada G-H-I yang punya sub-tree adalah G.

Langkah ini kita lanjutkan, jadi kita punya A-B-E, setelah E ini kita tidak langsung ke kanan tapi kita ambil anaknya dulu J-K.

Jadi di sini ada J-K, K-nya masih punya anak lagi, baru kita teruskan ke daftar yang sebelumnya F-C-D-G, kemudian dari G itu ke anaknya dulu ini L dan M, kemudian lanjut ke H-I.

Dan yang terakhir kita nanti akan dapat bentuk list seperti ini A-B-E-J-K-N-O-P-F-C-D-G-L-M-H-I.

Dari sini kita bisa melihat tree-nya, jadi kita lihat di sini kita punya A-B berarti A itu akar, B itu tidak mungkin akar lagi, jadi pasti anaknya si A.

Ini B, terus nanti ada E-J karena urutan alfabetnya itu tidak urut berarti si E-J itu adalah anaknya si B.

Terus nanti disitu ada E-J, kemudian ada K, ini bukan ke B, E itu anaknya J sama K, kemudian nanti baru ada N, disini anaknya dari K, karena bukan L berarti anaknya lagi, jadi ini N.

Terus ada N-O-P, setelah N-O-P ada F, F itu adalah urutan setelah E berarti itu adalah anaknya si B, setelah F ada C, C itu berarti setelah B itu berarti anaknya A.

Dan seterusnya nanti kita akan bisa mendapatkan graf aslinya dari urutan ini, karena kita punya prosedur namanya itu mulai dari kiri ke kanan, jadi kita bisa membangun kembali si pohonnya.