Arbori binari ordonati (ABO). Tehnici de cautare a unui nod, traversare si creare a ABO

1. Scopul lucrarii il constituie prezentarea structurii de arbore binar ordonat, in principal crearea ei si cautarea unui nod in aceasta structura, in implementarea dinamica a acesteia.

2. Aspecte teoretice

Prin arbore binar ordonat se intelege un arbore binar care are urmatoarea proprietate: parcurgand nodurile sale in inordine, secventa cheilor este monoton crescatoare (figura 3.1).

Asadar, avand un arbore binar ordonat si N un nod oarecare al sau cu cheia C, toate nodurile din subarborele stang al lui N au cheile mai mici sau egale cu C si toate nodurile din subarborele drept al lui N au chei mai mari sau egale decat C. De aici rezulta un procedeu foarte simplu de cautare a unui nod cu o cheie data intr-un arbore binar ordonat, si anume: incepand cu radacina, se trece la fiul stang sau la fiul drept dupa cum cheia cautata este mai mica sau mai mare decat cea a nodului curent. Numarul comparatiilor efectuate in acest caz este cel mult egal cu inaltimea arborelui.

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 _nodABO;

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. Daca nu este vid, pentru inserarea noului nod, adresa acestuia trebuie memorata in nodul care-i va fi parinte. Pentru a ajunge la acesta, trebuie intai sa-l cautam.

Cautarea unui nod este mai simpla la arborii binari ordonati decat la cei neordonati, intrucat nu este nevoie sa parcurgem arborele pana la gasire printr-una din metode (preordine, inordine, postordine). Pornim de la radacina si urmam un drum fara reveniri in arbore, in functie de cheia cautata.

In figura 3.2 este indicat drumul parcurs la cautarea nodului cu cheia 10 in arborele reprezentat in figura 3.1.

Cautarea se poate simplifica aplicand metoda fanionului si modificand structurile arborelui astfel incat orice referinta catre NULL se inlocuieste cu o referinta spre nodul fanion In figura 3.3 este reprezentat subarborele drept al arborelui din figura 3.1 implementat fara fanion, iar in figura 3.4 - implementat cu fanion.

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

Functiile urmatoare adauga un nod ce va avea cheia x in arborele cu radacina p, fara fanion, respectiv cu fanion.

void AdaugNod(struct _nodABO **p, int x)

else

void AdaugNod(struct _nodABO **p, int x)

else

Mai jos este prezentata cautarea fara fanion in varianta de functie nerecursiva, respectiv recursiva.

struct _nodABO *CautaNodNerec(struct _nodABO *p,

int x)

return p;

struct _nodABO *CautaNodRec(struct _nodABO *p,

int x)

return p;

Folosind fanion, inainte de inceperea cautarii, cheia nodului fanion se asigneaza cu valoarea cautata, x; astfel, va exista in arbore cel putin un nod cu acea cheie, si, in cel mai rau caz, nodul va fi gasit pe aceasta pozitie. Functiile de cautare in acest caz sunt urmatoarele:

struct _nodABO *CautaNodNerec(struct _nodABO *p,

int x)

return(p);

struct _nodABO *CautaNodRec(struct _nodABO *p,

int x)

3. Problema rezolvata

Se presupune ca multimea de studenti dintr-un an este memorata sub forma unei structuri de arbore binar ordonat, in functie de numele studentilor. Pentru fiecare student se cunosc notele la examenele din sesiune, dar media nu este calculata.

a)     Sa se calculeze media fiecarui student si sa se construiasca pe baza primului arbore, un al doilea arbore binar ordonat de data aceasta in functie de medie.

b)     Sa se caute si sa se afiseze in ordine alfabetica toti studentii cu medii intre doua valori date, folosind primul arbore.

c)      Sa se caute si sa se afiseze in ordine crescatoare a mediilor toti studentii cu medii intre doua valori date, folosind al doilea arbore.

Rezolvare

Arborele initial cuprinde toti studentii ordonati dupa nume (in ordine alfabetica). Acesta este traversat (functia ParcurgereABONume) in scopul calcularii mediei si al crearii celui de-al doilea arbore. Traversarea se face in inordine, pentru a respecta cerinta de la punctul a.

Pentru afisarea ceruta la punctul b, traversarea va cuprinde toate nodurile arborelui ordonat alfabetic (functia CautaAB), afisand doar pe cele care satisfac criteriul de medie cerut.

