Atenție! Aceasta este o versiune veche a paginii., scrisă la 2014-09-28 13:59:33.
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ă elemente: fiul stâng și fiul drept. Rădăcina unui arbore este cel mai înalt nod, singurul care nu are părinte. Arborii sunt aciclici, adică de la rădăcină la orice nod există o cale unică. Dacă un nod nu are fiu stâng sau drept, pointerul corespunzător este nul. 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. În Figura 1 este prezentat un arbore binar de căutare.

O listă dublu înlănțuită corespunzătoare unui arbore binar de căutare este o listă dublu înlănțuită care conține numerele din arbore ordonate crescător. În Figura 2 este prezentată 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. Restul enunțului conține detalii tehnice.

|=.
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:

  • 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.

Î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.

|=.
Figura 3 Figura 4

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ă.

Date de intrare

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]

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:

intrare
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;

Exemplu

pointeri.in pointeri.out
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

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

Indicii de rezolvare

Arată 3 categorii