Tehnici de Programare Udri ștoiu Stefan [608698]

Tehnici de Programare Udri ștoiu Stefan
9. Arbori Stoica Spahiu Cosmin
1
Lucrarea 9 – Structuri arborescente.

Introducere
Dac ă ne-am uitat la un arbore genealogic, sau la o ierarhie de comand ă într-o firm ă,
am observat informa țiile aranjate într-un arbore.
Un arbore este compus dintr-o colec ție de noduri , unde fiecare nod are asociat ă o
anumită informa ție și o colec ție de copii.
Copiii unui nod sunt acele noduri care urmeaz ă imediat sub nodul îns ăși.
Părintele unui nod este acel nod care se afl ă imediat deasupra.
R ădăcina unui arbore este acel nod unic, care nu are nici un p ărinte.

Exemplu de ierarhie de comand ă intr-o firm ă:

In acest exemplu r ădăcina arborelui este Bob Smith. Este r ădăcină deoarece nu are
nici un p ărinte. Copilul s ău direct este Tina Jones.
Tina Jones are 3 noduri copii (nodurile de pe nivelul urm ător din ierarhie): Jisun Lee,
Frank Mitchell și Davis Johnson. P ărintele s ău este Bob Smith (nodul de pe nivelul superior,
din ierarhie).
To ți arborii au urm ătoarele propriet ăți:
• Există o singur ă rădăcină
• Toate nodurile, cu excep ția rădăcinii, au exact un singur p ărinte
• Nu exist ă cicluri. Aceasta înseamn ă că pornind de la un anumit nod, nu exist ă
un anumit traseu pe care îl putem parcurge, astfel încât s ă ajungem înapoi la nodul
de plecare.

Arbori Binari
Arborii binari sunt un tip aparte de arbori, în care fiecare nod are maxim 2 copii.
Pentru un nod dat, într-un arbore binar, vom avea copilul din stânga, și copilul din dreapta.
Exemplu de arbori binari:
PDF created with pdfFactory Pro trial version www.pdffactory.com

Tehnici de Programare Udri ștoiu Stefan
9. Arbori Stoica Spahiu Cosmin
2

Arborele din figura a) are 8 noduri, nodul 1 fiind r ădăcina. Acesta are ca și copil
stânga nodul nr.2, iar ca și copil dreapta nodul nr.3. La rândul s ău nodul nr.2 nu are decât un
singur copil (stânga), și anume nodul nr 4.
Deci un nod dintr-un arbore binar poate avea 2 copii (stânga și dreapta), un singur
copil (doar stânga sau doar dreapta) sau nici unul (exemplu nodul 8).
Nodurile care nu au nici un copil se numesc noduri frunz ă.
Nodurile care au 1 sau 2 copii se numesc noduri interne.

Pentru re ținerea informa ției în calculator se va folosi alocarea dinamic ă. Deoarece
pentru fiecare nod în parte este necesar s ă se rețină, pe lâng ă informa ția utilă și legăturile cu
nodurile copii (adresele acestora), ne putem imagina urm ătoarea structura a unui nod:

struct Nod {
int inf;
Nod *leg_st;
Nod *leg_dr;
};
Nod *prim;

unde: leg_st reprezint ă adresa nodului copil din stânga, inf reprezint ă câmpul cu
informa ție utilă, iar leg_dr este leg ătura cu copilul din dreapta.
Un arbore binar va avea urm ătoarea structur ă internă:

adr1 nivel 1

adr2 adr3 nivel 2

adr5 nivel 3

Pe nivelul 1 vom avea un singur nod, nodul r ădăcină. Componenta leg_st va fi egal ă
cu adresa adr2, nodul din stânga de pe nivelul 2, iar componenta leg_dr va fi egal ă cu adresa
adr3.
Componentele leg_st și leg_dr ale nodului din stânga de pe nivelul 2, vor fi egale cu
adr4, respectiv adr5. leg_st inf leg_dr
leg_st inf leg_dr
leg_st inf leg_dr leg_st inf leg_dr
leg_st inf leg_dr leg_st inf leg_dr
PDF created with pdfFactory Pro trial version www.pdffactory.com