Pentru afisarea ceruta la punctul c, avand in vedere ca arborele al doilea este ordonat dupa medii, atunci cand in procesul de traversare se ajunge la un nod cu media mai mica decat pragul minim, nu mai are rost traversarea subarborelui sau stang. La fel, nu mai are rost traversarea subarborelui drept al unui nod cu media mai mare decat pragul maxim (functia CautaABO).

Pentru crearea arborelui initial se foloseste un fisier care contine numele si notele studentilor.

#include <stdio.h>

#include <conio.h>

#include <string.h>

#define nrEx 3

typedef struct _nodABOnodABO;

nodABO *radN, *radM;

FILE *f;

char s[100];

float vMin, vMax;

int note[nrEx];

//adaugarea in arbore alfabetic

void AdaugNodNume(nodABO **p)

else

//adaugare in arbore dupa medii

void AdaugNodMedii(nodABO **p, nodABO *q)

else

//crearea arborelui binar ordonat dupa nume din fisier

void CreareABONumeFis(void)

//calcularea mediei si construirea arborelui ordonat dupa medii

void ParcurgereABONume(nodABO *p)

//cauta si afiseaza alfabetic pe cei cu mediile intre cele doua valori

void CautaAB(nodABO *p)

//cauta si afis. in ordinea mediilor pe cei cu mediile intre cele doua valori

void CautaABO(nodABO *p)

//afisarea unui arbore

void Afisare(nodABO *p, int niv)

//stergerea subarborelui cu radacina indicata de p

void StergABO(nodABO *p)

int main(void)

CreareABONumeFis();

fclose(f);

ParcurgereABONume(radN);

printf('ARBORELE ORDONAT ALFABETIC:n');

Afisare(radN, 0);

printf('ARBORELE ORDONAT DUPA MEDII:n');

Afisare(radM, 0);

printf('Valoarea minima: ');

scanf('%f', &vMin);

printf('Valoarea maxima: ');

scanf('%f', &vMax);

printf('Lista din arborele alfabetic: '); CautaAB(radN);

printf('nLista din arborele pe medii: '); CautaABO(radM);

StergABO(radN); //stergerea arborelui ordonat dupa nume

StergABO(radM); //stergerea arborelui ordonat dupa medii

getch();

return 0;

4. Probleme propuse

4.1. Sa se modifice problema rezolvata astfel incat sa nu avem informatii in dublu exemplar, ci cei doi arbori sa contina aceleasi noduri (cu campuri de inlantuire separate pentru fiecare arbore). 

4.2. Sa se creeze un arbore binar odonat si sa se implementeze ca si functii urmatoarele operatii:

a)     stabilirea faptului ca doua chei date sunt in relatie stramos-descendent sau nu.

b)     afisarea nodurilor de pe un nivel dat.

c)      afisarea subarborelui a carui radacina este un nod dat.

d)     crearea unui alt arbore binar ordonat care sa contina numai nodurile cu chei mai mari decat o valoare data.

4.3. Se dau doua multimi A si B de chei, memorate sub forma unei structuri de arbore binar ordonat. Sa se implementeze operatiile de reuniune si de intersectie sub forma unor subrutine care, primind cele doua multimi date (respectiv pointerii catre arborii care contin cele doua multimi initiale), construieste si returneaza un pointer catre arborele reprezentand reuniunea, respectiv intersectia multimilor initiale.

4.4. Se considera un arbore binar ordonat cu chei siruri de caractere, dat initial. Sa se scrie programul prin care sa se determine nivelul (nivelurile) cu numarul maxim de noduri.

4.5. Se considera doi arbori binari ordonati, dati initial, cu chei de tip sir de caractere. Sa se scrie programul prin care se verifica daca cel de-al doilea arbore este un sub-arbore al primului arbore.

4.6. Dupa cum se stie, tehnica dispersiei utilizeaza in varianta cunoscuta o structura de lista simplu inlantuita pentru tratarea situatiei de coliziune (memorarea cheilor care conduc la acelasi indice de tablou prin intermediul functiei de dispersie). Sa se modifice aceasta implementare, utilizandu-se arbori binari ordonati in locul listelor inlantuite. Pe seturi de chei generate aleator, sa se compare performantele celor doua implementari.