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