travesering i et binært træ

Inorder er den traversering der udskriver data i rigtig rækkefølge, og dermed den vigtigste. De to andre henviser til om man udskriver før (pre) eller efter (post) man har undersøgt grenen... Det er ikke så nemt at forklare uden en tegning!!!

Et eksempel (pseudo-kode):

UdskrivPre:
  Udskriv r->navn;
  UdskrivPre (r->venstre) // kalder \'UdskrivPre\'
  UdskrivPre (r->højre)  // rekursivt
---
UdskrivIn:
  UdskrivIn (r->venstre)
  Udskriv r->navn;
  UdskrivIn (r->højre)
---
UdskrivPost:
  Udskriv (r->venstre)
  Udskriv (r->højre)
  Udskriv r->navn;

SORRY, UdskrivPost skal se sådan ud:

UdskrivPost
  UdskrivPost (r->venstre)
  UdskrivPost (r->højre)
  Udskriv r->navn;

Som du kan se, traverserer vi i Post-traversering igennem hele træet (da vi kalder UdskrivPost rekursivt), inden vi udskriver data.

I Pre-order-traversering udskriver vi data først, og traverserer derefter videre.

I In-Order-traversering går vi først SÅ DYBT NED TIL VENSTRE som muligt, og udskriver data. Herefter tester vi højre-siden

Har du styr på rekursion???
(ellers må det virke meget forvirende!)

Binære træer er altid sorteret, og kan derfor anvendes i den forbindelse.

Preorder giver altid ordnet ascending rækkefølge (stigende sortering)
Postorder giver altid ordnet descending rækkefølge (faldende sortering)

Inorder traverserer træet oppefra og ned. Det kan blandt andet bruges, hvis du vil gemme træet, og kunne oprette det igen senere. Hvis man har gemt pre- eller postorder, vil man når man læser data igen skabe et ubalanceret træ. Hvis man har gemt inorder, bliver træet præcis det samme.