Trætraversering

I modsætning til linkede lister, endimensionale arrays og andre lineære datastrukturer, som kanonisk gennemløbes i lineær rækkefølge, kan træer gennemløbes på flere måder. De kan gennemgås i dybde-først- eller bredde-først-orden. Der er tre almindelige måder at gennemløbe dem i dybdeførste rækkefølge på: i rækkefølge, forudgående rækkefølge og efterfølgende rækkefølge. Ud over disse grundlæggende gennemgange er forskellige mere komplekse eller hybride ordninger mulige, f.eks. dybdebegrænsede søgninger som f.eks. iterativ uddybende dybdeførste søgning. Sidstnævnte, såvel som breadth-first search, kan også bruges til at traverse uendelige træer, se nedenfor.

Datastrukturer til trætraverseringRediger

Traversering af et træ indebærer iterering over alle knuder på en eller anden måde. Da der fra en given knude er mere end én mulig næste knude (det er ikke en lineær datastruktur), skal nogle knuder, hvis man antager sekventiel beregning (ikke parallel), udskydes og lagres på en eller anden måde med henblik på senere besøg. Dette sker ofte ved hjælp af en stak (LIFO) eller en kø (FIFO). Da et træ er en selvreferentiel (rekursivt defineret) datastruktur, kan traversering defineres ved rekursion eller, mere subtilt, corecursion, på en meget naturlig og klar måde; i disse tilfælde lagres de udskudte knuder implicit i call stack.

Depth-first search kan let gennemføres via en stack, herunder rekursivt (via call stack), mens breadth-first search let gennemføres via en kø, herunder corecursivt.:45-61

Dybdeførstesøgning af binært træRediger

Dybdeførstetraversal (stiplet sti) af et binært træ:

• Pre-order (nodeadgang ved position rød ●):

  F, B, A, D, C, E, G, I, H;

• In-order (nodeadgang ved position grøn ●):

  A, B, C, D, D, E, F, G, H, I;

• Post-order (nodeadgang ved position blå ●):

  A, C, E, D, B, H, I, G, F.

Disse søgninger betegnes som dybdeførste søgning (DFS), da søgetræet uddybes så meget som muligt på hvert barn, før man går til den næste søskende. For et binært træ defineres de som adgangsoperationer på hver knude, startende med den aktuelle knude, hvis algoritme er som følger:

Det generelle rekursive mønster til at gennemløbe et binært træ er følgende:

1. Gå et niveau ned til det rekursive argument N. Hvis N eksisterer (er ikke-tomt), udføres følgende tre operationer i en bestemt rækkefølge: L: Recursivt gennemløber N’s venstre undertræ. R: Recursivt gennemløb af N’s højre undertræ. N: Adgang til (besøg) den aktuelle knude N selv.
2. Vend tilbage ved at gå et niveau op og ankomme til N’s overordnede knude.

Der er tre metoder (mønstre) for, ved hvilken position i parcourset (traversen) i forhold til knuden (i figuren: rød, grøn eller blå) besøget (adgangen) af knuden skal finde sted. Valget af præcis én farve bestemmer præcis ét besøg af et knudepunkt som beskrevet nedenfor. Adgang ved alle tre farver resulterer i et tredobbelt besøg af den samme knude, hvilket giver “all-order” sekventalisering:

F-B-A-A-A-A-A-B-D-C-C-C-C-C-D-D-E-E-E-E-E-D-B-B-F-F-G-G-G- I-H-H-H-H- I- I-G-F

Pre-order, NLREdit

1. Access the data part of the current node (i figuren: position red).
2. Forsøg i venstre undertræ ved rekursivt at kalde pre-order-funktionen.
3. Forsøg i højre undertræ ved rekursivt at kalde pre-order-funktionen.

Den forudgående traversal er topologisk sorteret, fordi en overordnet knude behandles, før en af dens underordnede knuder er færdigbehandlet.

In-order, LNREdit

1. Traverser det venstre undertræ ved rekursivt at kalde in-order-funktionen.
2. Access the data part of the current node (in the figure: position green).
3. Traverse the right subtree by recursively calling the in-order function.

I et binært søgetræ, der er ordnet således, at nøglen i hver knude er større end alle nøgler i venstre undertræ og mindre end alle nøgler i højre undertræ, henter in-order traversal nøglerne i opstigende sorteret rækkefølge.

Omvendt i rækkefølge, RNLEdit

1. Traverser det højre undertræ ved rekursivt at kalde funktionen omvendt i rækkefølge.
2. Access the data part of the current node.
3. Traverser det venstre undertræ ved rekursivt at kalde funktionen omvendt i rækkefølge.

I et binært søgetræ henter reverse in-order traversal nøglerne i faldende sorteret rækkefølge.

Post-order, LRNEdit

1. Traverse det venstre undertræ ved rekursivt at kalde post-order-funktionen.
2. Traverer det højre undertræ ved rekursivt at kalde postorder-funktionen.
3. Access the data part of the current node (in the figure: position blue).

Sporet af en traversal kaldes en sekventalisering af træet. Traversalsporet er en liste over hver enkelt besøgt knude. Ingen sekventalisering i henhold til før-, ind- eller efterorden beskriver det underliggende træ entydigt. For et træ med forskellige elementer er enten pre- eller post-order kombineret med in-order tilstrækkeligt til at beskrive træet entydigt. Imidlertid efterlader pre-order med post-order en vis tvetydighed i træstrukturen.

Generisk treeEdit

For at gennemgå et hvilket som helst træ med dybdeførste søgning skal du udføre følgende operationer ved hver enkelt knude:

1. Hvis knude ikke findes returneres.
2. Access (= besøg) node (pre-order position).
3. For each i from 1 to number_of_children – 1 do:
   1. Recursivt gennemløber i-th child.
   2. Access node (in-order position).
4. Rekursivt gennemløber sidste barn.
5. Access node (post-order position).

Afhængigt af det pågældende problem kan pre-order-, post-order- og især en af (number_of_children – 1) in-order-operationerne være ugyldige, eller der ønskes kun adgang til et bestemt barn, så disse operationer er valgfrie. I praksis kan der også være behov for mere end én af operationerne “pre-order”, “in-order” og “post-order”. Når der f.eks. indsættes i et ternært træ, udføres en før-ordningsoperation ved at sammenligne elementer. En post-order-operation kan være nødvendig bagefter for at afbalancere træet igen.

Breadth-first search, or level-orderEdit

Level-order: F, B, G, A, D, I, C, E, H.

Træer kan også gennemløbes i niveau-orden, hvor vi besøger alle knuder på et niveau, før vi går til et lavere niveau. Denne søgning kaldes breadth-first search (BFS), da søgetræet udvides så meget som muligt på hver dybde, før man går til den næste dybde.

Andre typerRediger

Der findes også trætraversal-algoritmer, der hverken klassificeres som depth-first search eller breadth-first search. En af disse algoritmer er Monte Carlo tree search, som koncentrerer sig om at analysere de mest lovende træk og baserer udvidelsen af søgetræet på en tilfældig prøveudtagning af søgeområdet.