<<Pagina Materiale

 
 
Arbori binari 


Aspecte teoretice

Definitie 

Un arbore binar este o multime de n >= 0 noduri, care daca nu este vida, contine un nod numit radacina, restul nodurilor formând doi arbori disjuncti numiti subarborele stâng si subarborele drept.

Aceasta structura de date e importanta pentru ca e usor de reprezentat si prelucrat, orice arbore putând fi transformat în arbore binar .

Tehnica transformarii unui arbore generalizat în arbore binar

Un arbore generalizat poate fi transformat intr-un arbore binar, astfel incât 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 în arbore binar având radacina A1, A1,1 fiul sau stâng, iar A1,i devin fiii drepti ai lui A1,i-1 pentru 2<=i<=k.

Secventele de noduri în parcurgerea în preordine a arborelui generalizat si a celui binar obtinut prin transformare, sunt identice.

Exemplu: Se considera arborele generalizat de mai sus. Aplicând regula descrisa, se obtine arborele binar reprezentat.

Implementarea arborilor binari

Un arbore binar poate fi descris cu ajutorul urmatoarei structuri de date dinamice:

typedef int TCheie; 

class TNodAB { 
   public: 
      TCheie cheie; 
      TNodAB *stg,*dr; 
      TNodAB(TCheie k) { 
           cheie=k; 
           stg=dr=NULL; 
       } 
}; 

Operatorii arborelui binar

INITIALIZEAZA(A) - face vid arborele A;
INSEREAZA(X,A) - insereaza cheia X în arborele A;
CAUTA(X,A) - cauta cheia X, returnând true la gasire;
SUPRIMA(X,A) - suprima cheia X, daca exista;
TRAVERSEAZA(A) - parcurge toate cheile arborelui A

Traversarea arborilor binari

Pentru un arbore binar, notând cu R radacina si cu A si cu B subarborele sau stâng, respectiv drept, cele 3 posibilitati de traversare sunt:

    • preordine - lista R, A, B
    • inordine - lista A, R, B
    • postordine- lista A, B, R.
Cele trei metode de traversare se concretizeaza în trei functii recursive în care Prelucrare este operatia ce trebuie facuta asupra fiecarui nod.

Arbori binari ordonati. Arbori binari de înaltime minima

Arborele binar ordonat e arborele binar cu proprietatea ca parcurgând nodurile în inordine, secventa cheilor este monoton crescatoare.

Are proprietatea ca daca un nod oarecare al arborelui are cheia c, toate nodurile din subarborele stâng al nodului au cheile mai mici decât valoarea c, respectiv toate cheile din subarborele drept au cheile mai mari sau egale cu c. De aici rezulta procedeul de cautare foarte simplu, prin trecerea la fiul stâng sau drept de la nodul curent, functie de relatia dintre cheia cautata si cea a nodului curent.

Cum înaltimea minima a unui arbore binar ordonat cu n noduri este

hmin=[log2 (n+1)],
rezulta ca o cautare într-un arbore binar ordonat necesita aproximativ log2n comparatii de chei, fata de n/2 comparatii într-o lista liniara.

Tehnica de creare a arborilor binari ordonati

Procesul de creare consta în insertia câte unui nod într-un arbore binar ordonat, care initial este vid, astfel încât dupa insertie el sa ramâna ordonat.

Pentru aceasta se traverseaza arborele începând cu radacina si se selecteaza fiul stâng sau drept, dupa cum cheia de inserat e mai mica sau mai mare decât a nodului parcurs. Se repeta pâna când se ajunge la un pointer nil care se inlocuieste cu pointerul spre noul nod creat. Pentru ca sortarea sa fie stabila, se trece la fiul drept chiar daca valoarea cheii e egala.

Pentru a vedea cum se construieste un ABO, sa vedem ce se intampla la insertia intr-un arbore vid a cheilor:

MOON, JUPITER, SATURN, EARTH, MARS, VENUS, PLUTO, URANUS

Apasati succesiv pe Adauga Nod si observati locul de insertie al noului nod:

Comentarii: 
 

Tehnica suprimarii unui nod dintr-un arbore binar ordonat

În urma suprimarii unui nod având cheia x dintr-un arbore binar ordonat, acesta trebuie sa ramâna ordonat.

Cazurile ce se disting sunt functie de numarul de fii ai nodului ce se suprima. Daca numarul fiilor este:

  • cel mult unu - referinta spre nodul de suprimat se inlocuieste cu referinta spre unicul sau fiu ( sau nil daca nodul e terminal );

  • doi fii - se cauta predecesorul nodului în ordonarea arborelui în inordine 
    • se demonstreaza ca acesta exista si nu are fiu drept; se gaseste construind secventa formata din fiul stâng al nodului de suprimat si apoi fiii drepti pâna la cel ce nu are descendent drept;
    • se asigneaza toate câmpurile de informatie ( nu de înlantuire ) ale nodului de suprimat cu cele ale predecesorului sau;
    • se suprima predecesorul ( nu are fiu drept ).
