|=. !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 [$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.
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 elementului anterior și următor și o variabilă $prim$ pentru a reține poziția primului element. Î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 parțială a unui arbore binar cu $N$ noduri: vectorii [$st$], $dr$ și variabila [$intrare$]. 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ă.
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$
$N rad$
$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$ 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]$
