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

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