Parcurgerea

 

Parcurgerea unui arbore binar poate fi realizată, la fel ca si parcurgerea grafurilor, în două feluri:

 

• BFS (breadth-first order) parcurgerea în lățime, la care, după vizitarea nodului inițial, se explorează toate nodurile adiacente lui, se trece apoi la primul nod vecin și se parcurg toate nodurile adiacente acestuia neparcurse încă și tot așa până se explorează tot arborele.

• DFS (depth-first order) parcugerea în adâncime, care începe cu un nod inițial, denumit nod de start. Se vizitează mai intâi nodul de start. Se vizitează apoi primul vecin nevizitat al nodului de start. Nodul y este considerat vecin al nodului x dacă există muchia [x,y]. Se vizitează în continuare primul vecin nevizitat al primului vecin al nodului de start, și așa mai departe, mergând în adâncime până când ajungem într-un nod care nu mai are vecini nevizitați. Când ajungem într-un astfel de nod, revenim la nodul său parinte (nodul din care acest nod a fost vizitat). Dacă acest nod nu mai are vecini nevizitați, alegem primul vecin nevizitat al său și continuăm parcurgerea în același mod. Dacă nici acest nod nu mai are vecini nevizitați, revenim în nodul său părinte și continuăm în același mod, până când toate nodurile accesibile din nodul de start sunt vizitate.