Declararea si utilizarea arborilor in ingineria programarii in C/C++

Declararea si utilizarea arborilor in ingineria programarii in C/C++

1. Introducere

Organizarea datelor in liste liniare nu este totdeauna suficienta in unele aplicatii. De exemplu, daca trebuie descrisa structura unui produs, va fi nevoie de o descriere ierarhizata a partilor care il compun, adica a unei structuri asemanatoare unui arbore. Organizarea ierarhizata, arborescenta, a datelor este intalnita in cele mai diverse domenii cum ar fi : organizarea administrativa a unei tari, stabilirea ordinii de executie a operatiilor tehnologice pentru obtinerea unor produse sau a ordinii de efectuare a operatiilor in vederea obtinerii valorii unei expresii aritmetice. In concluzie orice entitate fizica sau abstracta poate fi reprezentata printr-o structura ierharhizata, arborescenta.

Daca se considera ierarhia de comanda intr-o firma, se observa informatiile aranjate intr-un arbore.

Un arbore este compus dintr-o colectie de noduri, unde fiecare nod are asociata o anumita informatie si o colectie de copii, de descedenti.

Copiii sau descendentii unui nod sunt acele noduri care urmeaza imediat sub nodul insusi.

Parintele unui nod este acel nod care se afla imediat deasupra acestuia.

Radacina unui arbore este acel nod unic, care nu are nici un parinte.

Exemplu Ierarhia administrativa intr-o societate de productie:

In acest exemplu radacina arborelui este Director general (Popescu Ion). Este radacina deoarece nu are nici un parinte si are 3 noduri. Copii sai directi sunt: Directia productie (Director productie Ionescu Constantin), Directia economica (Director economic Tomescu Eleonora) si Directia proiectare (Director proiectare Stamate Valeriu). Serviciul Comercial (Sef de serviciu Chelcea Mioara) are ca parinte nodul Directia economica (Director economic Tomescu Eleonora) iar ca noduri copii are nodurile: Biroul aprovi-zionare (Sef de birou Pasare Maria) si Biroul desfa-cere (Sef de birou Pitigoi Ioana)

Toti arborii au urmatoarele proprietati:

- Exista o singura radacina

- Toate nodurile, cu exceptia radacinii, au exact un singur parinte

- Nu exista cicluri. Aceasta inseamna ca pornind de la un anumit nod, nu exista un anumit traseu pe care il putem parcurge, astfel incat sa ajungem inapoi la nodul de plecare.

2. Arbori Binari

Arborii binari sunt un tip aparte de arbori, in care fiecare nod are maxim 2 copii. Pentru un nod dat, intr-un arbore binar, vom avea copilul din stanga, si copilul din dreapta.

Exemplu de arbori binari:

Arborele din figura (a) are 8 noduri, nodul 1 fiind radacina. Acesta are ca si copil stanga nodul nr.2, iar ca si copil dreapta nodul nr.3. La randul sau nodul nr.2 nu are decat un singur copil (stanga), si anume nodul nr 4.

Deci un nod dintr-un arbore binar poate avea 2 copii (stanga si dreapta), un singur copil (doar stanga sau doar dreapta) sau nici unul (exemplu nodul 8).

Nodurile care nu au nici un copil se numesc noduri frunza.

Nodurile care au 1 sau 2 copii se numesc noduri interne.

Pentru retinerea informatiei in calculator se va folosi alocarea dinamica. Deoarece pentru fiecare nod in parte este necesar sa se retina, pe langa informatia utila, si legaturile cu nodurile copii (adresele acestora), ne putem imagina urmatoarea structura a unui nod:

struct Nod

Nod *primul_nod;

Unde adr_leg_stanga reprezinta adresa nodului copil din stanga, inf reprezinta campul cu informatie utila, iar adr_leg_dreapta este legatura cu copilul din dreapta.

Arborelui binary din figura (b) de mai sus, va avea urmatoarea structura interna in memoria calculatorului :

