Arbori binari





Definiţie:Se numeşte arbore un graf conex şi fără cicluri.
Exemplu de arbore:
Graful G=(V,M) unde V={1,2,3,4} şi M={[1,2],[2,3],[1,4]}, a cărui reprezentare grafică este figurată mai jos, este arbore.

Definiţie:Se numeşte arborescenţă un arbore caracterizat astfel:
-are un vârf special numit rădăcină;
-celelalte noduri pot fi grupate în p>=0 mulţimi disjuncte, astfel
încât fiecare dintre aceste mulţimi să conţină un nod adiacent cu rădăcina iar subgrafurile generate de acestea să fie la rândul lor arborescenţe.
OBSERVAŢII!
1. Dacă o arborescenţă este formată dintr-un singur nod spunem că este formată doar din nodul rădăcină.
2. Dacă ordinea relativă a arborescenţelor, are importanţă, arborescenţa se numeşte se numeşte arbore ordonat.
Definiţie:Se numeşte arbore binar, o mulţime finită de noduri care este fie vidă, fie un arbore ordonat în care fiecare nod are cel mult doi descendenţi(succesori).

Exemplu de arbore binar:

Teoriile care tratează arborii binari folosesc în plus faţă de cele care se referă la structurile arborescente în general, următoarele noţiuni:
• Succesor stâng: pentru un nod, se numeşte succesor stâng acel succesor care este figurat în stânga sa.
Ex:pentru nodul 1, succesorul stîng este nodul 2;
nodul 5, succesorul stîng este nodul 7;
nodul 7,succesorul stîng nu există.
• Succesor drept: pentru un nod, se numeşte succesor drept acel succesor care este figurat în dreapta sa.
Ex:pentru nodul 1, succesorul drept este nodul 3;
nodul 5, succesorul drept nu există.
• Subarbore stâng: pentru un nod, se numeşte subarbore stâng subarborele care se obţine suprimând muchia care-l leagă pe acesta de succesorul său stâng; dacă succesorul stâng nu există, se spune că subarborele stâng este vid.
Ex:pentru nodul 1 subarborele stâng este:

• Subarbore drept: pentru un nod, se numeşte subarbore drept subarborele care se obţine suprimând muchia care leagă pe acesta de succesorul drept; dacă succesorul drept nu există, se spune că subarborele drept este vid.
Ex:pentru nodul 1 subarborele drept este:


Descarca toata lectia

Please enable / Bitte aktiviere JavaScript!
Veuillez activer / Por favor activa el Javascript![ ? ]