În comparație cu listele legate, array-urile unidimensionale și alte structuri de date liniare, care sunt traversate în mod canonic în ordine liniară, arborii pot fi traversați în mai multe moduri. Ei pot fi parcurși în ordine profundă sau amplă. Există trei moduri obișnuite de parcurgere în ordine „depth-first”: in-order, pre-order și post-order. Dincolo de aceste parcurgeri de bază, sunt posibile diverse scheme mai complexe sau hibride, cum ar fi căutările limitate în profunzime, cum ar fi căutarea iterativă în profunzime întâi. Aceasta din urmă, la fel ca și căutarea de tip breadth-first, poate fi utilizată și pentru a parcurge arbori infinit, a se vedea mai jos.
Structuri de date pentru parcurgerea arborilorEdit
Prin parcurgerea unui arbore implică iterarea peste toate nodurile într-un anumit mod. Deoarece de la un nod dat există mai mult de un nod următor posibil (nu este o structură de date liniară), atunci, presupunând un calcul secvențial (nu paralel), unele noduri trebuie să fie amânate-stocate într-un fel pentru a fi vizitate ulterior. Acest lucru se face adesea prin intermediul unei stive (LIFO) sau a unei cozi (FIFO). Deoarece un arbore este o structură de date autoreferențială (definită recursiv), parcurgerea poate fi definită prin recursivitate sau, mai subtil, prin corecursivitate, într-un mod foarte natural și clar; în aceste cazuri, nodurile amânate sunt stocate implicit în stiva de apeluri.
Cercetarea în profunzime este ușor de implementat prin intermediul unei stive, inclusiv recursiv (prin intermediul stivei de apeluri), în timp ce căutarea în amplitudine este ușor de implementat prin intermediul unei cozi, inclusiv corecursiv.:45-61
Căutarea în profunzime a arborelui binarEdit
- Pre-ordonare (accesarea nodului la poziția roșu ●):
F, B, A, D, C, E, G, I, H;
- In-order (accesarea nodului la poziția verde ●):
A, B, C, D, E, F, G, H, I;
- Post-order (accesarea nodului la poziția albastru ●):
A, C, E, D, B, B, H, I, G, F.
Aceste căutări sunt denumite căutare în profunzime (DFS), deoarece arborele de căutare este adâncit cât mai mult posibil pe fiecare copil înainte de a trece la următorul frate. Pentru un arbore binar, acestea sunt definite ca operații de acces la fiecare nod, începând cu nodul curent, al căror algoritm este următorul:
Patronul general recursiv pentru parcurgerea unui arbore binar este următorul:
- Descindeți un nivel până la argumentul recursiv N. Dacă N există (nu este gol) executați următoarele trei operații într-o anumită ordine: L: Parcurge recurent subarborele stâng al lui N. R: parcurge recurent subarborele drept al lui N. N: accesează (vizitează) nodul curent N în sine.
- Întoarceți urcând un nivel și ajungând la nodul părinte al lui N.
Există trei metode (modele) în ce poziție a parcursului (parcurgerii) în raport cu nodul (în figură: roșu, verde sau albastru) va avea loc vizita (accesul) nodului. Alegerea unei singure culori determină exact o singură vizită a unui nod, după cum este descris mai jos. Accesul la toate cele trei culori are ca rezultat o triplă vizită a aceluiași nod care produce secvențializarea „all-order”:
F-B-A-A-A-A-B-D-C-C-C-C-C-D-E-E-E-D-B-F-G-G- I-H-H-H- I- I-G-F
Pre-order, NLREdit
- Accesează partea de date a nodului curent (în figură: poziția roșie).
- Traversează subarborele stâng prin apelarea recursivă a funcției de preordonare.
- Traversează subarborele drept prin apelarea recursivă a funcției de preordonare.
Traversarea prin preordonare este una ordonată topologic, deoarece un nod părinte este procesat înainte de a fi procesat oricare dintre nodurile sale copil.
In-order, LNREdit
- Traversează subarborele din stânga prin apelarea recursivă a funcției in-order.
- Accesați partea de date a nodului curent (în figură: poziția verde).
- Traversează subarborele din dreapta prin apelarea recursivă a funcției in-order.
Într-un arbore de căutare binar ordonat astfel încât, în fiecare nod, cheia este mai mare decât toate cheile din subarborele său stâng și mai mică decât toate cheile din subarborele său drept, parcurgerea în ordine recuperează cheile în ordine crescătoare.
Inversare în ordine, RNLEdit
- Traversează subarborele drept prin apelarea recursivă a funcției de inversare în ordine.
- Accesează partea de date a nodului curent.
- Traversează subarborele stâng prin apelarea recursivă a funcției de inversare în ordine.
Într-un arbore binar de căutare, traversarea inversă în ordine inversă recuperează cheile în ordine descrescătoare.
Post-order, LRNEdit
- Traversează subarborele stâng prin apelarea recursivă a funcției post-order.
- Traversează subarborele din dreapta prin apelarea recursivă a funcției post-order.
- Accesează partea de date a nodului curent (în figură: poziția albastră).
Traseul unei traversări se numește o secvențializare a arborelui. Urma traversării este o listă a fiecărui nod vizitat. Nicio secvențializare în funcție de pre-, in- sau post-ordonare nu descrie în mod unic arborele subiacent. Având în vedere un arbore cu elemente distincte, fie preordinea, fie postordinea asociată cu ordinea în ordine este suficientă pentru a descrie arborele în mod unic. Cu toate acestea, pre-ordonarea cu post-ordonarea lasă o oarecare ambiguitate în structura arborelui.
Generic treeEdit
Pentru a parcurge orice arbore cu căutare în profunzime, efectuați următoarele operații la fiecare nod:
- Dacă nodul nu este prezent se întoarce.
- Accesați (= vizitați) nodul (poziția de preordine).
- Pentru fiecare i de la 1 la numărul_de_copii – 1 faceți:
- Recursiv parcurge al i-lea copil.
- Accesați nodul (poziția în ordine).
- Recursiv parcurge ultimul copil.
- Accesați nodul (poziția după ordine).
În funcție de problema în cauză, operațiile pre-order, post-order și, în special, una dintre operațiile in-order (number_of_children – 1) pot fi nule, sau se dorește accesul doar la un anumit copil, astfel încât aceste operații sunt opționale. De asemenea, în practică, pot fi necesare mai multe operații de pre-order, in-order și post-order. De exemplu, la inserarea într-un arbore ternar, se efectuează o operație de preordonare prin compararea elementelor. O operație de post-ordonare poate fi necesară ulterior pentru a reechilibra arborele.
Breadth-first search, or level orderEdit
Arborii pot fi parcurși, de asemenea, în ordine de nivel, unde vizităm fiecare nod de pe un nivel înainte de a merge la un nivel inferior. Această căutare se numește breadth-first search (BFS), deoarece arborele de căutare este lărgit cât mai mult posibil pe fiecare adâncime înainte de a merge la următoarea adâncime.
Alte tipuriEdit
Există și algoritmi de parcurgere a arborilor care nu se clasifică nici ca deep-first search, nici ca breadth-first search. Un astfel de algoritm este căutarea arborelui Monte Carlo, care se concentrează pe analiza celor mai promițătoare mișcări, bazând expansiunea arborelui de căutare pe eșantionarea aleatorie a spațiului de căutare.
.