Revizia anterioară Revizia următoare
| 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.15 sec | Limită de memorie | 2048 KB |
| Scorul tău | N/A | Dificultate |
   1.5
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
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ă elemente: fiul stâng și fiul drept. Arborii sunt aciclici, adică un nod nu poate avea un pointer către un strămoș al lui. Rădăcina unui arbore este cel mai înalt nod, singurul care nu are părinte. 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 sau egal cu orice număr din subarborele stâng, dar mai mic sau egal cu 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.
| Figura 1 | Figura 2 |
|---|
|=. 
O posibilă codificare a arborilor binari 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.
| Figura 3 | Figura 4 |
|---|
|=. 
Cerință
Se dă o codificare a unui arbore binar cu N noduri. Se cere să se tipărească codificarea listei dublu înlănțuite corespunzătoare
Date de intrare
Fișierul de intrare pointeri.in ...
Date de ieșire
În fișierul de ieșire pointeri.out ...
Restricții
- ... ≤ ... ≤ ...
Exemplu
| pointeri.in | pointeri.out |
|---|---|
| This is some text written on multiple lines. |
This is another text written on multiple lines. |
Explicație
...
