Fişierul intrare/ieşire:pointeri.in, pointeri.outSursăad-hoc
AutorDin FolclorAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.5 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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 1Figura 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 3Figura 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.inpointeri.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici