Diferențe pentru problema/pointeri între reviziile #7 si #19

Nu există diferențe între titluri.

Diferențe între conținut:

== 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ă 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. În Figura 2 este prezentată 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. Restul enunțului conține detalii tehnice.
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.
|=. !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 [$rad$], 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.
* $rad$ 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.
Figura 3 arată o posibilă codificare a arborelui din Figura 1. De exemplu, $st[7]$ = 6, adică numărul de pe poziția 7 (14) are ca fiu stâng numărul de pe poziția 6 (10). 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. Remarcați că vectorul $v$ este identic în Figurile 3 și 4.
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.
|=. !problema/pointeri?pointeri03.png! |=. !problema/pointeri?pointeri04.png! |
|_=. Figura 3 |_=. Figura 4 |
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 dau valorile pentru [$st$], $dr$ și $rad$ dintr-o codificare a unui arbore binar cu $N$ noduri. 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
Fișierul de intrare $pointeri.in$ are formatul:
$N intrare$
$v[0] ... v[N - 1]$
$N rad$
$st[0] ... st[N - 1]$
$dr[0] ... dr[N - 1]$
h2. Date de ieșire
În fișierul de ieșire $pointeri.out$ se vor tipări variabila $intrare$ și vectorii $st$ și $dr$ care codifică lista, în formatul:
În fișierul de ieșire $pointeri.out$ se vor tipări variabila $prim$ și vectorii $st$ și $dr$ care codifică lista, în formatul:
$intrare$
$prim$
$st[0] ... st[N - 1]$
$dr[0] ... dr[N - 1]$
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).
|_. pointeri.in |_. pointeri.out |
| 8 1
 8  5  2 12 15  3 10 14
-1  2 -1 -1 -1 -1  0  6
-1  7  5 -1 -1 -1  3  4
-1 2 -1 -1 -1 -1 0 6
-1 7 5 -1 -1 -1 3 4
| 2
1  5 -1  6  7  2  0  3
6  0  5  7 -1  1  3  4
1 5 -1 6 7 2 0 3
6 0 5 7 -1 1 3 4
|
== include(page="template/taskfooter" task_id="pointeri") ==

Nu există diferențe între securitate.