nod 1         

nivel 1

adr_n1

nod 2 nod 3             

nivel 2

adr_n2 adr_n3

nod 4 nod 5 nod 6 nod 7

adr_n4 adr_n5 adr_n6 adr_n7 nivel 3

Pe nivelul 1 vom avea un singur nod, nodul radacina. Componenta adr_leg_stanga va fi egala cu adresa adr_n2, a nodul din stanga de pe nivelul 2, iar componenta adr_leg_dreapta va fi egala cu adresa adr_n3, a nodului din dreapta de pe nivelul 2.

Lucrare: Descompuneri in factori Proiect: Media aritmetica si media aritmetica ponderata

Componentele adr_leg_stanga si adr_leg_dreapta ale nodului din stanga de pe nivelul 2, vor fi egale cu adr_n4, respectiv adr_n

Componentele adr_leg_stanga si adr_leg_dreapta ale nodului din dreapta de pe nivelul 2, vor fi egale cu adr_n6, respectiv adr_n7.

Toate nodurile din stanga, respectiv dreapta de pe nivelul 3 nu mai are nici un copil, descendent, si de aceea componentele lor, adr_leg_stanga si adr_leg_dreapta vor avea valoarea NULL, ca si la listele dinamice.

Arbori Binari de Cautare

Un arbore binar de cautare este un arbore binar destinat imbunatatirii timpului de cutarea informatiei. El va trebui sa respecte urmatoarea proprietate:

pentru oricare nod n, fiecare din descendentii din subarborele din stanga va avea valoarea informatiei mai mica decat a nodului n

fiecare din descendentii din subarborele din dreapta va avea valoarea informatiei mai mare decat a nodului n.

Exemplu:

in figura de mai sus avem 2 arbori binari.

Arborele din figura b) este arbore binar de cautare deoarece este respectata regula de mai sus, si anume ca in oricare subarbore stang valorile informatiilor (cheilor) rebuie sa fie mai mici decat ale radacinii si in oricare subarbore dreapta, valorile trebuie sa fie mai mari decat ale radacinii. (Cu alte cuvinte, toate valorile informatiilor din nodurile aflate in stanga nodului n trebuie sa fie mai mici, iar cele din dreapta mai mari).

Se foloseste exprimarea „oricare din subarborii” stang respectiv drept, deoarece pentru radacina 7, elementele subarborelui stang sunt 3, 1, 5, 4, care sunt toate mai mici decat 7, iar elementele subarborelui drept sunt 11, 10, 15, care sunt toate mai mari decat 7. Daca in schimb vom considera ca radacina nodul 3, vom avea ca subarbore stang nodul 1 (1 este mai mic decat 3), iar ca subarbore drept nodurile 5 si 4 (ambele mai mari decat 3).

Daca vom considera ca si radacina pe nodul 10, acesta nu are nici un copil, deci implicit respecta regula pentru arborii binari de cautare.

Arborele din figura a) nu este un arbore binar de cautare deoarece nu toate nodurile respecta regula.

Nodul 4 nu are ce cauta acolo in dreapta nodului 8. Ar trebui sa se afle in stanga lui 8 (4<8). Daca privim mai sus observam ca nodul 4 ar trebui sa se afle si in stanga nodului 10, si in stanga nodului 9, si in stanga nodului 7. Cu alte cuvinte nodul 4 nu are ce cauta in subarborele drept. Unde ar trebui sa fie pozitionat astfel incat si arborele din figura a) sa fie arbore binar de cautare?

3. Crearea si inserarea unui nod intr-un arbore binar de cautare

