Diferențe pentru problema/pointeri între reviziile #8 si #9

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

Un *arbore binar* este o structură de date în care fiecare element (numit *nod*) conține un număr și pointeri către două elemente: fiul stâng și fiul drept. *Rădăcina* unui arbore este cel mai înalt nod, singurul care nu are părinte. Arborii sunt *aciclici*, adică de la rădăcină la orice nod există o cale unică. Dacă un nod nu are fiu stâng sau drept, pointerul corespunzător este nul. Un *arbore binar de căutare* este un tip particular de arbore binar, în care nodurile au proprietatea că numărul dintr-un nod este mai mare sau egal cu orice număr din subarborele stâng, dar mai mic sau egal cu orice număr din subarborele drept. În Figura 1 este prezentat un arbore binar de căutare.

Un *arbore binar* este o structură de date în care fiecare element (numit *nod*) conține un număr și pointeri către două elemente: fiul stâng și fiul drept. *Rădăcina* unui arbore este cel mai înalt nod, singurul care nu are părinte. Arborii sunt *aciclici*, adică de la rădăcină la orice nod există o cale unică. Dacă un nod nu are fiu stâng sau drept, pointerul corespunzător este nul. Un *arbore binar de căutare* este un tip particular de arbore binar, în care nodurile au proprietatea că numărul dintr-un nod este mai mare decât orice număr din subarborele stâng, dar mai mic decât orice număr din subarborele drept. În Figura 1 este prezentat un 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:

O posibilă codificare a unui arbore binar de căutare 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]$;

h2. Cerință

Se dă o codificare a unui arbore binar cu $N$ noduri. Se cere să se tipărească codificarea listei dublu înlănțuite corespunzătoare arborelui care are vectorul $v$ identic. Cu alte cuvinte, să se reorganizeze pointerii din $st$ și $dr$ astfel încât arborele să se transforme într-o listă dublu înlănțuită ordonată.

Se dă o codificare parțială a unui arbore binar cu $N$ noduri: vectorii [$st$], $dr$ și variabila [$intrare$]. Vectorul $v$ nu se dă. Se cere să se tipărească codificarea listei dublu înlănțuite corespunzătoare arborelui care are vectorul $v$ identic. Cu alte cuvinte, să se reorganizeze pointerii din $st$ și $dr$ astfel încât arborele să se transforme într-o listă dublu înlănțuită ordonată.

h2. Date de intrare