![](images/title/arboribinari.jpg)
![](images/def.gif)
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.
|