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].
5. Un arbore (cu valori numerice în noduri) este un heap dacă e vid sau dacă 1) nodul rădăcină are valoare mai mare sau egală cu oricare din cei doi fii (dacă există)
si (2) subarborii săi au și ei aceeași proprietate.
a) scrieți o funcție care determină dacă un arbore e un heap
b) transformați un arbore în heap: Transformați întâi cei doi subarbori, apoi schimbați rădăcina cu copilul de valoare maximă (dacă aceasta e mai mare), și la nevoie re-transformați subarborele a cărui rădăcină s-a schimbat.
6. Scrieți o funcție care returnează al k-lea nod în inordine dintr-un arbore (numărând de la zero). Prelucrați subarborele stâng. Dacă are prea puține noduri, returnați printr-o excepție (declarați exception Too_large of int) al câtelea nod trebuie căutat în restul arborelui, și returnați, după caz rădăcina sau rezultatul căutării în arborele drept.
7. Adaptați citirea de s-expresii de la curs pentru a construi un arbore corespunzător unei expresii cu operatori aritmetici și operanzi care sunt fie numere fie identificatori, și evaluați apoi expresia parcurgând arborele.