Arbori

Probleme propuse

Considerăm arbori binari (nu neapărat compleți) cu același tip de date în fiecare nod.

1. Scrieți o funcție care construiește lista nodurilor unui astfel de arbore, traversat în a) preordine; b) inordine; c) postordine.
Pentru eficiență, folosiți o funcție ajutătoare care concatenează lista nodurilor unui arbore (în ordinea indicată) la o listă dată.

2. Scrieți o funcție care afișează un arbore în a) preordine; b) inordine; c) postordine, câte un nod pe linie, precedând fiecare nod cu numărul lui de ordine (începând de la 1).
Scrieți o funcție ajutătoare cu un parametru suplimentar care indică ultimul numâr de ordine consumat înainte de traversarea arborelui, și având ca rezultat ultimul număr de ordine consumat după traversarea arborelui.

3. Scrieți o funcție care afișează un arbore în a) preordine; b) inordine, câte un rând pe linie, precedând fiecare nod cu un numâr de spații egal cu dublul adâncimii la care se află (câte două spații pentru fiecare nivel).

4. Un arbore cu valori diferite în fiecare nod poate fi reconstruit în mod unic cunoscând lista nodurilor sale în inordine și preordine. Reconstruirea se poate face recursiv, observând că rădăcina (primul nod din lista în preordine) împarte lista în inordine în listele pentru subarborele stâng și cel drept. Listele corespondente în preordine pot fi identificate după lungime.
De exemplu, avănd:

inordine: [1; 7; 5; 6; 11; 2; 8; 4; 9]
preordine: [2; 7; 1; 6; 5; 11; 8; 9; 4]
rădăcina e 2, și am redus problema la cei doi subarbori: inordine [1; 7; 5; 6; 11] cu preordine [7; 1; 6; 5; 11] (următoarele 5 noduri), și inordine [8; 4; 9] cu preordine [8; 9; 4].
Scrieți o funcție care construiește arborele, fiind date cele două liste.


Marius Minea
Last modified: Sat Dec 14 17:30:00 EET 2013