Cazul suprimarii unui nod care are doi fii este ilustrat intr-ul mod general in figura.

Construirea unui arbore binar total echilibrat

Pentru orice nod al unui ABO total echilibrat, numarul nodurilor din subarborele stâng diferacel mult cu unu de cel al nodurilor subarborelui drept, toate nodurile terminale fiind pe ultimele doua nivele.

Având secventa ordonata crescator a celor n noduri ale arborelui ( cea care se va obtine la parcurgerea în inordine ), construirea ABO total echilibrat se realizeaza prin urmatorul algoritm recursiv:

a) nodul median este radacina;
b) ns (= n div 2 ) noduri va contine subarborele stâng ce se construieste începând cu pasul a);
c) nd (= n - ns - 1 ) noduri va contine subarborele drept ce se construieste începând cu pasul a).
 

Sus
Exemplu de implementare ABO

Rulati programul de mai jos; modificati main astfel incat programul sa devina interactiv avand optiunile:

  • initializare arbore
  • insertie cheie citita
  • cautare cheie
  • stergere cheie
  • traversare in cele trei variante
  • afisare arbore si inaltime.
//////////////////////////////////////////////////////////

// ABO.H - declaratia clasei Arbore Binar Ordonat

#include <stddef.h>

typedef int TCheie;
enum  BOOL {FALSE=0, TRUE=1};

class TNodAB {
  public:
    TCheie cheie;
    TNodAB *stg,*dr;
    TNodAB(TCheie k) {
      cheie=k;
      stg=dr=NULL;
    }
};

class TArboreABO {

    TNodAB *radacina;
    TNodAB * adauga(TNodAB *r, TCheie k);
    TNodAB *d(TNodAB *u,TNodAB *q);
    TNodAB *sterge(TNodAB *r, TCheie k);
    int inaltime(TNodAB *r);
    void inordine(TNodAB *r);
    void preordine(TNodAB *r);
    void postordine(TNodAB *r);
    void tipar_arbore(TNodAB *r, int h);
    void distruge(TNodAB *r);
  public:
    TArboreABO();
    ~TArboreABO();
    void Adauga(TCheie k);
    void Sterge(TCheie k);
    BOOL Prezent(TCheie k);
    int Inaltime();
    void Inordine();
    void Preordine();
    void Postordine();
    void TiparArbore();
};

//////////////////////////////////////////////////////////

// ABO.CPP - Implementarea clasei Arbore Binar Ordonat

#include "abo.h"
#include <iostream.h>

TArboreABO::TArboreABO() {
  radacina=NULL;
}

TArboreABO::~TArboreABO() {
  distruge(radacina);
}

void TArboreABO::distruge(TNodAB *r) {
  if (r) {
    distruge(r->stg);
    distruge(r->dr);
    delete r;
  }
}

void TArboreABO::Adauga(TCheie k) {
  radacina=adauga(radacina, k);
}

TNodAB * TArboreABO::adauga(TNodAB *r, TCheie k) {
// functie recursiva de adaugare a unui nod nou k intr-o
// structura arborescenta cu radacina r
  if (!r) {
    r=new TNodAB(k);
    return r;
  }
  else if (k<r->cheie) r->stg=adauga(r->stg,k);
  else if (k>r->cheie) r->dr=adauga(r->dr,k);
  return r;
}

int TArboreABO::Inaltime() {
  return inaltime(radacina);
}

int max(int a, int b) {
  if (a>b) return a;
  return b;
}

int TArboreABO::inaltime(TNodAB *r) {
  if (!r) return 0;
  return max(inaltime(r->stg),inaltime(r->dr))+1;
}

BOOL TArboreABO::Prezent(TCheie k) {
  TNodAB *crt=radacina;
  while (crt) {
    if (k==crt->cheie) return TRUE;
    if (k<crt->cheie) crt=crt->stg;
    if (k>crt->cheie) crt=crt->dr;
  }
  return FALSE;
}

TNodAB *TArboreABO::d(TNodAB *u,TNodAB *q){
// d elimina nodul din extrema dreapta si returneaza
// radacina subarborelui obtinut 

  TNodAB *t;
  if(q->dr!=NULL) q->dr=d(u,q->dr);
  else {
    t=q;
    u->cheie=q->cheie;
    q=t->stg;
    delete t;
  }
  return q;
}

TNodAB * TArboreABO::sterge(TNodAB *r, TCheie k) {
  TNodAB *t;
  if(r!=NULL)
    if( k<r->cheie) r->stg=sterge(r->stg,k);
    else
      if (k>r->cheie) r->dr=sterge(r->dr,k);
      else{
        t=r;
        if (t->stg==NULL) { 
          r=t->dr;
          delete t;
        }
        else
          if (t->dr==NULL) {
            r=t->stg;
            delete t;
          }
          else t->stg=d(t,t->stg);
     }
  return r;
}

