O clasă foarte importantă de
arbori cu rădăcină o constituie arborii binari. Un arbore binar este un arbore cu rădăcină în care gradul oricărui
vârf este cel mult egal cu doi.
Definim recursiv arborii binari
astfel :
Un arbore binar (Figura
nr.4) este un arbore care fie este vid, fie constă dintr-un nod rădăcină şi doi arbori binari
disjuncţi numiţi subarborele stâng (A1, Figura nr.4), respectiv
subarborele drept (A2, Figura nr.4).
 |
Figura nr. 4 – Structura simplificată a unui arbore binar
|
Se face o distincţie clară între
subarborele drept şi cel stâng. Dacă subarborele stâng este nevid,
rădăcina lui se numeşte fiul stâng al rădăcinii. Analog, dacă subarborele drept este nevid, rădăcina
lui se numeşte fiul drept al rădăcinii.