Traversering är en operation som kan göras på datastrukturen träd.
Djupet-först traversering: Vid postordertraversering gås alla nodens barn igenom innan noden själv gås igenom. Vid preordertraversering gås noden själv igenom innan barnen gås igenom. Vid inordertraversering gås vänster delträd igenom därefter noden själv och slutligen det högra delträdet.
Om inordertraversering genomförs på ett sorterat träd, så besöks noderna i ordning.
Exempel
Preorder traversering ger sekvensen: F, B, A, D, C, E, G, I, H (rot, vänster, höger) Inorder traversering ger sekvensen: A, B, C, D, E, F, G, H, I (vänster, rot, höger); notera att denna sekvens blir ordnad Postorder traversering ger sekvensen: A, C, E, D, B, H, I, G, F (vänster, höger, rot) Bredden-först traversering ger sekvensen: F, B, G, A, D, I, C, E, H
Pseudokod för inordertraversering besök(nod N)
besök(vänster barn till N) operera på N besök(höger barn till N)
besök(trädets rot);
Pseudokod för preordertraversering besök(nod N)
operera på N besök(vänster barn till N) besök(höger barn till N)
besök(trädets rot);
Pseudokod för postordertraversering besök(nod N)
besök(vänster barn till N) besök(höger barn till N) operera på N
besök(trädets rot);
Kategori:Grafalgoritmer