Tehnici de Programare Udri ștoiu Stefan
9. Arbori Stoica Spahiu Cosmin
3 Nodul din dreapta de pe nivelul 2 nu mai are nici un copil și de aceea componentele
sale leg_st și leg_dr vor avea valoarea NULL (ca și la liste dinamice).
În mod analog și componentele leg_st și leg_dr ale nodurilor de pe nivelul 3 vor avea
valoarea NULL.

Arbori Binari de C ăutare
Un arbore binar de c ăutare este un arbore binar destinat îmbun ătățirii timpului de
cutarea informa ției. El va trebui s ă respecte urm ătoarea proprietate: pentru oricare nod n,
fiecare din descendentii din subarborele din stânga va avea valoarea informa ției mai mic ă
decât a nodului n, iar fiecare din descenden ții din subarborele din dreapta va avea valoarea
informa ției mai mare decât a nodului n.

Exemplu:

în figura de mai sus avem 2 arbori binari.
Arborele din figura b) este arbore binar de c ăutare deoarece este respectat ă regula de
mai sus, si anume c ă în oricare subarbore stâng valorile trebuie s ă fie mai mici decât ale
rădăcinii și în oricare subarbore dreapta, valorile trebuie s ă fie mai mari decât ale r ădăcinii.
(Cu alte cuvinte, toate valorile din nodurile aflate în stânga nodului n trebuie s ă fie mai mici,
iar cele din dreapta mai mari).
Se folose ște exprimarea „oricare din subarborii” stâng respectiv drept, deoarece
pentru r ădăcina 7, elementele subarborelui stâng sunt 3, 1, 5, 4 (care sunt toate mai mici
decât 7), iar elementele subarborelui drept sunt 11, 10, 15 (care sunt toate mai mari decât 7).
Dacă în schimb vom considera ca r ădăcină nodul 3, vom avea ca subarbore stâng nodul 1 (1
este mai mic decât 3), iar ca subarbore drept nodurile 5 și 4 (ambele mai mari decât 3).
Dac ă vom considera ca și rădăcină pe nodul 10, acesta nu are nici un copil, deci
implicit respect ă regula pentru arborii binari de c ăutare.
Arborele din figura a) nu este un arbore binar de c ăutare deoarece nu toate nodurile
respectă regula.
Nodul 4 nu are ce c ăuta acolo în dreapta nodului 8. Ar trebui s ă se afle în stânga lui 8
(4<8). Dac ă privim mai sus observ ăm că nodul 4 ar trebui s ă se afle și in stânga nodului 10,
și în stânga nodului 9, și în stânga nodului 7. Cu alte cuvinte nodul 4 nu are ce c ăuta în
subarborele drept. Unde ar trebui s ă fie pozi ționat astfel încât și arborele din figura a) s ă fie
arbore binar de c ăutare?

PDF created with pdfFactory Pro trial version www.pdffactory.com

Tehnici de Programare Udri ștoiu Stefan
9. Arbori Stoica Spahiu Cosmin
4 Crearea și inserarea într-un arbore binar de c ăutare

Vom considera arborele din dreapta. S ă
presupunem c ă dorim s ă inserăm nodul cu
valoarea 62. Acesta se va insera ca nod frunz ă.
Pentru a-l insera va trebui s ă căutăm o
poziție în arbore care respect ă regula de
integritatea a arborilor binari de c ăutare.

Vom începe prin compararea nodului de
inserat (62), cu r ădăcina arborelui (90).
Observăm că este mai mic decât ea, deci va
trebui inserat undeva în subarborele stâng al
acesteia.

