Definitie
Un arbore binar este un arbore în care orice vârf are cel mult doi descendenţi, cu precizarea că se face distincţie între descendentul stâng şi cel drept.
Reprezentarea arborilor binari
Forma standard de reprezentare a unui arbore binar constă în:
-a preciza rădăcina arborelui = (notatie) rad
-a preciza pentru fiecare vârf i tripletul:
– st(i) = descendentul stâng
– dr(i) = descendentul drept
– info(i) = informaţia ataşată vârfului
Trebuie stabilită o convenţie pentru lipsa unuia sau a ambilor descendenţi, ca de exemplu specificarea lor prin valoarea 0.
Tipuri de reprezentari statice:
1) Cu ajutorul a doi vectori:
Vectorul st – care contine descendentii stangi ai unui nod
Vectorul dr – care contine descendentii drepti ai unui nod
2) Cu ajutorul altor doi vectori:
Vectorul tata care retine valorile care sunt descendenti ai fiecarui nod in parte
Vectorul desc care are valori de -1 sau 1 prin care se specifica daca un nod este descendent stang, respectiv drept.
Presupunând că informaţia ataşată fiecărui vârf este chiar numărul său de ordine, avem:
• rad = 1
• st = (2,3,4,0,6,0,0,0,0)
• dr = (8,5,0,0,7,0,0,9,0)
• info= (1,2,3,4,5,6,7,8,9)
Pentru exemplul de mai sus:
• tata = (0,1,2,3,2,5,5,1,8)
• desc = (0,-1,-1,-1,1,-1,1,1,1)
• info = (1,2,3,4,5,6,7,8,9)
Definitie
Numim nod terminal sau frunza, un nod fara descendenti.
Definitie
Numim arbore binar complet, un arbore binar in care fiecare nod care nu este terminal are exact doi descendenti.
Propozitie
Un arbore binar complet care are n noduri terminale, toate situate pe acelasi nivel, are in total 2*n-1 noduri.