Diferențe pentru problema/pointeri între reviziile #2 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ă 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.
 
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.
 
|=. !problema/pointeri?pointeri01.png! |=. !problema/pointeri?pointeri02.png! |
|_=. Figura 1 |_=. Figura 2 |
 
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$];
* $rad$ este poziția rădăcinii arborelui.
 
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 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 |
h3. Explicație
h2. Cerință
...
!>problema/pointeri?pointeri01.png!
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$ ...
Fișierul de intrare $pointeri.in$ are formatul:
 
$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$ ...
În fișierul de ieșire $pointeri.out$ se vor tipări variabila $prim$ și vectorii $st$ și $dr$ care codifică lista, în formatul:
 
$prim$
$st[0] ... st[N - 1]$
$dr[0] ... dr[N - 1]$
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 200.000$;
* înălțimea arborelui nu va depăși 1.000 de noduri.
h2. Exemplu
table(example).
|_. pointeri.in |_. pointeri.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 8 1
-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
|
h3. Explicație
 
...
 
== include(page="template/taskfooter" task_id="pointeri") ==

Nu există diferențe între securitate.