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