Arbori

1. Lista nodurilor a) Scrieți o funcție care construiește lista nodurilor unui arbore binar, traversat în i) preordine; ii) inordine; iii) postordine.
Tratați tipurile: 1) arbore binar oarecare; 2) arbore strict binar
b) Scrieți o funcție care ia un arbore binar și returnează lista nodurilor care au un singur fiu. Ordinea nodurilor în listă va fi cea din traversarea în inordine.
Pentru eficiență, folosiți o funcție ajutătoare care adaugă lista nodurilor unui arbore (în ordinea indicată) la o listă dată.

2. Parcurgerea arborilor oarecare Modificați funcțiile de parcurgere așa încât să funcționeze pe arbori oarecare (fiecare nod are o listă de fii). Folosiți funcții de parcurgere pe liste. Pentru inordine, parcurgeți întâi capul listei, apoi rădăcina și coada listei.
Indicații: Folosiți unul din tipurile generale pentru arbori (nu neapărat binari) de la curs. Funcțiile de traversare de la curs au doi parametri: primul număr disponibil pentru etichetare, și arborele. Ele returnează următorul număr disponibil pentru etichetare. Deci ele pot fi folosite direct ca funcție în List.fold_left pe o listă de subarbori: rezultatul funcției e intrare pentru următorul element (arbore) din listă.

3. Tipărire indentată Scrieți o funcție care afișează un arbore în a) preordine; b) inordine, câte un nod pe linie, precedând valoarea din 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. Arbore binar de căutare Scrieți o funcție care determină dacă un arbore este un arbore binar de căutare: pentru fiecare nod, subarborele stâng conține doar valori mai mici, iar cel drept, doar valori mai mari.
Indicație: Folosiți o funcție auxiliară care verifică dacă toate nodurile unui arbore sunt într-un anumit interval (posibil nelimitat la un capăt).
Puteți folosi de exemplu următoarele funcții ajutătoare care lucrează cu valori opționale (None însemnând nelimitat) și verifică apartenența la un interval:

let less = function
  | (None, _) | (_, None) -> true
  | (Some v1, Some v2) -> v1 < v2
     
let between x (a, b) = less (a, x) && less (x, b)
  

5. Eliminarea unui nod Scrieți o funcție care ia ca parametru o valoare și un arbore binar de căutare și returnează arborele din care valoarea a fost eliminată (dacă exista).
Indicație: Dacă valoarea e într-un nod cu doi descendenți, va trebui fie să o înlocuiți cu maximul arborelui stâng sau minimul arborelui drept (după preferință), sau să inserați un subarbore într-un loc gol (fiu inexistent) în alt arbore.

6. Arbore echilibrat (AVL) Scrieți o funcție care determină dacă un arbore binar e echilibrat, în sensul că pentru fiecare nod, înălțimea celor doi subarbori diferă cu cel mult 1.
Indicație: Folosiți o funcție auxiliară care calculează înălțimea unui arbore (similar cu cea de la curs), dar generează o excepție (de exemplu Exit) în loc să returneze înălțimea dacă diferența de înălțime între subarbori depășește 1.
Funcția cerută va apela funcția auxiliară de calcul a înălțimii, returnând true dacă aceasta se încheie cu succes, sau false dacă eșuează cu excepție (vezi ca exemplu implementarea lui mem pentru liste din notițele de curs sau pentru dicționare din discuția de pe Piazza.

7. Arbore aproape complet Scrieți o funcție care determină dacă într-un arbore binar cel mult ultimul nivel e incomplet.
Indicație: Scrieți o funcție auxiliară care pentru un arbore returnează o pereche cu adâncimea minimă și maximă până la un nod vid. Combinați rezultatele pentru cei doi subarbori. Dacă obțineți un interval de lungime maxim 1, îl returnați, altfel generați o excepție.
Funcția cerută va returna false sau true după cum funcția auxiliară generează o excepție sau nu.

8. Al n-lea nod Scrieți o funcție care returnează al n-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.

9. Arbore din liste 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]

10. Mulțimea ca arbore O mulțime poate fi implementată ca arbore binar de căutare (în practică, o formă echilibrată, pentru eficiență). Completați modulul de mai jos cu funcții pentru a căuta și adăuga un element într-o mulțime reprezentată ca arbore. Puteți apoi instanția module S = TreeSet(String) și folosi toate funcțiile scrise, la fel cum le-ați folosit pe cele din modulul standard Set.

module TreeSet(Elt: Set.OrderedType) = struct
  type t = Nil | T of t * Elt.t * t
  let empty = Nil
  let is_empty t = (t = Nil)
  let singleton e = T (Nil, e, Nil)
  let rec mem e s = ...
  (* folosește:   Elt.compare e1 e2   (va fi < 0, 0 sau > 0) *)
  let rec add e s = ...
end