Diferențe pentru problema/pointeri între reviziile #2 si #3

== include(page="template/taskheader" task_id="pointeri") ==

Un *arbore binar* este o structură de date în care fiecare element (numit *nod*) poate avea pointeri către două elemente: fiul stâng și fiul drept. Arborii sunt *aciclici*, adică un nod nu poate avea un pointer către un strămoș al lui. *Rădăcina* unui arbore este cel mai înalt nod, singurul care nu are părinte. Un *arbore binar de căutare* este un tip particular de arbore binar, în care nodurile conțin numere cu proprietatea că numărul dintr-un nod este mai mare sau egal cu orice număr din nodurile din subarborele stâng, dar mai mic sau egal cu orice număr din nodurile din subarborele drept. În Figura 1 este prezentat un astfel de arbore binar de căutare.
 
O *listă dublu înlănțuită corespunzătoare* unui arbore binar de căutare este o listă dublu înlănțuită care conține numerele din arbore ordonate crescător. În Figura 2 este prezentată lista dublu înlănțuită corespunzătoare arborelui din Figura 1.
 

|=. !problema/pointeri?pointeri01.png! |=. !problema/pointeri?pointeri02.png! |
|_=. Figura 1 |_=. Figura 2 |

 
O posibilă codificare a arborilor binari folosește trei vectori $(v, st, dr)$ și un număr [$intrare$], astfel:
 
* se scriu numerele din noduri în vectorul [$v$], într-o ordine oarecare;
* pentru numărul $v[i]$, se scriu în $st[i]$ și în $dr[i]$ pozițiile pe care apar fiul stâng, respectiv fiul drept al lui $v[i]$;
* dacă un nod nu are fiu stâng sau fiu drept, se scrie $-1$ pe poziția corespunzătoare din [$st$], respectiv [$dr$];
* $intrare$ este poziția rădăcinii arborelui.
 
În Figura 3 puteți vedea o posibilă codificare a arborelui din Figura 1. De exemplu, $st[7]$ = 6, adică numărul de pe poziția 6 (10) este fiu stâng al numărului de pe poziția 7 (14). De asemenea, $st[3]$ = -1, adică numărul de pe poziția 3 (12) nu are fiu stâng.
 
Similar putem codifica listele dublu înlănțuite, folosind vectorii $st$ și $dr$ pentru a reține poziția elementului anterior, respectiv următor. În Figura 4 puteți vedea o posibilă codificare a listei din Figura 2.
 

|=. !problema/pointeri?pointeri03.png! |=. !problema/pointeri?pointeri04.png! |
|_=. Figura 3 |_=. Figura 4 |

h3. Explicație

h2. Cerință

...
!>problema/pointeri?pointeri01.png!

Se dă o codificare a unui arbore binar cu $N$ noduri. Se cere să se tipărească o codificare a unei

h2. Date de intrare