Arbori binari
I
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!
- Dacă o arborescenţă este formată dintr-un singur nod spunem că este formată doar din nodul rădăcină.
- 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:
- Nod frunză(sau terminal): un nod se numeşte frunză dacă nu are descendenţi.
Ex:în arborele prezentat mai sus, frunzele sunt nodurile 4,7,8,9.
Definiţie:Se numeşte arbore binar complet un arbore binar în fiecare nod, care nu este frunză, are exact doi descendenţi.
Propoziţie:Un arbore binar complet care are p noduri terminale, toate situate pe acelaşi nivel, are în total 2p-1 noduri.
REPREZENTAREA ARBORILOR BINARI
Dacă avem în vedere faptul că un arbore binar este un arbore, care înainte de toate este un graf, putem spune că printre metodele de reprezentare a arborilor binari se numără şi metodele de reprezentare a grafurilor, cum ar fi:
-reprezentarea prin matricea de adiacenţă;
-reprezentarea prin listele de adiacenţă;
-reprezentarea prin şirul muchiilor;
Modalităţile de reprezentare specifice arborilor binari sunt:
-reprezentarea standard:
1.cu ajutorul vectorilor
2.folosind alocarea dinamică
-reprezentarea cu ajutorul legăturilor Tata.
Reprezenarea cu ajutorul legăturii tata
Acest mod de reprezentare se realizează astfel:
-pentru fiecare nod, se precizează părintele său;
-pentru fiecare nod, se precizează ce fel descendent este, stâng sau drept, pentru părintele său.
OBSERVAŢIE!
Implementarea acestui mod de reprezentare, în cadrul unui program, se face folosind vectorii tata şi desc(desc=descendent), care au atâtea componente câte noduri are arborele, cu următoarele semnificaţii:
tata[I]: reţine părintele nodului I, dacă acest există;
şi reţine 0, dacă nodul I nu are părinte(în cazul rădăcinii);
desc[I]: reţine valoarea -1, dacă nodul I este descendent stâng;
reţine valoarea 1, dacă nodul I este descendent drept;
reţine valoarea 0, dacă nodul I este rădăcina arborelui.
PARCURGERA ARBORILOR BINARI
Prin parcurgerea arborilor binari se înţelege examinarea în mod sistematic a nodurilor sale astfel încât să fie atins o singură dată.
Există trei modalităţi, specifice arborilor binari, de parcurgere:
-parcurgerea în preordine (RSD: rădăcina-stânga-dreapta)
-parcurgerea în inordine (SRD: stânga-rădăcina-dreapta)
-parcurgerea în postordine (SDR: stânga-dreapta-rădăcina)
Parcurgerea în preordine, a arborelui cu rădăcina I, presupune parcurgerea etapelor:
-se vizitează rădăcina(nodul i);
-dacă există, se parcurge în preordine subarborele stâng: stâng(are rădăcina st[I]);
-dacă există, se parcurge în preordine subarborele drept(are rădăcia dr[I]);
Parcurgerea în inordine, a arborelui cu rădăcina I, presupune parcurgerea etapelor:
-dacă există, se parcurge în inordine subarborele stâng(are rădăcina st[I]);
-se viziteaiă rădăcina(nodul i);
-dacă există, se parcurge în inordine subarborele drept(are rădăcina dr[I]);
Parcurgerea, în postordine, a arborelui cu rădăcina I, presupune parcurgerea etapelor:
-dacă există, se parcurge în postordine subarborele stâng(are rădăcina st[I]);
-dacă există, se parcurge în postordine subarborele drept(are rădăcina dr[I]);
-se vizitează rădăcina(nodul I).
Exemplu:Fie arborele binar:
Lista nodurilor în urma parcurgerii:
în preordine este: 1,2,4,5,7,3,6,8,9
în inordine este: 4,2,7,5,l,3,8,6,9
în postordine este: 4,7,5,2,8,9,6,3,1
Problema rezolvate:
Enunt:
Creati arborele binar asociat unei secvenţe de caractere. Secvenţa este constituită din litere mari şi caracterele ( , ) $. Seminificaţia acestora este următoarea:
- literele reprezintă informaţia dintr-un nod;
- ( defineşte un nivel inferior;
- , separă sub-arborele stâng de cel drept;
- ) marchează stârşitul nivelului inferior;
- $ marchează lipsa sub-arborelui respectiv.
Exemplu: “A ( B , C ( D ( E , F ) , $ ) )”.
Solutie:
Plecand de la exemplu, putem observa ca arborele binar asociat secventei este:
Pentru a crea acest arbore, vom defini un tip de date propriu pentru nodul arborelui:
struct nod
{
char info;
int ss, sd;
nod *tata, *s, *d;
};
Dupa cum se observa, acest tip de date difera de nodul unui arbore binar “standard”, datorita faptului ca functia de creare este recursiva, de unde si nevoia unui pointer catre nodul tata. Campurile ss si sd sunt necesare unei eventuale prelucrari ale arborelui, din moment ce secventa de caracere nu precizeaza nodurile fara succesori.
Asadar, functia de creare este:
void creare_2( nod *& n)
{
char c;
cin.get(c);
if( c==’\n’)
return;
else
{
if( c>=65 && c<=90)
{
n->info = c;
n->ss = 0;
n->sd = 0;
creare_2( n);
}
else
{
if( c=='(‘)
{
n->s = new nod;
n->s->tata = n;
n->ss = 1;
creare_2( n->s);
}
if( c==’)’)
{
creare_2( n->tata);
}
if( c==’,’)
{
n->tata->d = new nod;
n->tata->d->tata = n->tata;
n->tata->sd = 1;
creare_2( n->tata->d);
}
if( c==’$’)
{
n->info= null;
creare_2( n);
}
}
}
}
informatica.cnet 