Traversering

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

 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);

 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);

 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);