Vom considera arborele din dreapta. Sa presupunem ca dorim sa inseram nodul cu valoarea 62. Acesta se va insera ca nod frunza. Pentru a-l insera va trebui sa cautam o pozitie in arbore care respecta regula de integritatea a arborilor binari de cautare. Vom incepe prin compararea nodului de inserat (62), cu radacina arborelui (90). Observam ca este mai mic decat ea, deci va trebui inserat undeva in subarborele stang al acesteia. Vom compara apoi 62 cu 50. Din moment ce 62 este mai mare decat 50, nodul 62 va trebui plasat undeva in subarborele drept al lui 50. Se compara apoi 62 cu 7 Deoarece 75 este mai mare decat 62, 62 trebuie sa se afle in subarborele din stanga al nodului 75 Dar 75 nu are nici un copil in partea stanga. Asta inseamna ca am gasit locatia pentru nodul 62. Tot ceea ce mai trebuie facut este sa modificam in nodul 75 adresa catre copilul din stanga, incat sa indice spre 62.

Prin crearea unui arbore binar de cautare (A.B.C.) vom intelege de fapt crearea radacinii, restul nodurilor fiind adaugate prin operatia de inserare.

Implementare :

//programul va primi ca parametru numarul pe care trebuie sa il adauge

void inserare_nod(int wnrnod)

else

else

}// sfarsit while(nod2!=NULL)

// dupa gasirea nodului parinte,se creeaza legatura

// nod3 (nod parinte) cu nod1 (nodul fiu de inserat)

if(wnrnod<nod3->nrnod)

else

//sfarsit if(wnrnod<nod3->nrnod)

}// sfarsit if(primul_nod==NULL)

return;

4. Parcurgerea unui Arbore (Listarea)

Exista 3 tipuri de parcurgere a unui arbore:

inordine,

preordine

post ordine.

Aceste denumiri corespund modului cum este vizitata radacina.

Parcurgerea in preordine:

Parcurgerea in inordine se bazeaza pe urmatorul principiu: se va vizita mai intai radacina, copilul (copiii) din stanga, iar apoi copilul (copiii) din dreapta.

Implementarea se va face recursiv, astfel incat nu ne intereseaza ce se intampla decat pe unul din nivele (de exemplu pe primul), pe restul procedandu-se identic.

Fie arborele din figura:

Parcurgerea in preordine presupune:

- se va vizita radacina 90

- se viziteaza copilul din stanga (50). Dar acesta este la randul sau radacina pentru subarborele 20 – 7 Fiind radacina, ea se viziteaza prima. Deci vizitam si nodul 50.

- se viziteaza copilul din stanga al nodului radacina 50, adica nodul 20. Si acesta este radacina pentru subarborele 5 – 2 Fiind radacina, se va vizita si nodul 20.

- se viziteaza copilul din stanga al radacinii 20, adica nodul Si acesta este radacina pentru arborele vid. Il vizitam.

- cum pe ramura aceasta nu mai avem ce vizita, ne intoarcem la radacina 20. Aceasta este deja vizitata. La fel si copilul din stanga. Vom vizita copilul din dreapta, nodul 2

- nodul 25 nu mai are copii, deci nu mai avem ce vizita sub el. Cum pentru nodul radacina 20 am vizitat si copilul din stanga si copilul din dreapta, vom mai urca un nivel la nodul radacina 50. Pentru acesta tocmai am terminat de vizitat subarborele stang.

- Mai avem de vizitat subarborele drept. Vom merge la nodul 7 Nodul 75 este radacina pentru un alt subarbore. Il vizitam.

- mergem la copilul din stanga, nodul 66.

- cum nodul 66 nu mai are copii, revenim la radacina 75, pentru care vom vizita copilul din dreapta: nodul 80

- pentru radacina 75 am vizitat tot ce se putea. Urcam la radacina 50. Si pentru aceasta am vizitat tot ce se putea. - Urcam la radacina 90. Aici tocmai am terminat de vizitat subarborele stang. Mai avem de vizitat subarborele drept.

- Vom merge la nodul 150. El este radacina pentru subarborele 95 – 175, deci il vizitam

- vizitam copilul sau din stanga, 95

- Ne intoarcem la radacina 150. Vizitam copilul din dreapta, 175

