ARBORI BINARI DE CAUTARE

NOTIUNI INTRODUCTIVE

Definitie. Se numeste graf orientat perechea ordonata G = (X, U), unde X = si U X x X .

Elementele x_i X se numesc noduri.

Elementele (x_i , x_j) U se numesc arce.

Definitie. Fiind date doua noduri i si j ale unui graf orientat, se spune ca exista un lant de la i la j daca exista o succesiune de arce, indiferent de sensul lor prin care cele doua noduri sunt unite.

Definitie. Un graf orientat G = (X, U) este conex daca , exista un lant de la i la j.

Definitie. Un graf orientat este arbore daca este conex si nu admite cicluri.

Definitie. Un graf orientat G = (X, U) admite o radacina daca pentru orice exista un drum de la v la x.

Definitie. Se numeste arborescenta un graf orientat care indeplineste simultan doua conditii :

1.     Este arbore.

2.     Admite radacina.

Observatie. Intr-o arborescenta radacina este unica. Radacina se mai numeste si varf.

In cazul in care arborescenta are cel mult doi descendenti, unul stang si unul drept, spunem ca avem un arbore binar.

Observatie. In cazul unui arbore binar se considera ca sensul arcelor este implicit, motiv pentru care nu se mai reprezinta grafic.

Exemplu : mai jos se gaseste o arborescenta care are radacina 1 si care este arbore binar. Alaturat, se observa modul in care se reprezinta grafic, renuntand la sensurile arcelor, care sunt implicite.

Nodurile sunt asezate pe mai multe niveluri. Radacina este pe nivelul 0, descendentii directi ai radacinii sunt pe nivelul 1, descendentii directi ai nodurilor de pe nivelul 1 sunt pe nivelul 2, s.a.m.d.

Numarul de niveluri, mai putin cel al radacinii, ocupate de nodurile grafului, se numeste adancimea arborelui binar.

Observatie. Se va face o distinctie intre descendentul stang si cel drept. De exemplu, arborii de mai jos sunt considerati distincti.

MODALITATI DE REPREZENTARE A ARBORILOR BINARI

Arborii binari pot fi reprezentati ca orice graf orientat,dar aceasta forma este deosebit de greoaie in aplicatii,de aceea s-a recurs la alte reprezentari mult mai convenabile.

1.    REPREZENTAREA CU AJUTORUL VECTORILOR

Un arbore binar poate fi reprezentat cu ajutorul a doi vectori, care se vor numi st (stanga) si dr (dreapta). Pentru fiecare nod i din cele n, st[i] retine numarul de ordine al nodului stang subordonat de i , iar dr[i] retine numarul de ordine al nodului drept subordonat de i.

Daca nu exista nod subordonat, se retine 0.

Exemplu: Urmatorul arbore binar cu 7 noduri, se reprezinta astfel:

ST

1 234 5 67

DR

123 45 67

2.    REPREZENTAREA IN HEAP

Fiecare nod al arborelui este reprezentat in HEAP de o inregistrare cu urmatoarea structura (in limbajul de programare C++) ׃

Programul C va retine doar adresa radacinii (virfului).

3.    REPREZENTAREA CU AJUTORUL LEGATURII DE TIP TATA

Arborele se reprezinta sub forma unui vector t cu n componente. Daca nodul i este descendent al nodului k atunci t[i] = k. Daca nodul i este radacina, t[i] = 0.

Exemplu. Pentru arborele binar anterior avem urmatoarea reprezentare cu ajutorul legaturii de tip tata:

MODALITATI DE PARCURGERE A ARBORILOR BINARI

In scopul prelucrarii,este necesar ca nodurile arborilor binari sa fie vizitate.

Exista mai multe modalitati de parcurgere a arborilor binari care difera prin ordinea de vizitare a nodurilor.

Se considera ca fiecare nod al arborelui subordoneaza un subarbore binar stang si un subarbore binar drept.

Principalele modalitati de parcurgere ale unui arbore binar sunt :

Parcurgerea in inordine (SVD). Se va parcurge mai intai subarborele stang, apoi varful, apoi subarborele drept.

Parcurgerea in preordine (VSD). Se va parcurge mai intai varful, apoi subarborele stang, apoi cel drept.

Parcurgerea in postordine (SDV). Se va incepe cu parcurgerea subarborelui stang, apoi cel drept, apoi varful.

Parcurgerea in latime : se parcurge radacina, apoi nodurile de pe nivelul 1, apoi cele de pe nivelul 2,etc.

inordine SVD :

