Structura de arbore. Arbori binari

1. Scopul lucrarii il constituie prezentarea structurii de arbore binar, in principal crearea si traversarea sa, cu exemplificari pentru implementarea dinamica.

2. Aspecte teoretice. Arbori binari si implementarea lor dinamica

Prin arbore binar se intelege o multime de n noduri care daca nu este vida, contine un anumit nod numit radacina, iar restul nodurilor formeaza doi arbori binari disjuncti, numiti subarborele stang si subarborele drept.

2.1. Implementarea dinamica a arborilor binari

Fiecare nod trebuie sa contina, pe langa cheie si alte informatii specifice, adresele celor cel mult doi fii ai sai. Structura de date folosita in aceasta implementare este urmatoarea:

struct _nodAB;

Schematic, un arbore implementat cu aceste structuri se poate reprezenta astfel (se considera ca exemplu arborele prezentat in figura 2.1):

2.2. Crearea arborilor binari

Pentru adaugarea unui nou nod in arbore, acesta trebuie intai creat, apoi inserat in arbore. Pe langa acestea, mai trebuie initializate campurile cu informatii specifice nodului.

Daca arborele este vid, noul nod va fi radacina lui.

rad = new struct _nodAB;

scanf("%d", &rad->cheie);

rad->stang = NULL;

rad->drept = NULL;

Daca nu este vid, pentru inserarea noului nod, adresa acestuia trebuie memorata in nodul care-i va fi parinte. Functia de mai jos adauga un fiu stang nodului parinte dat, daca acesta nu are deja un fiu stang.

void AdaugNodStg(struct _nodAB *par)else

printf('%d are deja fiu stang.n', par->cheie);

2.3. Suprimarea unui nod 

Daca eventualii fii ai nodului de sters trebuie mutati spre alte noduri, prima data se face acest lucru, apoi putem sterge nodul.

Daca se cere stergerea nodului impreuna cu toti descendentii sai, atunci putem folosi o functie recursiva ca si cea de mai jos.

Referat: Contabilitatea tertilor Referat: Structurarea elementelor de activ si pasiv dupa criterii financiare

void StergAB(struct _nodAB *p)

2.4. Traversarea arborilor binari

Traversarea  arborilor binari se realizeaza analog traversarii arborilor obisnuiti. Astfel, considerand figura 2.3, unde R este radacina, iar A si B sunt subarborii stang, respectiv drept:

- traversarea arborelui in preordine inseamna traversarea radacinii R, urmata de traversarea subarborelui A, si apoi a subarborelui B (vizitarea radacinii inaintea subarborilor: R, A, B);

- ordonarea arborelui in inordine inseamna traversarea subarborelui A, urmata de traversarea radacinii R, si apoi a subarborelui B (A, R, B);

- ordonarea arborelui in postordine inseamna traversarea subarborelui A, apoi a subarborelui B urmata apoi de traversarea radacinii R (vizitarea radacinii dupa cei doi subarbori: A, B, R).

De exemplu, pentru arborele reprezentat in figura 2.1, traversarea acestuia in cele trei moduri are ca rezultat:

preordine A, B, D, G, E, H, I, C, F, J, K

inordine G, D, B, H, E, I, A, C, J, F, K

postordine: G, D, H, I, E, B, J, K, F, C, A

Functiile de mai jos traverseaza un arbore binar in cele trei moduri.

void Preordine(struct nodAB *p)

void Inordine(struct _nodAB *p)

void Postordine(struct _nodAB *p)

3. Problema rezolvata

Se da arborele genealogic (atat cat s-a putut reconstitui) al unei persoane. Se cere sa se afiseze ordonati pe generatii toti stramosii cunoscuti ai unei persoane din acest arbore, parcurgand arborele cel mult o data.

Rezolvare

Se utilizeaza in rezolvarea problemei un arbore binar in cadrul caruia stramosii unui anumit nod sunt marcati ca si fiii nodului respectiv. Astfel, daca persoana pentru care se doreste afisarea stramosilor se gaseste in arbore, se va considera in continuare doar cu subarborele a carui radacina este nodul corespunzator ei. Pentru afisarea pe generatii se foloseste o coada (adaugare la sfarsit, extragere de la inceput). Initial coada va avea doar un nod corespunzator persoanei cerute si ea constituie prima generatie parcursa. Parcurgerea unei generatii presupune prelucrarea nodurilor din coada corespunzatoare ei. Dupa prelucrarea unui nod, el va fi eliminat din coada. La fiecare generatie trebuie sa stim cate persoane sunt, altfel nu stim cand trecem la urmatoarea generatie. Pentru aceasta, la fiecare generatie numaram cate noduri din generatia urmatoare adaugam in coada.

Observatie de implementare: Presupunem numele persoanelor ca si cheie pentru noduri, deci, pentru identificarea lor exacta se cere sa nu existe persoane cu acelasi nume in datele de intrare.

#include <stdio.h>

#include <conio.h>

#include <string.h>

typedef struct _nodABnodAB;

typedef struct _coadacoada;

nodAB *rad;//radacina arborelui

coada *inc, *sf;//inceputul, respectiv sfarsitul cozii

char nume[100];

int i;

//adauga recursiv cate un nod in arbore

void AdaugNod(nodAB **p, int niv)

else *p = NULL;

//afis. arb. rotit cu 90 de grade in sens trigonometric(dr=tata, st=mama)

void AfisAB(nodAB *p, int niv)

void StergAB(nodAB *p)

//cauta un nod in arbore, traversandu-l in preordine

nodAB *Cauta(nodAB *nod)

}

return p;

//adauga un nod in coada (la sfarsitul cozii)

int AdaugInCoada(nodAB *p)

return 0;//nu am avut ce adauga(am adaugat 0 noduri)

//afisarea arborelui binar pe generatii

void AfisABGen()

//pregatirea pentru generatia urmatoare

cati = catiNou;

grad++;

}

void main(void)

else printf('Persoana %s nu se gaseste in

arbore.', nume);

getch();

}

}while(nume[0]!='0');

StergAB(rad);//stergerea arborelui

4. Probleme propuse

4.1. Sa se realizeze stergerea unui nod dintr-un arbore binar, astfel:

- daca a fost fiu stang sau radacina arborelui, in locul lui trece fiul sau stang, iar fiul sau drept devine fiu drept al celui mai din dreapta nod al fiului stang al nodului de sters.

- daca a fost fiu drept, in locul lui trece fiul sau drept, iar fiul sau stang devine fiu stang al celui mai din stanga nod al fiului drept al nodului de sters.

4.2. Se considera un arbore binar care reprezinta o expresie aritmetica. Nodurile terminale sunt numere pozitive, iar cele interne sunt operatorii aritmetici binari: +, -, * si /.

Daca expresia este corecta, sa se afiseze si sa se evalueze.

Exemplu: pentru arborele din figura 2.5, rezultatul executiei programului trebuie sa fie: 2*(3+2)/(4-6/3) = 5.