Sa presupunem ca dorim sa
desenam un arbore binar pe o foaie de matematica (in care am numerotat liniile
de sus in jos si coloanele de la stânga la dreapta). Desenul trebuie sa
respecte urmatoarele reguli:
1. Nodurile situate pe acelasi nivel trebuie sa fie desenate pe aceeasi linie.
Nivelul radacinii arborelui este 1 si radacina va fi desenata pe linia 1. Fii
radacinii constituie nivelul 2 si vor fi desenati pe linia 2. Fiii fiilor radacinii
constituie nivelul 3 si vor fi desenati pe linia 3 etc.
2. Pe fiecare coloana poate fi desenat un singur nod.
3. Nodurile din subarborele stâng al unui nod trebuie sa fie desenate
în coloanele din stânga coloanei in care este desenat nodul respectiv,
iar nodurile din subarborele drept trebuie sa fie desenate în coloanele
din dreapta coloanei în care este desenat nodul respectiv.
4.Orice coloana cuprinsa intre coloana cea mai din stânga în care
este desenat un nod si coloana cea mai din dreapta în care este desenat
un nod trebuie sa contina un nod.
Sa notam cu L
cea mai din stanga coloana in care este desenat un nod si cu R
cea mai din dreapta coloana in care este desenat un nod. Latimea arborelui binar
este R-L+1.
De exemplu:
Observati ca latimea acestui
arbore binar este 19.
Putem calcula latimea pe fiecare nivel ca fiind diferenta dintre numarul celei
mai din dreapta coloane care contine un nod de pe nivelul respectiv si numarul
celei mai din stanga coloane care contine un nod de pe nivelul respectiv +1.
Arborele din exemplu are 6 niveluri, latimile nivelurilor fiind 1, 13, 18, 18,
13, 12.
Cand desenam un arbore binar dupa aceste reguli ne intereseaza si latimea nivelului
cu latime maxima si care este acest nivel. Daca exista mai multe niveluri cu
latimea maxima, ne intereseaza cel cu numarul cel mai mic.
In exemplul de mai sus latimea maxima a unui nivel este 18 si ea este atinsa
pe nivelurile 3 si 4, deci nivelul care ne intereseaza este 3.
Cerinta
Dat fiind un arbore binar,
scrieti un program care sa determine latimea maxima a unui nivel in arborele
desenat dupa regulile de mai sus si nivelul cu numarul cel mai mic care are
aceasta latime.
Date de intrare
Fisierul de intrare latime.in
contine pe prima linie un numar natural N
reprezentand numarul de noduri din arbore. Nodurile sunt numerotate de la 1
la N. Fiecare dintre urmatoarele
N linii contine cate 3 numere
întregi separate prin cate un spatiu x
s d cu semnificatia "fiul stang al nodului x
este s, iar fiul drept al nodului
x este d".
Daca un nod nu are fiu stang sau fiu drept atunci s,
respectiv d, pentru nodul respectiv
va avea valoarea -1. Radacina
arborelui este nodul 1.
Date de iesire
Fisierul de iesire latime.out
va contine o singura linie pe care se afla doua numere naturale separate printr-un
singur spatiu niv lat cu semnificatia
"cel mai mic nivelul de latime maxima este niv,
iar latimea lui este lat".
