Traversal pada Binary Tree

Proses traversal adalah proses melakukan kunjungan pada setiap node pada suatu binary tree tepat satu kali. Dengan melakukan kunjungan secara lengkap, maka akan didapatkan urutan informasi secara linier yang tersimpan dalam sebuah binary tree. Terdapat tiga cara untuk melakukan kunjungan itu, yaitu:
1. Traversal preorder (depth first order)
Dilaksanakan dengan jalan mencetak isi node yang dikunjungi lalu melakukan kunjungan ke subtree kiri dan selanjutnya ke subtree kanan. Algoritma umum traversal preorder adalah sebagai berikut:
• Jika tree kosong, maka keluar.
• Proses node root.
• Traverse subtree kiri secara preorder.
• Traverse subtree kanan secara preorder.
2. Traversal inorder (symmetric order)
Dilaksanakan dengan jalan melakukan kunjungan ke subtree kiri, mencetak isi node yang dikunjungi, lalu melakukan kunjungan ke subtree kanan. Algoritma umum traversal inorder adalah sebagai berikut:
• Jika tree kosong, maka keluar.
• Traverse subtree kiri secara inorder.
• Proses node root.
• Traverse subtree kanan secara inorder.
3. Traversal postorder
Dilaksanakan dengan jalan melakukan kunjungan ke subtree kiri, lalu ke subtree kanan, dan selanjutnya mencetak isi node yang dikunjungi. Algoritma umum traversal inorder adalah sebagai berikut:
• Jika tree kosong, maka keluar.
• Traverse subtree kiri secara postorder.
• Traverse subtree kanan secara postorder.
• Proses node root.
Semua algoritma traversal (preorder, inorder, postorder) yang diberikan di atas berupa algoritma rekursif, dan sebenarnya dapat dikerjakan secara iteratif dengan bantuan stack. Contoh: diberikan ekspresi matematika ((A * B) - (C ^ D)) + (E / F), apabila digambarkan dalam bentuk binary tree
Apabila binary tree di atas dikunjungi:
• secara preorder akan menghasilkan: + - * A B ^ C D / E F
• secara inorder akan menghasilkan: A * C - C ^ D + E / F
• secara postorder akan menghasilkan: A B + C D ^ - E F / +