Arbori binari de cautare
1. Definitii
Un arbore este un graf orientat in care nu exista nici un ciclu(graf orientat aciclic)
Un arbore binar este o multime de n >= 0 noduri, care daca nu este vida, contine un nod numit radacina, restul nodurilor formand doi arbori disjuncti numiti subarborele stang si subarborele drept.
Aceasta structura de date e importanta pentru ca e usor de reprezentat si
prelucrat, orice arbore putand fi transformat in arbore binar .
2. Transformarea unui arbore generalizat in arbore binar
Un arbore generalizat poate fi transformat intr-un arbore binar, astfel incat secventele de noduri pentru parcurgerea in preordine sa fie identice in cazul ambilor arbori.
Un arbore generalizat A cu radacina A1 si subarborii A1,1, A1,2, ,A1,k se transforma in arbore binar avand radacina A1, A1,1 fiul sau stang, iar A1,i devin fiii drepti ai lui A1,i-1 pentru 2<=i<=k.
Secventele de
noduri in parcurgerea in preordine a arborelui generalizat si a celui binar
obtinut prin transformare, sunt identice.
Exemplu: Se considera arborele generalizat de mai sus.
Aplicand regula descrisa, se obtine arborele binar reprezentat.
Implementarea arborilor binari
Un arbore binar poate fi descris cu ajutorul urmatoarei structuri de date dinamice:
typedef struct informaties;
typedef struct arborenod;
nod*prim,*prim1;
3. Operatorii arborelui binar
INITIALIZEAZA(A) - face vid arborele A;
INSEREAZA(X,A) - insereaza cheia X in arborele A;
CAUTA(X,A) - cauta cheia X, returnand true la gasire;
SUPRIMA(X,A) - suprima cheia X, daca exista;
TRAVERSEAZA(A) - parcurge toate cheile arborelui A
4. Arbori binari de cautare- Creare
Se numeste arbore de cautare un arbore binar ale carui noduri au o cheie de identificare, iar pentru fiecare nod sunt valabile proprietatile urmatoare:
Cheile de identificare sunt distincte.
Fie arborele din figura urmatoare. Cheile sunt : 30, 21 , 27, 15, 37, 31, 33, 36, 35, 24
Observatie: ordinea de inserare a cheilor poate determina o alta configuratie pentru arbore. Spre exemplu daca se insereaza mai intai 30 si apoi 27 si 21 atunci 27 va deveni subordonat stang pentru 30 si 21 subordonat stang pentru 27.
Crearea arborilor de cautare se realizeaza aplicand de un numar de ori operatia de inserare. Inserarea se realizeaza astfel:
-se compara valoarea k de inserat cu cheia asociata nodului curent. Exista urmatoarele posibilitati:
- cheia coincide cu valoarea de inserat si se renunta la inserare
- cheia este mai mica decat k caz in care se incearca inserarea in subarborele drept
- cheia este mai mare decat k caz in care se incearca inserarea in subarborele stang
- inserarea propriuzisa se realizeaza atunci candsubarborele stang , respectiv drept, este vid, altfel se reia.
Parcurgerea arborilor de cautare se face ca orice arbore binar (svd, vsd sdv).
Cautarea unei valori se determina in mod similar cu subprogramul de inserare.
5. Parcurgerea arborilor binari
Operatiile de parcurgere a arborilor binari se simplifica mult daca vom considera ca fiecare nod al arborelui subordoneaza un subarbore binar stang si un subarbore binar drept. Avand in vedere aceasta observatie se vor defini subprograme recursive care utilizeaza tehnica Divide et Impera.
Principalele modalitati de parcurgere ale unui arbore binar sunt:
A) Arborii binari pot fi parcursi prin metode specifice grafurilor: in adancime, latime.
B) Metode specifice arborilor binari :
Solutiile de parcurgere ale arborelui din figura urmatoare :
|
|
parcurgere sVd - in inordine 4 2 5 1 6 3 7 8 parcurgere Vsd - in preordine 1 2 4 5 3 6 7 8 parcurgere sdV - in postordine 4 5 2 6 8 7 3 1
|
6. Stergerea unui nod dintr-un arbore binar ordonat
In urma suprimarii unui nod avand cheia x dintr-un arbore binar ordonat, acesta trebuie sa ramana ordonat.
Cazurile ce se disting sunt functie de numarul de fii ai nodului ce se suprima. Daca numarul fiilor este:
o se demonstreaza ca acesta exista si nu are fiu drept; se gaseste construind secventa formata din fiul stang al nodului de suprimat si apoi fiii drepti pana la cel ce nu are descendent drept;
o se asigneaza toate campurile de informatie ( nu de inlantuire ) ale nodului de suprimat cu cele ale predecesorului sau;
o se suprima predecesorul ( nu are fiu drept ).
Cazul suprimarii unui nod care are doi fii este ilustrat intr-ul mod general in figura.
- Aplicatie -
Baza de date cu personalul unei firme
Sa se realizeze un program in limbajul C++ care sa poata crea o baza de date cu personalul unei firme. Fiecare inregistrare va avea campurile cod angajat, nume, prenume, adresa si salariul de baza. Programul va trebui sa realizeze adaugari, stergeri, afisarea bazei de date, cautarea unui anume angajat.
1. Descrierea metodei
Pentru realizarea programului se va folosi un arbore binary de cautare, in care cheia va fi campul cod, codul angajatului(cheia este campul dupa acre se va face introducerea datelor in arbore).
Structura folosita pentru realizarea fiecarui nod al arborelui este urmatoarea:
typedef struct informaties1;
typedef struct nodurinod;
Programul va contine un meniu cu ajutorul caruia utilizatorul va putea selecta una din optiunile descrise de acesta.
Vom avea 2 tipuri de creari. Primul tip va fi o creare normala, cu introducerea de la tastatura a datelor, prin acest fel creandu-se o baza noua de date. Al doilea mod de creare este dat de citirea datelor din fisierul "personal.txt" acesta putand fi creat fie direct de catre utilizator, fie este creat de program, dup ace acesta a mai fost rulat prin selectarea ultimei optiuni, aceea de a salva datele in fisier.
Crearea se va face dupa metoda descrisa in capitolul I , si anume vom crea mai intai nodul radacina, si apoi se vor adauga in arbore celelalte inregistrari, in functie de codul acestora in stanga sau in dreapta, ajuntanddu-ne de functia cauta() , in care se va si adauga nodul cel nou si se vor face legaturile necesare.
Toate celelalte operatiuni vor fi realizate de functii, pe care le vom descrie mai jos.
2. Functiile programului. Descrierea lor
Void cautare(nod *unu, nod *altu)
Este o functie recursiva, folosita pentru a ajuta la crearea arborelui, indiferent ce metoda se va alege. Functia va parcurge arboreal, pana va gasi pozitia unde trebuie adaugat un nod nou, si va face lagaturile pentru legarea acestuia la arbore. Campul care va conditiona pozitionarea nodului va fi campul cod.
Nod *creare()
Este o functie care va returna in final valoarea nodului radacina al arborelui, si care va apela in interiorul ei functia descrisa mai sus. Pentru creare se vor cere introducerea datelor de la tastatura.
Nod *creare_fis()
La fel ca si cealalta functie de creare, va returna adresa nodului radacina, insa citirea datelor se va face din fisierul "personal.txt". Dupa crearea separata a primului nod, care va fi si radacina, pana se va termina fisierul, se vor citi datele pentru un singur nod si se va apela cautare(.) care va introduce nodul in arbore.
Void afis(nod *temp)
Este o functie recursive cu un singur parametru, care va parcurge arborele in INORDINE(Stanga - Radacina - Dreapta) si va afisa pe ecran continutul intregulu arbores au cu alte cuvinte, continutul bazei da date a personalului firmei.
Nod *stergere( *temp)
Este functia care va realize stergerea unui nod din arbore. Se va citi mai intai codul angajatului care se vrea a fi sters, care va fi primit ca parametru prin variabila temp , iar stergerea acestuia se va efectua in functie de pozitionarea acestuia in arbore, metoda fiind prezentata la capitolul I.
Void cautare(nod *prim, nod *nou)
Void inserare()
Aceste 2 functii adauga un nou nod in arbore, adica o noua persoana in baza de date. Principiul in mare este acelasi ca la creare, se vor citi datele aferente noii inregistrari, si se va cauta unde trebuie introdus acesta. Dupa introducerea acesteiintregistrari se va intra in pagina de meniu a programului.
Void cautarecod(nod *temp, int nr)
Efectueaza cautarea unui nod in arbore, prin cheia acestuia, primita ca papametru prin variabila nr, variabila care va fi citita de la tastatura. Procedeul este urmatorul: se va parcurge arborele pentru cautare, si daca acesta va fi gasit se va afisa pe ecran toate datele despre acea persoana, altfel se va afisa ca acel cod nu exista in baza de date.
Void salvare(nod *t)
Este functia cu ajutorul careia se vor salva toate informatiile in fisierul "personal.txt", acestea aparand in fisier in ordinea in care vor fi citite in cazul selectarii de creare din fisier.
Programul C++
#include<stdio.h>
#include<string.h>
#include<conio.h>
typedef struct informaties1;
typedef struct nodurinod;
#define ESC 27
int ok=1,ok1=1;
nod*prim,*temp,*prim1,*t,*nou;
int x,nr;
FILE *m;
char y[100];
void cautare(nod*unu,nod*altu)
else
}
nod *creare()
printf('nn ESC Exit ENTER Continue');
}
while (ch!=ESC);
return prim;
}
nod *creare_fis()
fclose(f);
return prim;
}
void afis(nod*temp)
}
getch();
}
nod *stergere(nod*temp)
stergere(temp->dr);
}
}
return prim1;
}
void cautare1(nod*prim,nod*nou)
else
}
}
else
}
}
void inserare()
void cautare2(nod*prim1,nod*t)
else
}
nod *aux(nod*temp)
aux(temp->dr);
}
return prim1;
}
void salvare(nod*t)
}
void cautarecod(nod*temp,int nr)
cautarecod(temp->dr,nr);
}
}
getch();
}
void main()
else f=prim->stg;
delete prim;
prim=f;
temp=f;
}
else
break;
}
case '6':
case '7':
break;
}
}
}
while(ch!=ESC);
getch();
}
