Î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.
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.
|=. !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
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ă.
h2. Date de intrare
Fișierul de intrare $pointeri.in$ ...
Fișierul de intrare $pointeri.in$ are formatul:
$N intrare$
$v[0] ... v[N - 1]$
$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 $intrare$ și vectorii $st$ și $dr$ care codifică lista, în formatul:
$intrare$
$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;
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
8 5 2 12 15 3 10 14
-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") ==
