Tree Traversals
Dalam belajar struktur data, kita tentunya tidak asing dengan istilah tree atau pohon. Tree ini digunakan tujuannya untuk menunjukan struktur atau hirarki dari data-data. Sebenarnya ada banyak istilah yang terdapat dalam tree, yang paling utama ada root dan node. Node adalah sebutan untuk masing-masing elemen, sedangkan root dianggap sebagai kumpulan dari node-node, root ini yang berugas untuk mendefinisikan, sebagai sebuah titik utama.
Kali ini kita akan membahas tentang tree travelsals yang merupakan cara mengunjungi node pada binary tree. Cara ini biasa digunakan dalam Binary Search Tree (BTS). Ada 3 cara tree traversals, yaitu: in-order, pre-order, dan post-order. Berikut adalah cara penggunaannya:
- In-order : kiri, root, kanan
- Pre-order : root, kiri, kanan
- Post-order : kiri, kanan, root
Sebagai contoh, jika ada angka 15, 30, 27, 25, 29 maka akan menghasilkan binary tree:
Hasil yang akan muncul ketika diprint adalah:
- In-order
Kiri pertama adalah 25, naik ke root 27, ke kanan 29. Karena sudah tidak ada di kiri, baik ke root 15 dan kanan 30. Jadi akan muncul data : 25, 27, 29, 15, 30
- Pre-order : root, kiri, kanan
Root pertama 15, ke kiri 27, punya kiri lagi 25. Setelah itu ke kanan 29, ke kanan yang atasnya 30. Jadi akan muncul data : 15, 27, 25, 29, 30
- Post-order : kiri, kanan, root
Kiri pertama 25, kanan 29, rootnya 27 tapi juga jadi kiri, kanan 30 dan rootnya 15. Jadi akan muncul data : 25, 29, 27, 30, 15
Referensi :
https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
https://en.wikipedia.org/wiki/Reverse_Polish_notation
