Un arbore binar este un arbore care fie este vid, fie consta dintr-un nod radacina si doi arbori binari disjuncti numiti subarborele stang, respectiv subarborele drept.

Clase speciale:

1) ARBORI BINARI STRICTI sunt arborii binari in care orice varf are gradul zero (este terminal) sau doi (are exact doi fii).

2) ARBORI BINARI PLINI sunt arbori binari care au 2^k-1 varfuri dispuse pe nivelurile 0,1, ..., k-1, astfel incat pe fiecare nivel i se gasesc 2^i varfuri.

3) ARBORI BINARI COMPLETI sunt arbori binari care se obtin dintr-un arbore binar plin prin eliminarea din dreapta catre stanga a unor noduri de pe ultimul nivel.

PROPRIETATI ALE ARBORILOR BINARI

Proprietatea 1 :: Numarul maxim de noduri de pe nivelul i al unui arbore binar este 2^i.

Proprietatea 2 :: Numarul maxim de noduri intr-un arbore binar cu inaltimea h este 2^(h+1)-1

Proprietatea 3 :: In orice arbore binar nevid cu n noduri noduri terminale exista n-1 noduri de grad 2.

Proprietatea 4 :: Un arbore cu n varfuri are inaltimea cel putin egala cu [log n].

Proprietatea 5 :: Definim lungimea drumurilor interne (I) ca fiind suma lungimilor drumurilor de la radacina la noduri neterminale (interne) si lungimea drumurilor externe (E) ca fiind suma lungimilor drumurilor de la radacina la noduri terminale (frunza sau externe). Intr-un arbore binar cu n noduri interne, E = I+2*n.