Vom compara apoi 62 cu 50. Din moment
ce 62 este mai ma re decât 50, nodul 62 va trebui
plasat undeva în subarborele drept al lui 50.

Se compar ă apoi 62 cu 75. Deoarece 75
este mai mare decât 62, 62 trebuie s ă se afle în
subarborele din stânga al nodului 75

Dar 75 nu are nici un copil în partea stângă.
Asta înseamn ă că am găsit locația pentru nodul 62.
Tot ceea ce mai trebuie f ăcut este s ă modific ăm în
nodul 75 adresa c ătre copilul din stânga, încât s ă
indice spre 62.
PDF created with pdfFactory Pro trial version www.pdffactory.com

Tehnici de Programare Udri ștoiu Stefan
9. Arbori Stoica Spahiu Cosmin
5 Prin crearea unui arbore binar de c ăutare (A.B.C.) vom în țelege de fapt crearea
rădăcinii, restul nodurilor fiind ad ăugate prin opera ția de inserare.
Implementare :

//programul va primi ca parametru num ărul pe care trebuie s ă îl adauge
void insertie(int nr)
{
Nod *nod1, *nod2, *nod3;

//se creaz ă nodul care se adaug ă în arbore.
nod1 = new Nod;
nod1->inf = nr;
//deoarece o s ă se adauge ca nod frunz ă, el nu va avea nici un copil, deci
legăturile stânga și dreapta, vor fi nule
nod1->leg_st = NULL;
nod1->leg_dr = NULL;
//verificam mai intai dac ă există o rădăcină (dacă arborele a fost creat)
if(prim==NULL)
{
//nodul creat va deveni r ădăcina arborelui
prim = nod1;
}
//dacă există un nod r ădăcină, inserarea în arbore se va face conform
algoritmului prezentat mai sus.
else
{
nod2 = prim;
//se va c ăuta locul de inserare al nodului nod1, pornind c ăutarea din
rădăcină. Nodul nod3 va reprezenta nodul p ărinte al nodului nod1
while (nod2 != NULL) {
if (nr < nod2->inf) {
nod3 = nod2;
nod2 = nod2->leg_st;
} //end if
else { // se merge spre dreapta
nod3 = nod2;
nod2 = nod2->leg_dr;
}//end else
}//end while
//după găsirea nodului p ărinte, se creaz ă legătura nod3 (nod p ărinte) ->
nod1 (nodul inserat acum)
if (nr < nod2->inf)
//se asaza in stânga p ărintelui
nod3->leg_st = nod1;
else
//se așază în dreapta p ărintelui
nod3->leg_dr = nod1;
}//end else
return t;
}

Parcurgerea unui Arbore (Listarea)

Exist ă 3 tipuri de parcurgere a unui arbore: inordine, preordine și post ordine.
Aceste denumiri corespund modului cum este vizitat ă rădăcina.
Parcurgerea în preordine :
PDF created with pdfFactory Pro trial version www.pdffactory.com

Tehnici de Programare Udri ștoiu Stefan
9. Arbori Stoica Spahiu Cosmin
6 Parcurgerea în inordine se bazeaz ă pe urm ătorul principiu: se va vizita mai întâi r ădăcina,
copilul (copiii) din stânga, iar apoi copilul (copiii) din dreapta.
Implementarea se va face recursiv, astfel încât nu ne intereseaz ă ce se întâmpl ă decât pe
unul din nivele (de exemplu pe primul), pe restul procedându-se identic.
Fie arborele din figur ă:

