ARBORI BINARI

DEFINIŢIE: Se numeşte arbore un graf conex şi fără cicluri;

DEFINIŢIE: Se numeşte arborescenţă un arbore care conţine un nod special numit rădăcină iar restul nodurilor sunt grupate în m mulţimi disjuncte (nu au elemente comune) x 1, x 2 ,…,x m, fiecare mulţime având un nod adiacent cu rădăcina şi subgrafurile determinate de aceste submulţimi sunt la rândul lor arborescenţe;

DEFINIŢIE: Se numeşte arbore binar o arborescenţă care are cel puţin un nod, dacă are mai multe noduri fiecare dintre acestea are cel mult doi fii.

Se presupune ca 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 etc. Numarul de niveluri mai putin cel al radacinii, ocupate de nodurile grafului se numeste adancimea arborelui binar.

Exemplu de arbore binar ordonat:

Unde:

· 26 – este radacina arborelui

· 3, 21, 111 – sunt noduri terminale (frunze) pentru ca nu au fii.

Definirea unui nod:

Pascal	C++
type pnod=^nod;	typedef struct nod{
nod=record
inf:integer;	int inf;
st, dr: pnod;	nod *st, *dr;
end;	} *pnod;

Adăugarea unui nod:

Pascal	Explicatii	C++
procedure adauga(x:integer; var p:pnod);		void adauga(int x, pnod p)
begin		{
if p=NIL then begin	dacă nu există nodul p atunci	if (p) {
new(p);	se creează nodul p	p=new nod;
p^.inf:=x;	se pune informaţia x în noul nod	p->inf=x;
p^.st:=NIL;	nodul p nu are fiu stâng	p->st=NULL;
p^.dr:=NIL;	nodul p nu are fiu drept	p->dr=NULL;
end		}
else if x<p^.inf then adauga(x,p^.st)	altfel dacă valoarea noului nod este mai mică decât valoarea din nodul p atunci se adaugă noul nod în subarborele stang al nodului p	else if (x<p->inf) adauga(x,p->st);
else if x>p^.inf then adauga(x,p^.dr);	altfel dacă valoarea noului nod este mai mare decât valoarea din nodul p atunci se adaugă noul nod în subarborele drept nodului p	else if (x>p->inf) adauga(x,p->dr);
end;		}

Ştergerea unui nod:

Pascal	Explicatii	C++
procedure sterge(x:integer; var p:pnod);	sterge nodul cu informatia x din arbore	void sterge (int x, pnod p)
var q:pnod;		pnod q;
procedure ste(var p:pnod);	procedura ste caută cel mai mare element dintre fii nodului p	void ste(pnod p)
begin		{
if p^.dr<>NIL then ste(p^.dr)	daca nodul p are fiu drept atunci se continua cautarea in subarborele sau drept	if (p->dr) ste(p->dr);
else begin	altfel	else {
q^.inf:= p^.inf;	se copiază în q informaţia din nodul p	q->inf=p->inf;
q:=p;	q va indica spre nodul ce trebuie şters	q=p;
p:=p^.st;	fiul stang al nodului p urca pe pozitia pe care se afla p	p=p->st;
end;		}
end;		}
begin
if p=NIL then writeln(‘Nu exista’)	dacă nodul căutat nu există se afişează un mesaj corespunzator	if (p==NULL)
else if x=p^.inf then begin	altfel dacă s-a găsit nodul ce trebuie şters	else if (x==p->inf) {
q:=p;	q va indica spre nodul ce trebuie şters	q=p ;
if p^.st=NIL then p:=p^.dr	dacă nu are fiu stâng în locul nodului şters se pune fiul lui drept	if (p->st==NULL) p=p->dr ;
else if p^.dr=NIL then p:=p^.st	altfel dacă nu are fiu drept în locul nodului şters se pune fiul său stâng	else if (p->dr==NULL) p=p->st ;
else ste(p^.st);	altfel se pune în locul lui cel mai mare element din subarborele sau stâng	else ste(p->st) ;
dispose(q);	se dezaloca memoria ocupata de nodul q	dispose(q) ;
end		};
else if x<p^.inf then sterge(x,p^.st)	altfel, daca nu s-a gasit inca nodul si valoarea x este mai mica decat valoarea retinuta de nodul p atunci elementul x va fi cautat in subarborele stang al nodului p	else if (x<p->inf) sterge(x,p->st);
else sterge(x,p^.dr);	altfel, daca nu s-a gasit inca nodul si valoarea x este mai mare decat valoarea retinuta de nodul p atunci elementul x va fi cautat in subarborele drept al nodului p	else sterge(x,p->dr);
end;		}

Parcurgerea în preordine:

Pascal	Explicatii	C++
procedure preordine(p:pnod);	parcurge arborele in preordine	void preordine(pnod p)
begin		{
if p<>NIL then begin	dacă există nodul p	if (p) {
{o operatie asupra informatiei nodului}	se executa o operatie asupra nodului curent. Ex: afisare, modificare, testare daca indeplineste o anumita conditie etc.	/* o operatie asupra informatiei nodului */
preordine(p^.st);	se parcurge subarborele stâng	preordine(p->st) ;
preordine(p^.dr);	se parcurge subarborele drept	preordine(p->dr) ;
end;		};
end;		}

Parcurgerea în inordine:

Pascal	Explicatii	C++
procedure inordine(p:pnod);		void inordine(pnod p)
begin		{
if p<>NIL then begin	dacă există nodul p	if (p) {
inordine(p^.st);	se parcurge subarborele stâng	inordine(p->st) ;
{o operatie asupra informatiei nodului}	se executa o operatie asupra nodului curent. Ex: afisare, modificare, testare daca indeplineste o anumita conditie etc.	/* o operatie asupra informatiei nodului */
inordine(p^.dr);	se parcurge subarborele drept	inordine(p->dr) ;
end;		};
end;		}

Parcurgerea în postordine:

Pascal	Explicatii	C++
procedure postordine(p:pnod);		void postordine(pnod p)
begin		{
if p<>NIL then begin	dacă există nodul p	if (p) {
postordine(p^.st);	se parcurge subarborele stâng	postordine(p->st) ;
postordine(p^.dr);	se parcurge subarborele drept	postordine(p->dr) ;
{o operatie asupra informatiei nodului}	se executa o operatie asupra nodului curent. Ex: afisare, modificare, testare daca indeplineste o anumita conditie etc.	/* o operatie asupra informatiei nodului */
end;		};
end;		}