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