Atenție! Aceasta este o versiune veche a paginii., scrisă la 2014-09-28 15:54:39.
Revizia anterioară   Revizia următoare  

Fișierul intrare/ieșire pointeri.in, pointeri.out Sursă ad-hoc
Autor din folclor Adăugată de avatar Catalin.Francu 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 stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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 ≤ 100.000;
  • 1 ≤ v[i] ≤ 1.000.000.000;
  • toate numerele din arbore sunt distincte;
  • î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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii