Hoppa till innehållet

Traversering

Från Wikipedia

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.

Ett sorterat binärt träd.

  • 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

[redigera | redigera wikitext]
 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

[redigera | redigera wikitext]
 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

[redigera | redigera wikitext]
 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);