Fișierul intrare/ieșire | pointeri.in, pointeri.out | Sursă | ad-hoc |
---|---|---|---|
Autor | din folclor | Adăugată de | Cătălin Frâncu • Catalin.Francu |
Timp de execuție pe test | 0.5 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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.
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.
Figura 3 | Figura 4 |
---|
Cerință
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ă.
Date de intrare
Fișierul de intrare pointeri.in are formatul:
N rad
st[0] ... st[N – 1]
dr[0] ... dr[N – 1]
Date de ieșire
Î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]
Restricții
- 1 ≤ N ≤ 200.000;
- înălțimea arborelui nu va depăși 1.000 de noduri.
Exemplu
pointeri.in | pointeri.out |
---|---|
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 |