Binary Tre Gjennomsøkingen Metoder
Binære trær (BTS) er datastrukturer som brukes av programmerere som programvaren må representere middels til store datasett i en organisert, strukturert måte. En BT består av en forelder node med maksimalt to valgfrie barn noder: en venstre barn og en høyre barn. Programspesifikke datastrukturer som søke trær, hauger og uttrykk trær er rett og slett samlinger av individuelle BTs knyttet sammen til en kollektiv datasett. Det er tre forskjellige metoder for traversering BTs: forhåndsbestiller traversering, inorder traversering og Postorder traversering.
forhåndsbestilling Traversal
Forhåndsbestilling traversering besøk tre noder i denne sekvensen: ordnede, forlot barnet, høyre barn. Enkelte programmer i forhåndsbestilling traversering er evaluering av uttrykk i prefiks notasjon og behandlingen av abstrakte syntakstrær av kompilatorer. Følgende pseudokode demonstrerer den nøyaktige fremgangsmåten for en forhåndsbestilling traversering:
PROSEDYRE preorder (Binary_Tree_Node T)
BEGYNNE
ProcessNode (T)
Hvis (T venstre barnet er NOT NULL)
BEGYNNE
Preorder (T venstre barn)
SLUTT
Hvis (T rett barnet er NOT NULL)
BEGYNNE
Preorder (T rett barn)
SLUTT
SLUTT
inorder Traversal
Inorder traversering besøk tre noder i denne sekvensen: venstre barn, foreldre, høyre barn. Binære søketrær (en spesiell type BT) bruker inorder traversering å skrive ut alle sine data i alfanumerisk rekkefølge. Følgende pseudokode demonstrerer den nøyaktige fremgangsmåten for en inorder traversering:
PROSEDYRE Inorder (Binary_Tree_Node T)
BEGYNNE
Hvis (T venstre barnet er NOT NULL)
BEGYNNE
Inorder (T venstre barn)
SLUTT
ProcessNode (T)
Hvis (T rett barnet er NOT NULL)
BEGYNNE
Inorder (T rett barn)
SLUTT
SLUTT
Postorder Traversal
Postorder traversering besøk tre noder i denne sekvensen: venstre barn, høyre barn, foreldre. Et populært program for bruk av Postorder traversering er evaluering av uttrykk i postfix notasjon. Følgende pseudokode demonstrerer den nøyaktige fremgangsmåten for en Postorder traversering:
PROSEDYRE Postorder (Binary_Tree_Node T)
BEGYNNE
Hvis (T venstre barnet er NOT NULL)
BEGYNNE
Postorder (T venstre barn)
SLUTT
Hvis (T rett barnet er NOT NULL)
BEGYNNE
Postorder (T rett barn)
SLUTT
ProcessNode (T)
SLUTT