4 2 1 5 7 3 6

preordine VSD :

1 2 4 3 5 7 6

postordine SDV :

4 2 7 5 6 3 1

latime :

1 2 3 4 5 6 7

Programul urmator citeste si parcurge in inordine, preordine, postordine un arbore binar. Acesta este retinut in HEAP. Pentru a marca faptul ca descendentul unui nod lipseste se introduce 0.

#include<iostream.h>                 void svd(Nod *c)

struct Nod ; cout<<c->nr;

Nod *c; svd(c->dr);

}

void vsd(Nod *c) void sdv(Nod *c)

}

}}

Nod * arb( ) main( )

c->st=arb( );

c->dr=arb( );

return c;

}

}

Nodurile arborelui se introduce in ordinea :

1 2 4 0 0 0 3 5 0 7 0 0 6 0 0

Atat pentru introducerea informatiilor despre arbore,cat si pentru parcurgeri s-au utilizat tehnici recursive care decurg din tehnica Divide et Impera !

Programul urmator efectueaza aceleasi parcurgeri ca si precedentul, numai ca arborele binar este reprezentat cu ajutorul vectorilor.

#include<iostream.h>

int st[50], dr[50], n, i, v;

void sdv(int nod) void vsd(nod)

}

}

void svd(nod)   void citire( )

cin>>st[i];

} cout<<”dr[”<<i<<”]=”;

cin>>dr[i];

} }

void main( )

ARBORI DE CAUTARE

Definitie. Se numeste arbore de cautare un arbore binar ale carui noduri au o cheie de identificare, iar pentru fiecare nod avem proprietatile urmatoare:

Orice cheie asociata unui nod al subarborelui stang este mai mica decat cheia asociata nodului;

• Orice cheie asociata unui nod al subarborelui drept este mai mare decat cheia asociata nodului.

Cheile de identificare sunt distincte.

Consideram ca arborele binar de cautare este reprezentat in HEAP de o inregistrare cu urmatoarea structura:

INSERAREA

Crearea arborilor de cautare se face aplicand de un numar de ori operatia de inserare. Regula de inserare este urmatoarea. Se compara cheia asociata inregistrarii care se insereaza. Exista 3 posibilitati:

Cheia coincide cu numarul - se renunta la inserarea acelui numar;

Cheia este mai mare decat numarul – se incearca inserarea in subarborele stang;

Cheia este mai mica decat numarul – se incearca inserarea in subarborele drept.

LISTAREA

Informatia se poate lista utilizand oricare din metodele cunoscute pentru parcurgerea arborilor. Daca se doreste listarea informatiilor in ordinea strict crescatoare a cheilor se utilizeaza metoda stang – varf - dreapta (inordine).

CAUTAREA

Regula de cautare este urmatoarea:

Daca arborele este nevid, atunci avem posibilitatile urmatoare:

Valoarea coincide cu cheia varfului – valoarea exista in arbore;

Valoarea este mai mica decat cheia asociata varfului – se reia problema pentru subarborele stang;

Valoarea este mai mare decat cheia asociata varfului – se reia problema pentru subarborele drept.

Altfel

Nu exista in arbore o cheie egala cu valoarea data.

STERGEREA

Daca arborele este nevid atunci avem posibilitatile urmatoare:

Valoarea coincide cu cheia varfului – valoarea exista in arbore;

Daca nodul este terminal (subarborii stang si drept sunt vizi), acesta este sters, iar adresa retinuta de parinte pentru el va fi nula.

Daca numai subarborele drept este nevid, nodul este sters, iar parintele lui va retine, in locul adresei lui, adresa subarborelui drept.

Daca subarborele stang este nevid, nodul este sters, iar parintele lui va retine, in locul adresei lui, adresa subarborelui stang.

Daca ambii subarbori sunt nevizi:

Se identifica cel mai din dreapta nod al subarborelui stang;

Cheia nodului astfel identificat va fi memorata de nodul analizat;

Nodul astfel identificat se sterge, iar stergerea se efectueaza ca in cazul in care nodul subordoneaza numai subarborele stang.

Valoarea este mai mica decat cheia asociata varfului – se reia problema pentru subarborele stang;

Valoarea este mai mare decat cheia asociata varfului – se reia problema pentru subarborele drept.

Altfel

Nu exista in arbore o cheie egala cu valoarea data.

Exemple de stergeri

1.     In arborele alaturat se sterge nodul 8. Acesta este nod terminal.

2.     In arborele alaturat se sterge nodul 9. Acesta subordoneaza un singur subarbore nevid, cel drept.