Parcurgerea în preordine presupune:
1. se va vizita rădăcina 90
2. se viziteaz ă copilul din stânga (50). Dar acesta este la rândul s ău rădăcină pentru
subarborele 20 – 75. Fiind r ădăcină, ea se viziteaz ă prima. Deci vizit ăm și nodul 50.
3. se viziteaz ă copilul din stânga al nodului r ădăcină 50, adic ă nodul 20. Si acesta este
rădăcină pentru subarborele 5 – 25. Fiind r ădăcină, se va vizita și nodul 20 .
4. se viziteaz ă copilul din stânga al r ădăcinii 20, adic ă nodul 5 . Si acesta este r ădăcină
pentru arborele vid. Il vizit ăm.
5. cum pe ramura aceasta nu mai avem ce vizita, ne întoarcem la r ădăcina 20. Aceasta este
deja vizitat ă. La fel și copilul din stânga. Vom vizita copilul din dreapta, nodul 25.
6. nodul 25 nu mai are copii, deci nu mai avem ce vizita sub el. Cum pentru nodul r ădăcină
20 am vizitat si copilul din stânga și copilul din dreapta, vom mai urca un nivel la nodul
rădăcină 50. Pentru acesta tocmai am terminat de vizitat subarborele stâng. Mai avem de
vizitat subarborele drept. Vom merge la nodul 75 . Nodul 75 este r ădăcină pentru un alt
subarbore. Îl vizit ăm.
7. mergem la copilul din stânga, nodul 66 .
8. cum nodul 66 nu mai are copii, revenim la r ădăcina 75, pentru care vom vizita copilul din
dreapta: nodul 80
9. pentru r ădăcina 75 am vizitat tot ce se putea. Urc ăm la rădăcina 50. Si pentru aceasta am
vizitat tot ce se putea. Urc ăm la r ădăcina 90. Aici tocmai am terminat de vizitat
subarborele stâng. Mai avem de vizitat subarborele drept. Vom merge la nodul 150 . El
este rădăcină pentru subarborele 95 – 175, deci îl vizit ăm
10. vizităm copilul s ău din stânga, 95
11. Ne întoarcem la r ădăcina 150. Vizit ăm copilul din dreapta, 175
12. ne întoarcem la r ădăcina 90, pentru care am terminat de vizitat si subarborele drept. Cum
nu mai exist ă nici un nivel deasupra sa, am terminat de vizitat tot arborelel.

Vizitarea arborelui va întoarce vectorul:
90 – 50 – 20 – 5 – 25 – 75 – 66 – 80 – 150 – 95 – 175

Deși la prima vedere pare destul de complicat, implementarea este destul de simpl ă. Se va
folosi o func ție Preordine care prime ște ca parametru ini țial rădăcina arborelui (respectiv,
prin apel ări succesive, r ădăcinile subarborilor)

void Preordine(Nod* rad)
{
PDF created with pdfFactory Pro trial version www.pdffactory.com

Tehnici de Programare Udri ștoiu Stefan
9. Arbori Stoica Spahiu Cosmin
7 //dacă nu s-a ajuns la ultimul nod
if (rad != NULL) {
//se viziteaz ă rădăcina
printf(” %d – ”,rad->inf);
// se viziteaz ă copilul din stânga, apoi cel din dreapta
Preordine(rad->leg_st);
Preordine(rad->leg_dr);
}
}

Parcurgerea în inordine
Parcurgerea în inordine presupune vizitarea mai întâi a copilului din stânga, apoi vizitarea
rădăcinii și mai apoi a copilului din dreapta.
Pentru arborele anterior, se procedeaz ă astfel:
1. se porne ște de la r ădăcina 90. Pentru aceasta se viziteaz ă mai întâi copilul din stânga,
nodul 50. Si acesta este la rândul lui o r ădăcină pentru arborele 20 – 75. De aceea vom
vizita mai intai copilul s ău stâng, nodul 20, care la rândul s ău este r ădăcină pentru
arborele 5 – 25. Vom vizita mai întâi copilul stâng, nodul 5.
2. pentru nodul 5 nu mai avem ce vizita. Revenim la rădăcina 20 , pentru care tocmai am
vizitat subarborele stâng. Conform defini ției, o vizit ăm pe ea.
3. vizităm nodul 25 , copilul s ău drept.
4. revenim la r ădăcina 20. Nu mai avem ce vizita pe acest nivel. Urc ăm la rădăcina 50 .
Pentru aceasta am vizitat subarborele stâng. Este rândul ei s ă o vizităm.
5. Vom vizita apoi subarborele ei drept, dup ă modelul anterior
…………………..

