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;

 

}