

	Sintetizand,trebuie sa rezolvam urmatoarea problema: Se dau nodurile unui arbore binar in
preordine si in inordine. Se cere sa listam perechile de noduri care sunt legate printr-o ramura
directa precum si numarul acestora. Evident, pt. a putea realiza acest lucru, trebuie sa recons-
tituim efectiv arborele. Pt. aceasta, putem folosi o procedura recursiva, care reconstituie arbo-
rele plecand de la reprezentarea lui in preordine.
	Probelma este ca trebuie considerate drept noduri si terminatiile unui nod care nu are fii
(precum si terminatia unui nod cu un singur fiu). Pt. orice astfel de nod terminal. trebuie sa con-
sideram ca mai are doi fii speciali, care sunt nuli (marcati in program cu'#'). Evident, un nod
care are un singur descendent, va avea un fiu nul (acesta putand fi in stanga sau in dreapta).
Programul citeste nodurile in preordine si inordine (in vectorii preord si inord) si apoi constru-
ieste vectorul preord2, care contine varfurile arborelui luate in preordine (inclusiv terminatiile
nule).
	Construirea vectorului preord2 se face tinand cont de urmatoarele situatii:
-> fiecare nod:
	- are un descendent in stanga	sau
	- are un descendent in dreapta	sau
	- are doi descendenti		sau
	- nu are nici un descendent (este nod terminal).

	Cum decidem in care situatie se gaseste un nod dat? Un nod i are un descendent in stanga
daca exista un nod j care apare in preordine dupa nodul i, iar in inordine inaintea lui i. Ase-
manator, un nod i are un descendent in dreapta daca exista un nod j care apare in preordine dupa
nodul i, iar in inordine apare tot dupa i, cu conditia suplimentara ca in inordine intre i si j
sa nu apara un nod care sa fie anterior lui i in in preordine. 