În final vom ob ține parcuregerea:
5 – 20 – 25 – 50 – 66 – 75 – 80 – 90 – 92 – 95 – 111 – 150 – 166 – 175 – 200
Se observ ă faptul c ă parcurgerea în inordine va afi șa de fapt vectorul ordonat cresc ător.

void Inordine(Nod* rad)
{
//dacă nu s-a ajuns la ultimul nod
if (rad != NULL) {
// se viziteaz ă copilul din stânga
Inordine(rad->leg_st);
//se viziteaz ă rădăcina
printf(” %d – ”,rad->inf);
//se viziteaz ă copilul din dreapta
Inordine(rad->leg_dr);
}
}

Parcurgerea în postordine
Pentru parcurgerea în postordine, se va vizita mai întâi subarborele stâng, apoi
subarborele drept și de abia ultima dat ă rădăcina.

Care este vectorul returnat de aceast ă parcurgere?
Implementa ți algoritmul!

Ștergerea dintr-un arbore binar de c ăutare

Ideea de baz ă pentru ștergerea dintr-un arbore astfel încât s ă se păstreze structura de
arbore binar de c ăutare este s ă înlocuim nodul care se dore ște să se șteargă cu cel mai din
PDF created with pdfFactory Pro trial version www.pdffactory.com

Tehnici de Programare Udri ștoiu Stefan
9. Arbori Stoica Spahiu Cosmin
8 stânga nod, al subarborelui drept al nodului de șters.

Prezent ăm în continuare implementarea algoritmului de mai sus. Func ția de ștergere va primi
ca parametru informa ția care dorim s ă o ștergem (num ărul de șters) și va returna true în cazul
în care a f ăcut ștergerea sau fals în cazul în care informa ția care dorim s ă o ștergem din
arbore, nu a fost g ăsită (dorim s ă ștergem nodul 1000?).

bool Sterge(int nr)
{
Nod *tmp,*tmp1,*tmp2;
//se porne ște căutarea informa ției de șters din r ădăcină
tmp1 = rad;
while (tmp1->inf != nr)
{
if (tmp1->inf > nr)
tmp1 = tmp1->leg_st;
else
tmp1 = tmp1->leg_dr;
}
tmp = tmp1;
//dacă suntem în cazul I Pentru ștergerea unui nod avem
următoarele cazuri:

Cazul I
Dorim s ă ștergem nodul 50.
Acesta nu are subarbore drept, a șa că
îl vom înlocui pur șî simplu cu nodul
20.

Cazul II
Dorim s ă ștergem nodul 150.
Subarborele drept nu con ține decât
nodul 175 Nu exist ă un subarbore
stâng al subarborelui drept.
Se va înlocui nodul 150 cu 175.

Cazul III
Dorim s ă ștergem nodul 50.
Deoarece subarborele drept al
nodului 50 con ține un subarbore
stâng, se va alege cel mai din stânga
nod al subarborelui drept a lui 50.
Acest cel mai din stânga nod va
conține cel mai mic num ăr mai mare
decât nodul de șters. In cazul nostru
acest nod este 66.
PDF created with pdfFactory Pro trial version www.pdffactory.com

Tehnici de Programare Udri ștoiu Stefan
9. Arbori Stoica Spahiu Cosmin
9 if (tmp1->leg_dr==NULL){
//mutare inf din nodul din st, in nodul curent
tmp1->inf=tmp1->leg_st->inf;
//refacere leg ături
tmp1->leg_st = tmp1->leg_st->leg_st;
delete tmp1->leg_st;
}
else
//nu avem copil stânga
if (tmp1->leg_st == NULL){
//mutare inf din nodul din st, in nodul curent
tmp1->inf=tmp1->dr->inf;
tmp1->dr = tmp1->dr->dr;
delete tmp1->dr;
}
//cazul III
else {
//mergem la copilul din dreapta
tmp = tmp1->leg_dr;
tmp2 = tmp1;
//căutăm cel mai din stânga copil
while (tmp->leg_st != NULL)
{
tmp2 = tmp;
tmp = tmp->leg_st;
}

tmp1->inf = tmp->inf;
tmp2->leg_st = NULL;
delete tmp;
}//end else

return 0;
}

