Arbori binari 

 

În informatică, un arbore binar este un arbore în care fiecare nod are cel mult doi succesori (fii). De obicei, succesorii se numesc „nodul stânga”(fiul stânga) și „nodul dreapta”(fiul dreapta). Într-un arbore binar, rangul unui nod poate fi cel mult doi. Arborii binari sunt folosiți mai ales drept arbori binari de căutare sau/și la structurile de date de tip heap, fiind foarte eficienți și pentru sortarea datelor.

 

De asemenea, un arbore binar este o mulțime de noduri care îndeplinesc următoarele condiții:

• fiecare nod are 0, 1 sau 2 succesori;

• fiecare nod are un singur predecesor, cu excepția rădăcinii care nu are niciunul;

• succesorii fiecărui nod sunt ordonați (fiul stâng, fiul drept; dacă este unul singur trebuie menționat care).

 

Definiția recursivă:

• (Baza:) Arborele fără niciun nod este un arbore binar.

• (Pasul recursiv:) Fie a și b doi arbori binari, iar n un nod. Atunci arborele care îl are pe n ca rădăcină, pe a ca subarbore stâng și pe b ca subarbore drept este un arbore binar.