.În informatica, 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 cautare sau/și la stucturile de date de tip heap.
Un arbore binar este o mulțime de noduri care îndeplinesc următoarele condiții:
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).
Se identifica printr-un nod unic numit radacina iar celelalte noduri se aseaza pe nivele in functie de departarea lor fata de radacina.
- Tatal unui nod este nodul adiacent ce acesta de pe nivelul anterior numit adiacent direct.
- Fiul unui nod este nodul adiacent aflat pe nivelul urmator.
- Un nod poate avea un singur tata.
- Doua noduri care au acelasi tata se numesc frati.
- Nodurile care nu au fii se numesc noduri terminale sau frunze.
Structura unui arbore admite o definitie recursiva adica orice fiu al unui nod din arbore este la randul sau arbore.Reprezentarea acestui arbore se face folosind un vector numit vector de tati cu semnificatia t[i]=tatal varfului i. Radacina este singurul nod care nu are tata, deci t[r]=0.
Un arbore binar este un arbore orientat in care fiecare varf are cel mult doi descendenti, facandu-se insa distinctie clara intre descendentul drept si descendentul stang al fiecarui varf.
Arborii binari nu reprezinta cazuri particulare de arbori orientati, decat daca se face abstractie de distinctia mentionata intre descendentul drept si cel stang al fiecarui varf. Intr-adevar daca un varf are un singur descendent, aceasta informatie este suficienta in cazul unui arbore, dar insuficienta in cazul unui arbore binar, cand trebuie precizat daca acest descendent este descendent stang sau descendent drept.
Arborii, ca structuri dinamice de date, au extrem de multe aplicatii in informatica. Deosebit de utilizatain aplicatii este structura de tip arbore binar. Un arbore binar este un arbore in care fiecare nod are cel mult doi fii, fiul stang si fiul drept (fiul stang este legat in stanga tatalui si cel drept in dreapta ).
Daca in figura se elimina radacina si legaturile ei, se obtin doi arbori binari care se numesc subarborii stang sidrept ai arborelui initial. Arborele binar este, deci, o structura recursiva de date. Un arbore binar nevid fie se reduce la radacina, fie cuprinde radacina si, cel mult, doi subarbori binari. Un arbore binar se poate implementa foarte usor cu ajutorul adreselor de inlantuire, fiecare element cuprinzand, in afara de informatia proriu-zisa asociata nodului, adresa fiului stang si adresa fiului drept, acestea exprimand legaturile existente intre noduri.
- Tatal unui nod este nodul adiacent ce acesta de pe nivelul anterior numit adiacent direct.
- Fiul unui nod este nodul adiacent aflat pe nivelul urmator.
- Un nod poate avea un singur tata.
- Doua noduri care au acelasi tata se numesc frati.
- Nodurile care nu au fii se numesc noduri terminale sau frunze.
Structura unui arbore admite o definitie recursiva adica orice fiu al unui nod din arbore este la randul sau arbore.Reprezentarea acestui arbore se face folosind un vector numit vector de tati cu semnificatia t[i]=tatal varfului i. Radacina este singurul nod care nu are tata, deci t[r]=0.
Un arbore binar este un arbore orientat in care fiecare varf are cel mult doi descendenti, facandu-se insa distinctie clara intre descendentul drept si descendentul stang al fiecarui varf.
Arborii binari nu reprezinta cazuri particulare de arbori orientati, decat daca se face abstractie de distinctia mentionata intre descendentul drept si cel stang al fiecarui varf. Intr-adevar daca un varf are un singur descendent, aceasta informatie este suficienta in cazul unui arbore, dar insuficienta in cazul unui arbore binar, cand trebuie precizat daca acest descendent este descendent stang sau descendent drept.
Arborii, ca structuri dinamice de date, au extrem de multe aplicatii in informatica. Deosebit de utilizatain aplicatii este structura de tip arbore binar. Un arbore binar este un arbore in care fiecare nod are cel mult doi fii, fiul stang si fiul drept (fiul stang este legat in stanga tatalui si cel drept in dreapta ).
Daca in figura se elimina radacina si legaturile ei, se obtin doi arbori binari care se numesc subarborii stang sidrept ai arborelui initial. Arborele binar este, deci, o structura recursiva de date. Un arbore binar nevid fie se reduce la radacina, fie cuprinde radacina si, cel mult, doi subarbori binari. Un arbore binar se poate implementa foarte usor cu ajutorul adreselor de inlantuire, fiecare element cuprinzand, in afara de informatia proriu-zisa asociata nodului, adresa fiului stang si adresa fiului drept, acestea exprimand legaturile existente intre noduri.