Struktur Data & Algoritma - Penjelajahan Pohon

Traversal adalah proses untuk mengunjungi semua node dari pohon dan dapat mencetak nilainya juga. Sebab, semua node terhubung melalui edge (tautan) kami selalu memulai dari node root (kepala). Artinya, kita tidak dapat mengakses node di pohon secara acak. Ada tiga cara yang kami gunakan untuk melintasi pohon -

• In-order Traversal
• Praorder Traversal
• Traversal pasca pesanan

Umumnya, kita melintasi pohon untuk mencari atau menemukan item atau kunci tertentu di pohon atau untuk mencetak semua nilai yang dikandungnya.

In-order Traversal

Dalam metode traversal ini, sub-pohon kiri dikunjungi terlebih dahulu, kemudian akar dan kemudian sub-pohon kanan. Kita harus selalu ingat bahwa setiap node dapat mewakili subpohon itu sendiri.

Jika pohon biner dilintasi in-order, keluarannya akan menghasilkan nilai kunci yang diurutkan dalam urutan menaik.

Kami mulai dari A, dan mengikuti traversal berurutan, kita pindah ke subtree kirinya B. Bjuga dilintasi secara berurutan. Proses ini berlangsung hingga semua node dikunjungi. Output dari inorder traversal pohon ini adalah -

D → B → E → A → F → C → G

Algoritma

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

Praorder Traversal

Dalam metode traversal ini, simpul akar dikunjungi terlebih dahulu, kemudian subpohon kiri dan terakhir subpohon kanan.

Kami mulai dari A, dan mengikuti traversal pre-order, kami mengunjungi pertama A sendiri dan kemudian pindah ke subtree kirinya B. Bjuga akan dilintasi praorder. Proses ini berlangsung hingga semua node dikunjungi. Output dari traversal pre-order pohon ini adalah -

A → B → D → E → C → F → G

Algoritma

Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

Traversal pasca pesanan

Dalam metode traversal ini, simpul akar dikunjungi terakhir, karena itulah namanya. Pertama kita melintasi subtree kiri, lalu subtree kanan dan akhirnya simpul root.

Kami mulai dari A, dan mengikuti Post-order traversal, pertama-tama kita mengunjungi subtree kiri B. Bjuga dilintasi pasca pemesanan. Proses ini berlangsung hingga semua node dikunjungi. Output traversal post-order dari pohon ini adalah -

D → E → B → F → G → C → A

Algoritma

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

Untuk memeriksa implementasi C dari penjelajahan pohon, silakan klik di sini .