Probleme propuse

1. Implementa ți operațiile de ad ăugare, ștergere din arbore, c ăutare și parcurgere prin toate
trei metodele, folosind doar func ții recursive. Implementa ți o func ție de parcurgere care
sa returneze sirul ordonat descresc ător. (a nu se ordona vectorul dup ă ce s-a f ăcut
parcurgerea)

2. Implementa ți operațiile de ad ăugare în arbore (recursiv), ștergere din arbore (nodul de
șters se va înlocui cu cel mai din dreapta nod al subarborelui stâng al nodului de șters) și
parcurgere Parcurgerea se va face printr-o metod ă care s ă returneze sirul ordonat
descresc ător.

3. Implementa ți un arbore unde fiecare nod are maxim 3 copii, aranja ți după următoarea
regulă:
• copilul din stânga este mai mic decât jumatate din nodul r ădăcină (nod x <
rădăcină/2)
• nodul din mijloc are informa ția cuprins ă între [r ădăcină/2 si rădăcină]
• nodul din dreapta are informa ția > decât informa ția din rădăcină

PDF created with pdfFactory Pro trial version www.pdffactory.com

Tehnici de Programare Udri ștoiu Stefan
9. Arbori Stoica Spahiu Cosmin
10 4. Evidența produselor aflate în stocul unui magazin se ține într-un arbore de c ăutare. Pentru
fiecare nod se re ține: denumire produs, pre ț, cantitate. În fiecare sear ă arborele este
actualizat prin comenzi de forma:
i → se mai introduc produse primite de la depozit (Aten ție: un astfel de produs este
posibil s ă se mai afle în stoc)
s → se șterg produsele vândute în ziua respectiv ă
v → se tipărește valoarea tuturor produselor aflate pe stoc
L → se tipărește o list ă cu toate produsele aflate pe stoc

5. Se citesc de la tastatur ă n numere naturale care se adaug ă pe măsură ce se citesc într-o
stivă (implementat ă dinamic). S ă se adauge aceste numere într-un arbore binar de c ăutare.

6. Definim un arbore de c ăutare pentru numere complexe, în care fiecare nod va con ține ca
informa ție utilă partea real ă și partea imaginar ă a unui num ăr complex de forma x + iy. S ă se
creeze un arbore binar de c ăutare care s ă memoreze n numere complexe citite de la tastatur ă,
apoi să se scrie o func ție care s ă șteargă din arbore numerele complexe care au partea real ă și
partea imaginar ă egală.

7. Un arbore binar de c ăutare se nume ște AVL dac ă pentru orice nod, diferen ța dintre
înălțimea subarborelui stâng și a subarborelui drept este -1, 0 sau 1 (în ălțimea reprezint ă
numărul de nivele). S ă se construiasc ă un arbore AVL care s ă aibă în noduri cheile 1, 2, … n.
Indicație: să se foloseasc ă un algoritm Divide et Impera. La fiecare pas al procedurii
recursive de creare se introduce în arbore un subinterval al mul țimii {1,2 … n} cuprins între
{st…m} iar apoi {m+1, … dr}, cu m = (st + dr)/2

8.
PDF created with pdfFactory Pro trial version www.pdffactory.com