Arbore binar

Î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” și „nodul dreapta”. Arborii binari sunt folosiți mai ales drept arbori binari de căutare sau și la structurile de date de tip heap.

Un arbore binar cu 9 noduri, înălţimea 3, şi în care rădăcina are valoarea 2

Definiții alternative

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.