Arbori binari

Un arbore este o multime de elemente numite noduri sau vârfuri pentru care:

1. exista un nod cu destinatie speciala (radacina arborelui);
2. celelalte noduri sunt repartizate în n$>=$0 seturi disjuncte A1, A2, ..., An fiecare set constituind la rândul sau un arbore.

În structura ierarhica a arborelui, fiecare nod (mai putin radacina) este subordonat unui alt nod (relatie fiu-parinte). Daca un nod nu are fii, el se numeste terminal (sau frunza)

Un arbore binar este un arbore în care un nod are maxim doi fii. Arborii binari ordonati reprezinta un caz particular al arborilor binari, în care fiecare nod contine o informatie distincta numita cheie, cu proprietatea ca, pentru fiecare nod $t_{i}$, toate nodurile din subarborele stâng au cheia mai mica decât cheia lui $t_{i}$ si toate nodurile din subarborele drept au cheia mai mare decât cheia lui $t_{i}$. Arborii binar ordonati se numesc si arbori de cautare.

Principalele operatii asupra arborilor binar ordonati, prezentate în continuare, sunt: cautarea unui nod în arbore, inserarea unui nod în arbore, stergerea unui nod din arbore si parcurgerea arborelui. Se vor prezenta algoritmii recursivi pentru realizarea acestor operatii.