Diferențe pentru problema/pointeri între reviziile #17 si #20

== 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ă noduri: 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. Figura 1 arată 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ă noduri: fiul stâng și fiul drept. Dacă un nod nu are fiu stâng sau drept, pointerul corespunzător este nul. *Rădăcina* unui arbore este cel mai înalt nod, singurul care nu are părinte. De la rădăcină la orice nod există o cale unică. 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. Figura 1 arată 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. Figura 2 arată lista dublu înlănțuită corespunzătoare arborelui din Figura 1.

Un arbore binar de căutare are o *listă dublu înlănțuită* corespunzătoare, care conține numerele din arbore ordonate crescător. Figura 2 arată lista dublu înlănțuită corespunzătoare arborelui din Figura 1.

Problema cere, în esență, să transformați un arbore binar de căutare într-o listă liniară simplu înlănțuită, folosind exclusiv manipularea pointerilor.

|=. <!-- Textile ține morțiș să fie un caption aici. -->

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

Similar putem codifica listele dublu înlănțuite, folosind vectorii $st$ și $dr$ pentru a reține poziția nodului anterior și următor și o variabilă $prim$ pentru a reține poziția primului nod. Figura 4 arată o posibilă codificare a listei din Figura 2. Remarcați că vectorul $v$ este identic în Figurile 3 și 4.

|=. <!-- Textile ține morțiș să fie un caption aici. -->

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

h2. Restricții

* $1 ≤ N ≤ 100.000$;
* $1 ≤ v[i] ≤ 1.000.000.000$;
* toate numerele din arbore sunt distincte;

* $1 ≤ N ≤ 200.000$;

* înălțimea arborelui nu va depăși 1.000 de noduri.
h2. Exemplu

table(example).

table(example).

|_. pointeri.in |_. pointeri.out |
| 8 1
-1 2 -1 -1 -1 -1 0 6