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

== 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.

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. 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. 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.

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.

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 |

* 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.

Î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.

h2. Cerință

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

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

h2. Date de intrare