3.    

In arborele alaturat se sterge nodul 3. Arborele subordoneaza 2 arbori nevizi. Cel mai din dreapta nod din subarborele stang are cheia 4. Cheia este copiata la nodul 3, iar nodul astfel identificat este sters.

4.    

In arborele alaturat se sterge nodul 7. In subarborele stang, cel mai din dreapta nod are cheia 4. Cheia sa va fi retinuta de nodul care avea cheia 7, iar nodul cu cheia 4 este sters.

Subprogramul cmmd efectueaza toate operatiile corespunzatoare cazului de stergere atunci cand nodul are ambii subarbori (cel stang si cel drept) nevizi:

APLICATIE

ENUNT

Sa se realizeze o aplicatie care gestioneaza stocul unui magazin. Aplicatia va efectua urmatoarele operatii:

• Introducerea informatiilor despre un produs (denumire, unitate de masura, pret, TVA, cantitate, valoare totala);
• Stergerea unui produs din baza de date a magazinului;
• Vanzarea unui produs din stocul magazinului;
• Listarea in ordine alfabetica a produselor din magazin;
• Listarea contorizata a produselor aflate pe stoc si numarul acestora;
• Listarea contorizata a produselor aflate pe stoc zero si numarul acestora;
• Listarea contorizata a produselor care au valoarea totala mai mare decat 10000 lei;
• Listarea contorizata a produselor in ordinea crescatoare a pretului;
• Afisarea valorii totale a stocului aflat in magazin;
• Iesirea din program.

Pentru implementarea informatiilor despre produsele aflate in stocul magazinului se va crea un arbore binar de cautare in care inserarea unui nod se va face astfel incat la parcurgerea in inordine a arborelui sa se poata obtina lista alfabetica a produselor.

REZOLVAREA PROBLEMEI

Aplicatia se va realiza in limbajul de programare C++.

Despre un produs se cunosc urmatoarele informatii:

o      Denumirea produsului;

o      Unitatea de masura a produsului;

o      Pretul produsului;

o      TVA-ul produsului;

o      Cantitatea de produse;

o      Valoarea totala a produsului;

Nodurile arborelui de cautare au urmatoarea structura:

struct arbore ;

unde info este campul care contine informatia din nod (informatii despre un elev), iar as, ad contin adresa subarborelui stang, respectiv adresa subarborelui drept.

Campul info este de tipul definit produs a carui structura este urmatoarea:

struct produs;

unde denumire memoreaza denumirea produsului, um memoreaza unitatea de masura, pret memoreaza pretul produsului, tva memoreaza TVA-ul produsului, cantitate memoreaza cantitatea de produse, iar total memoreaza valoarea totala a produsului.

Inserarea unui nod in arborele de cautare ce are ca radacina pe RAD se face dupa denumirea produsului astfel incat la o parcurgere in inordine a arborelui sa obtinem lista alfabetica a produselor. Acest lucru este realizat de functia inserare care are urmatoarea definitie:

void inserare(arbore *&c,produs e)

Inserarea unui nod in arborele de cautare ce are ca radacina pe RAD1 se face dupa pretul produsului astfel incat la o parcurgere in inordine a arborelui sa obtinem lista produselor in ordinea crescatoare a pretului. Acest lucru este realizat de functia inserare1 care are urmatoarea definitie:

void inserare1(arbore *&c,produs e)

else

Listarea diferitelor rapoarte, adaugarea de noi produse se efectueaza prin prelucrarea celor 2 arbori de cautare.

SURSA PROGRAMULUI C++

#include<fstream.h>

#include<string.h>

#include<conio.h>

#include<stdio.h>

#include<ctype.h>

struct produs;

struct arbore;

ofstream fo('MAGAZIN.DAT');

arbore * RAD, *RAD1;

// cheia principala este denumirea produsului (ordine alfabetica)

void inserare(arbore *&c,produs e)

// cheia este pretul produsului (ordine crescatoare)

void inserare1(arbore *&c,produs e)

else

void cmmd(arbore *&c, arbore*&f)

void sterg1(arbore *&c,char den[26], float price)

else

if(c->as==0)

else

if(c->ad==0)

else cmmd(c, c->as);

else

if(strcmp(c->info.denumire,den)<0)

sterg1(c->ad,den,price);

else sterg1(c->as,den,price);

}

else

if(c->info.pret<price)

sterg1(c->ad,den,price);

else

sterg1(c->as,den,price);

else cout<<'Acest produs nu exista in baza de date!!';