- ne intoarcem la radacina 90, pentru care am terminat de vizitat si subarborele drept. Cum nu mai exista nici un nivel deasupra sa, am terminat de vizitat tot arborele.

Vizitarea arborelui va intoarce vectorul:

Desi la prima vedere pare destul de complicat, implementarea este destul de simpla. Se va folosi o functie Preordine care primeste ca parametru initial radacina arborelui (respectiv, prin apelari succesive, radacinile subarborilor)

// functia de parcurgere in preordine a arborelui creeat

void preordine(nod *radacina)

In urma parcurgerii in preordine se obtine urmatorul vector de parcurgere :

Parcurgerea in inordine

Parcurgerea in inordine presupune vizitarea mai intai a copilului din stanga, apoi vizitarea radacinii si mai apoi a copilului din dreapta.

Pentru arborele anterior, se procedeaza astfel:

se porneste de la radacina 90. Pentru aceasta se viziteaza mai intai copilul din stanga, nodul 50. Si acesta este la randul lui o radacina pentru arborele 20 - 7

De aceea vom vizita mai intai copilul sau stang, nodul 20, care la randul sau este radacina pentru arborele 5 – 2 Vom vizita mai intai copilul stang, nodul

pentru nodul 5 nu mai avem ce vizita. Revenim la radacina 20, pentru care tocmai am vizitat                                      subarborele stang. Conform definitiei, o vizitam pe ea.

vizitam nodul 25, copilul sau drept.

revenim la radacina 20. Nu mai avem ce vizita pe acest nivel. Urcam la radacina 50. Pentru aceasta am vizitat subarborele stang. Este randul ei sa o vizitam.

- Vom vizita apoi subarborele ei drept, dupa modelul anterior

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

In final se va obtine parcuregerea:

5 – 20 – 25 – 50 – 66 – 75 – 80 – 90 – 140 – 150 – 175

Se observa faptul ca parcurgerea in inordine va afisa de fapt vectorul ordonat crescator.

Implementarea algoritmului pentru parcurgerea in ordine :

// functia de parcurgere in ordine a arborelui creeat

void inordine(nod *radacina)

In urma parcurgerii in ordine se obtine urmatorul vector de parcurgere, ordonat crescator :

5 – 20 – 25 – 50 – 66 – 75 – 80 – 90 – 95 – 150 – 175

Parcurgerea in postordine

Pentru parcurgerea in postordine, se va vizita mai intai subarborele stang, apoi subarborele drept si de abia ultima data radacina.

Implementarea algoritmului pentru parcurgerea in postordine :

// functia de parcurgere in postordine a arborelui creeat

void postordine(nod *radacina)

In urma parcurgerii in postordine se obtine urmatorul vector de parcurgere :

5 – 25 – 20 – 66 – 80 – 75 – 50 – 95 – 175 – 150 - 90

Stergerea unui nod dintr-un arbore binar de cautare

Ideea de baza pentru stergerea unui nod dintr-un arbore astfel incat sa se pastreze structura de arbore binar de cautare este sa inlocuim nodul care se doreste sa se stearga cu cel mai din stanga nod, al subarborelui drept al nodului de sters.

Pentru stergerea unui nod avem urmatoarele cazuri: Cazul I Dorim sa stergem nodul 50. Acesta nu are subarbore drept, asa ca il vom inlocui pur si simplu cu nodul 20. Cazul II Dorim sa stergem nodul 150. Subarborele drept nu contine decat nodul 175 Nu exista un subarbore stang al subarborelui drept. Se va inlocui nodul 150 cu 17 Cazul III Dorim sa stergem nodul 50. Deoarece subarborele drept al nodului 50 contine un subarbore stang, se va alege cel mai din stanga nod al subarborelui drept a lui 50. Acest cel mai din stanga nod va contine cel mai mic numar mai mare decat nodul de sters. In cazul nostru acest nod este 66.