void TArboreABO::Sterge(TCheie k) {
  radacina=sterge(radacina,k);
}

void TArboreABO::Inordine() {
  inordine(radacina);
}

void TArboreABO::inordine(TNodAB * r) {
  if (r) {
    inordine(r->stg);
    cout<<r->cheie<<" ";
    inordine(r->dr);
  }
}

void TArboreABO::Preordine() {
  preordine(radacina);
}

void TArboreABO::preordine(TNodAB * r) {
  if (r) {
    cout<<r->cheie<<" ";
    preordine(r->stg);
    preordine(r->dr);
  }
}

void TArboreABO::Postordine() {
  postordine(radacina);
}

void TArboreABO::postordine(TNodAB * r) {
  if (r) {
    postordine(r->stg);
    postordine(r->dr);
    cout<<r->cheie<<" ";
  }
}

void TArboreABO::tipar_arbore(TNodAB *r,int h){
  if (r) {
    tipar_arbore(r->stg,h-5);
    for (int i=1; i<h; i++) cout<<' ';
    cout<<r->cheie<<"\n";
    tipar_arbore(r->dr,h-5);
  }
}

void TArboreABO::TiparArbore() {
  cout <<"\n";
  tipar_arbore(radacina,Inaltime()*5);
}

//////////////////////////////////////////////////////////

// PROG_ARB.CPP

#include "abo.h"
#include <iostream.h>
#include <stdlib.h>

main() {
  TArboreABO *a=new TArboreABO;
  for (int i=0; i<10; i++) //se adauga 10 chei aleatoare
    a->Adauga(random(20));
  cout<<"\n Arborele(rotit 90 grd dr):";
  a->TiparArbore();
  cout<<"h="<<a->Inaltime();
  delete a;
}
Sus
Exercitii

1.Pentru un ABO initial vid, se cere:

a) Sa se specifice configuratia dupa insertia cheilor:

40,55,21,50,42,56,10,30,26,1,11,90,75,200 ;

b) respectiv dupa suprimarea fiecareia din cheile:

40,90,30,26,21,55,50,42;

c) Pentru subarborele obtinut dupa ultima stergere de la b), scrieti succesiunea cheilor pentru parcurgerea in preordine, inordine si postordine.

2.Demonstrati prin inductie ca numarul nodurilor cu doi descendenti dintr-un ABO este cu unu mai mic decât cel al frunzelor.

3.Adaugati la exemplul de implementare de mai sus urmatoarele prelucrari:

  • pentru doua chei precizate sa se stabileasca:
    • daca sunt în relatia stramos-descendent sau
    • daca sunt situate pe acelasi nivel, caz în care se afiseaza numarul nivelului respectiv;
  • determinarea si afisarea adâncimii arborelui
  • sa se suprime:
    • nodul cu cheia minima;
    • toate nodurile cu contorul mai mic decât o valoare data;
    • nodul cu o cheie data;
    • tatal nodului cu cheia data;
    • fiul drept al nodului cu cheia data.
  • pentru o cheie data sa se tipareasca toti descendentii nodului care o contine (subarborele a carui radacina este nodul cu cheia precizata);
  • pentru o cheie precizata sa se afiseze cheile nodurilor parinte, frate drept, frate stâng, fiu drept, fiu stâng.
4.Sa se construiasca arborele binar ordonat perfect echilibrat, având aceleasi chei ca si ABO construit la 3. Sa se vizualizeze cei doi arbori si sa li se compare înaltimile.

5.Sa se redacteze operatorii care creaza copia si simetricul în oglinda ai unui arbore binar dat. Sa se vizualizeze cei trei arbori.

6.Sa se realizeze un program care pornind de la o expresie aritmetica în format infix care contine operanzi (identificatori de o singura litera), operatorii +, -,*, / si paranteze, construieste arborele de parcurgere asociat. Expresia aritmetica se introduce de la tastatura.
Se vizualizeaza arborele de parcurgere obtinut.
Se introduc interactiv valori pentru toti identificatorii si se evalueaza expresia pornind de la forma postfix a expresiei rezultata din parcurgerea în postordine a arborelui de parcurgere.

7.Sa se implementeze operatorul care testeaza daca daca doi arbori binari au aceeasi forma geometrica.

Indicatie:
Fie A1=(S1,R,D1) si A2=(S2,R,D2) cei doi arbori. A1 si A2 au aceeasi forma geometrica daca S1 are aceeasi forma cu S2 si D1 are aceeasi forma cu D2. 

Sus
<<Pagina Materiale


Copyright © 2001-2002. Carmen Holotescu
All rights reserved. Published by Timsoft