void sterg(arbore *&c,char den[26])

else

if(c->as==0)

else

if(c->ad==0)

else cmmd(c, c->as);

else

if(strcmp(c->info.denumire,den)<0)

sterg(c->ad,den);

else sterg(c->as,den);

else cout<<'Acest produs nu exista in baza de date!!';

void modifica1(arbore *&c,char den[26],float price,unsigned int cant)

else

if(strcmp(c->info.denumire,den)<0)

modifica1(c->ad,den,price,cant);

else modifica1(c->as,den,price,cant);

else

if(c->info.pret>price)

modifica1(c->as,den,price,cant);

else modifica1(c->ad,den,price,cant);

else cout<<'Acest produs nu exista in baza de date!!';

void modifica(arbore *&c,char den[26],unsigned int cant)

else

if(strcmp(c->info.denumire,den)<0)

sterg(c->ad,den);

else sterg(c->as,den);

else cout<<'Acest produs nu exista in baza de date!!';

void inordine(arbore *p,unsigned int & nr)

inordine(p->ad,nr);

}

void produse_stoc(arbore *p,unsigned int & nr)

produse_stoc(p->ad,nr);

}

void stoc_zero(arbore *p,unsigned int & nr)

stoc_zero(p->ad,nr);

}

void peste_10000(arbore *p,unsigned int & nr)

peste_10000(p->ad,nr);

}

void total_stoc(arbore *p,unsigned int &nr,float &suma)

void scrie_in_fisier(arbore *p)

void main()

}

fi.close();

clrscr();

textbackground(RED);

textcolor(WHITE);

cout<<endl<<endl<<' ATESTAT 2007'<<endl<<endl<<endl;

cout<<endl<<endl<<' MAGAZIN'<<endl<<endl;

cout<<' CURCAN STEFANITA - clasa a XII-a G'<<endl<<endl<<endl<<endl;

cout<<' Apasa o tasta pentru a continua '<<endl;

getch();

textbackground(BLUE);

textcolor(YELLOW);

clrscr();

cout<<endl<<endl<<endl;

cout<<' I - adaugarea unui produs'<<endl;

cout<<' S - stergerea unui produs'<<endl;

cout<<' V - vanzarea unui produs'<<endl;

cout<<' A - lista alfabetica a produselor'<<endl;

cout<<' P - lista produselor aflate in stoc'<<endl;

cout<<' N - lista produselor cu stocul zero'<<endl;

cout<<' M - lista produselor cu valoare totala peste 10000 lei'<<endl;

cout<<' D - lista produselor in ordinea crescatoare a pretului'<<endl;

cout<<' Q - valoarea totala a stocului'<<endl;

cout<<' X - iesirea din program'<<endl<<endl;

do

case 'I':

case 'S' :

case 'V' :

case 'P' :

case 'N' :

case 'M' :

case 'D' :

case 'Q' :

default : if(optiune!='X') cout<<'Optiune gresita!!!'<<endl;

}

}while(optiune!='X');

clrscr();

cout<<endl<<endl<<' Se actualizeaza informatiile in fisierul MAGAZIN.TXT'<<endl<<endl;

cout<<' Apasa orice tasta pt a inchide aplicatia';

getch();

//se scriu informatiile din arbore in fisierul MAGAZIN.DAT

scrie_in_fisier(RAD);

fo.close();

//se copiaza continutul fisierului MAGAZIN.DAT in fisierul MAGAZIN.TXT

ifstream f('MAGAZIN.DAT');

ofstream g('MAGAZIN.TXT');

char ch[31];

while(!f.eof())

f.close();

g.close();

EXECUTIA PROGRAMULUI

MAGAZIN.TXT

CAIET1

BUC

3.5

0.665

360

1666

CAIET2

BUC

4.67

0.8873

200

1111.459961

CREION1

BUC

1.45

0.2755

300

517.650024

BIBLIOGRAFIE

1.     TUDOR SORIN, INFORMATICA – MANUAL PENTRU CLASA A IX-A, Varianta C++, EDITURA L&S INFOMAT, BUCURESTI, 2000.

2.     TUDOR SORIN, INFORMATICA – MANUAL PENTRU CLASA A XI-A, Varianta C++, EDITURA L&S INFOMAT, BUCURESTI, 2006.

3.     GEORGE DANIEL MATEESCU, PAVEL FLORIN MORARU – Informatica pentru liceu si bacalaureat – Materia de clasa a X-a, Varianta C++ – Editura Donaris, 2002.