Prezentam in continuare implementarea algoritmului de mai sus. Functia de stergere va primi ca parametru informatia care dorim sa o stergem (numarul de sters) si va returna 1 in cazul in care s-a facut stergerea sau 0 in cazul in care informatia care dorim sa o stergem din arbore, nu a fost gasita (dorim sa stergem nodul 1000?).

int stergere_nod(int wnrnod)

// sfarsit while (tmp1->nrnod != wnrnod)

tmp = tmp1;

// cazul I: nu exista legatura spre dreapta

if (tmp1->adr_leg_dreapta==NULL)

else

//cazul II: nu avem copil stanga

if (tmp1->adr_leg_stanga == NULL)

// cazul III:

else

// sfarsit while (tmp->adr_leg_stanga != NULL)

tmp1->nrnod = tmp->nrnod;

tmp2->adr_leg_stanga = NULL;

delete tmp;

}//end else

return 1;

6. Stergerea nodurilor unui subarbore dintr-un arbore binar de cautare

In acest caz se urmareste stergerea tuturor ramurilor legate de un anumit nod cautat. Pentru a realiza o astfel de stergere se cauta nodul precizat prin parcurgerea arborelui incepand cu nodul radacina. Cand s-a identificat nodul respective se atribuie adreselor de legatura ale acestuia, adr_leg_stanga si adr_leg_dreapta, valorile NULL.

Implementarea algoritmului unei asemenea stergeri este urmatoarea:

int stergere_subarbore(int wnrnod)

tmp = tmp1;

// se sterge un subarbore prin setarea adreselor de legaturi la valoarea NULL

if (tmp1->nrnod==wnrnod)

return 0;

Exemplul 4. Printr-un meniu adecvat, sa se realizeze urmatoarele operatii:

Crearea unui arbore binar prin operatii de inserare successive

Stergerea unui nod al arborelui care nu are o ramificatie

Stergerea subarborelui unui nod oarecare

Parcurgerea in preordine a arborelui creat cu afisarea vectorului de parcurgere

Parcurgerea in ordine a arborelui creat cu afisarea vectorului de parcurgere

Parcurgerea in postordine a arborelui creat cu afisarea vectorului de parcurgere

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#include<malloc.h>

struct nod

nod *primul_nod;

int i,numar_noduri;

int vector_parcurgere[100];

void inserare_nod(int wnrnod)

else

else

}// sfarsit while(nod2!=NULL)

// dupa gasirea nodului parinte,se creeaza legatura

// nod3 (nod parinte) cu nod1 (nodul fiu de inserat)

if(wnrnod<nod3->nrnod)

else

// sfarsit if(wnrnod<nod3->nrnod)

}// sfarsit if(primul_nod==NULL)

return;

int stergere_subarbore(int wnrnod)

// sfarsit while (tmp1->nrnod != wnrnod)

tmp = tmp1;

// se sterge un subarbore prin setarea adreselor de legaturi la valoarea NULL

if (tmp1->nrnod==wnrnod)

// sfarsit if (tmp1->nrnod==wnrnod)

return 0;

int stergere_nod(int wnrnod)

// sfarsit while (tmp1->nrnod != wnrnod)

tmp = tmp1;

// cazul I: nu exista legatura spre dreapta

if (tmp1->adr_leg_dreapta==NULL)

else

//cazul II: nu avem copil stanga

if (tmp1->adr_leg_stanga == NULL)

// cazul III:

else

tmp1->nrnod = tmp->nrnod;

tmp2->adr_leg_stanga = NULL;

delete tmp;

}// sfarsit if (tmp1->adr_leg_dreapta==NULL)

return 0;

// functia de parcurgere in preordine a arborelui creeat

void preordine(nod *radacina)

// functia de parcurgere in ordine a arborelui creeat

void inordine(nod *radacina)

// functia de parcurgere in postordine a arborelui creeat

void postordine(nod *radacina)

// functia principal main()

void main(void)

getch();

}

}