Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

CATEGORII DOCUMENTE





AccessAdobe photoshopAlgoritmiAutocadBaze de dateC
C sharpCalculatoareCorel drawDot netExcelFox pro
FrontpageHardwareHtmlInternetJavaLinux
MatlabMs dosPascalPhpPower pointRetele calculatoare
SqlTutorialsWebdesignWindowsWordXml

ARBORI BINARI. DEFINITIE SI TERMINOLOGIE

calculatoare

+ Font mai mare | - Font mai mic







DOCUMENTE SIMILARE

Trimite pe Messenger
Perceptia umana si procesarea de imagini
Informatica Multimedia - CSS
Redenumirea folderelor si fisierelor
VoIP - Managementul implementarii sistemului intr-o societate cu filiale distribuite in diferite localitii
Bruel & Kjaer PULSE
CONCEPEREA SI REALIZAREA UNUI SISTEM INFORMATIC (eventual FINANCIAR BANCAR)
Schemele logice (organigrama)
Procesare de text
METODICA PREDARII INFORMATICI
CAI DE IMPLEMENTARE A LIMBAJELOR DE PROGRAMARE

ARBORI áBINARI. DEFINITIE SI TERMINOLOGIE

Definitie. Se numeste arborescenta un arbore caracterizat astfel:



-á are un varf special numit radacina

- celelalteáá noduriáá potáá fiáá grupateáá ináá p>0áá multimiáá disjuncte,
V,,V2,,Vp,áá astfeláá incatáá fiecareáá din acesteá multimiáá saá continaá un nod adiacent cu radacina iar subgrafurile generate de aceasta sa fie la randul lor arborescente.

Exemplu. Graful din figura de mai jos este o arborescenta.

3

Demonstratie:

Graful este arbore. Contine un nod special numit radacina, fie acesta nodul 1.

Celelalte noduri se pot imparti in multimi disuncte V1= si V2= astfel incat in multimea V1, sa existe nodul 2 adiacent cu radacina, iar in multimea V2 sa existe nodul 4 adiacent cu radacina, si subgrafurile generate de V, si V2 sa fie la randul lor arborescente.

Obsevatii: 1. Daca o arborescenta este formata dintr-un singur nod spunem caáá este formata doar din nodul radacina.

2.á Daca ordinea relativa a arborescentelor,á generateá de V1,V2,,Vpáá din

definitie, are importanta, arborescenta se numeste arbore ordonat.

In reprezentarea grafica a unei arborescente, nodurile se deseneaza pe nivele, astfel:

pe primul nivelááááá : se deseneaza radacina;

pe al doilea niveláá : se deseneaza nodurile adiacente cu radacina;

pe al treilea nivel : se deseneaza nodurile adiacente cu noduri de pe

áááááááááááááááááááááááááááááá nivelul al doilea, si nu se afla pe nivelul 1;

pe al k-lea niveláááá : se deseneaza nodurile adiacente cu noduri de pe áááááááááááááááááááááánivelul k-1, si nu se afla pe nivelul k-2;áááááááááááááááááááááááááá áááááááááááááááááááááááááááá


Exemplu de arborescenta reprezentata grafic, conform regulii prezentate mai sus:


Definitie. Se numeste arbore binar, o multime finita de noduri care este vida, fie un arbore ordonat in care fiecare nod are cel mult doi descendenti(succesori).

Exemplu de arbore binar:

Teoriile care trateaza arborii folosesc in plus fata de cei care se refera la structurile arborescente in general, urmatoarele notiuni:




- succesor stang: pentru un nod, se numeste succesor stang acel successor care este figurat in stanga sa.

Exemplu: pentru nodul 1, succesorul stang este nodul 2;

pentru nodul 5, succesorul stang este nodul 7;

pentru nodul 7, succesorul stang nu exista.

- succesor drept: pentru un nod, se numeste succesor stang acel succesor

care este figurat in stanga sa.

Exemplu: pentru nodul 1, succesorul drept este nodul 3; pentru nodul 5, succesorul drept nu exista;


subarbore stang:áá pentru un nod se numeste subarbore stang subarborele care se obtineá suprimand muchia care-1á leaga pe acesta de succesorul sau stang; daca succesorul stang nu exista, se spune ca subarborele stang este vid. Exemplu. Pentru nodul 1 subarborele stang este:

subarborele drept: pentru un nod, se numeste subarbore drept subarborele care

se obtineá suprimand muchia care-1á leaga pe acesta de succesorul sau drept; daca succesorul drept nu exista, se spune ca subarborele drept este vid. Exemplu. Pentru nodul 1 subarborele drept este:

- nod frunza (sau terminal): un nod se numeste frunza daca nu are descendenti.

Exemplu. In arborele prezentat maiá sus,á frunzele sunt nodurile 4,7,8 si 9.

Definitie. Se numeste arbore binar complet un arbore binar in care fiecare nod, care nu este frunza, are exact doi descendenti.

Exemplu de arbore binar complet:

Propozitie: Un arbore binar complet care are p noduri terminate, situate pe acelasi nivel, are in total 2p-l noduri.

Exemplu: Fie arborele binar complet din figura:

ááááááááááááááááááááááááááá



Deoarece are p=8 noduri terminale, toate situate pe acelaži nivel, are, conform propozitiei de mai sus, 2p-1=2*8-1=15 noduri.








Politica de confidentialitate

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1075
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2019 . All rights reserved

Distribuie URL

Adauga cod HTML in site