Documente online.
Username / Parola inexistente
  Zona de administrare documente. Fisierele tale  
Am uitat parola x Creaza cont nou
  Home Exploreaza













Arbori binari

Informatica



loading...











ALTE DOCUMENTE

Structuri si liste inlantuite
ZipSnap 0.1
Utilizarea filtrului Unsharp Mask din Photoshop
Windows XP Anularea PC Speaker
Customizarea serviciilor XP
versiunea 131:
VSU
Configurare STRONG - DC++
Istoria calculatoarelor personale si a retelelor
Sisteme distribuite. Socket-uri


                             4. Arbori binari

              Arbori

     Un arbore cu rădăcină ("rooted tree") este o structură neliniară, în care fiecare nod poate avea mai multi succesori, dar un singur predecesor, cu exceptia nodului rădăcină, care nu are nic 515d310f i un predecesor. Structura de arbore se poate defini recursiv astfel: Un arbore poate fi :

- nimic (arbore vid)

- un singur nod (rădăcina)

- un nod  care are ca succesori un numar finit de arbori.

     Altfel spus, dacă se elimină rădăcina unui arbore rezultă mai multi arbori, care erau subarbori în arborele initial (dintre care unii pot fi arbori fără nici un nod). Un arbore poate fi privit ca o extindere a unei liste liniare sau ca un caz particular de graf fără cicluri.

     Structura de arbore este o structură ierarhică, cu noduri asezate pe niveluri succesive, cu relatii de tip "părinte-fiu" între noduri. Fiecare nod are o anumită "înăltime" fată de rădăcină; toti succesorii unui nod se află pe acelasi nivel si au aceeasi înăltime. Nodurile terminale, fără succesori, se numesc si "frunze".

     Structurile arborescente se folosesc în programare deoarece:

 - Reprezintă un model natural pentru o ierarhie de obiecte, de persoane, de operatii, de functii;

 - Permit mentinerea în ordine a unei colectii de date dinamice  (cu multe adăugări si stergeri) simultan cu o căutare rapidă după continut (reprezintă o bună structură de căutare).

     Arborii se folosesc pentru implementarea tipurilor abstracte multime, dictionar si coadă cu priorităti.

    Un caz particular important de arbori îl constituie arborii binari, în care un nod poate avea cel mult doi succesori: un succesor la stânga si un succesor la dreapta.

     De cele mai multe ori legăturile unui nod cu succesorii săi se reprezintă prin pointeri, dar este posibilă si o reprezentare a arborilor fără pointeri, printr-un vector de înregistrări , unde  fiecare înregistrare corespunde unui nod, iar adresele de legătură între noduri sunt indici în vector. De obicei se întelege prin arbore o structură cu  pointeri, deoarece  această structură este mai eficientă în cazul unor colectii cu număr necunoscut sau foarte variabil de elemente.

Un  arbore este complet definit printr-o singură variabilă, care contine adresa nodului rădăcină.

     Operatiile uzuale cu arbori sunt:

 - Initializare arbore (creare arbore vid sau cu un singur nod);

 - Adăugarea unui nod la un arbore ( ca nod frunză);

 - Căutarea unei valori date într-un arbore;

 - Eliminarea (stergerea) unui nod cu valoare dată;

 - Afisarea tuturor nodurilor din arbore într-o  anumită ordine (mai  general, aplicarea unor operatii asupra  tuturor  nodurilor din arbore).

     O reprezentare liniară posibilă a unui arbore este o expresie cu paranteze complete, în care fiecare nod este urmat de o paranteză ce grupează succesorii săi. Exemple:

  1)     a (b,c)

     este un arbore binar cu 3 noduri: rădăcina 'a', având la stânga pe 'b' si la dreapta pe 'c'

2)   5 (3 (1,), 7(,9))

     este un arbore binar ordonat cu rădăcina 5. Nodul 3 are un singur succesor, la stânga, iar nodul 7 are numai succesor la dreapta.  

                                   5

                      _______|_______

                     3                         7

                ___|___                ___|___

               1                                      9                        

     Operatiile cu arbori binari se realizează mai compact prin functii recursive, care reflectă structura recursivă a unui arbore: prelucrarea unui arbore binar se reduce la prelucrarea celor doi subarbori din componenta sa.

              Arbori binari cu pointeri

     Definirea unui nod dintr-un arbore binar seamănă cu definirea unui nod dintr-o listă înlăntuită, dar contine două adrese de legătură (doi pointeri), către cei doi succesori posibili :

typedef struct nod Nod;

     Initializarea unui arbore vid se reduce la atribuirea valorii NULL pentru variabila rădăcină. Poate fi luată în considerare si o initializare a  rădăcinii cu  prima  valoare introdusă în  arbore,  pentru ca adăugările ulterioare să nu mai modifice adresa rădăcinii (dacă nu se face modificarea  arborelui pentru  reechilibrare, după fiecare adăugare ).

     Una dintre cele mai simple operatii cu un arbore binar este determinarea  înăltimii unui arbore; înăltimea unui arbore este egală cu cea mai mare dintre înăltimile subarborilor săi, plus unu pentru rădăcină, pentru un arbore nevid si zero pentru arborele vid.

   // calcul inaltime arbore binar

int inaltime (Nod * r)

    Modificând putin functia anterioară se obtine o functie care să numere nodurile dintr-un arbore.

   Căutarea unei valori într-un arbore binar se reduce la căutarea succesivă în fiecare din cei doi subarbori:

   // cautare în arbore oarecare

Nod * cautAB ( Nod * r, int x)

     Vizitarea nodurilor unui arbore binar înseamnă de fapt liniarizarea arborelui, adică stabilirea unei secvente liniare de noduri. Explorarea unui arbore se poate face în adâncime sau în lărgime (nivel cu nivel). Explorarea în adâncime se poate face în mai multe  feluri, în functie de ordinea în care se iau  în considerare  rădăcina, subarborele stânga si subarborele dreapta :

     - Ordine prefixată (preordine sau RSD) : rădăcină, stânga, dreapta

     - Ordine infixată (inordine sau SRD) : stânga, rădăcină, dreapta

     - Ordine postfixată (postordine sau SDR): stânga, dreapta, rădăcină

     Fie arborele binar descris prin expresia cu paranteze:

          5 ( 2 (1,4(3,)), 8 (6 (,7),9) )

     Explorarea pe niveluri produce secventa de noduri:     5 2 8 1 4 6 9 3 7 

     Explorarea prefixată produce secventa de noduri:        5 2 1 4 3 8 6 7 9

     Explorarea infixată produce secventa de noduri:          1 2 3 4 5 6 7 8 9

     Explorarea postfixată produce secventa de noduri:      1 3 4 2 7 6 9 8 5

     Functia următoare afisează în ordine infixată valorile din nodurile unui arbore binar

void infix (Nod * r)

}

     Functia "infix" poate fi usor modificată pentru o altă strategie de vizitare a nodurilor.

void prefix (Nod * r)

}

     Modul de realizare a operatiei de adăugare a unui nod la un arbore binar depinde de tipul arborelui ( ordonat sau nu ), deci dacă trebuie mentinută o relatie între valorile nodurilor .

              Arbori binari de căutare

     Un arbore binar ordonat, numit si arbore de sortare sau arbore de căutare, este un arbore binar cu proprietatea că orice nod are valoarea mai mare decât toti succesorii la stânga si mai mică decât toti succesorii la dreapta. Rezultă că toate valorile din subarborele stânga sunt mai mici si toate  valorile din subarborele dreapta sunt mai mari ca valoarea din rădăcină, pentru orice subarbore dintr-un arbore ordonat. Exemplu de arbore binar de căutare:   

             5 ( 2 (1,4(3,)), 8 (6 (,7),9) )

      Avantajul unui astfel de arbore este acela că permite o căutare mai rapidă a unei valori, comparabilă cu căutarea  binară pentru vectori ordonati: după ce se compară valoarea căutată cu valoarea din rădăcină  se poate decide în care din cei doi subarbori se află (dacă există) valoarea căutată. Fiecare nouă comparatie elimină un subarbore din căutare si reduce cu 1 înăltimea arborelui în care se caută.

     Timpul minim de căutare se realizează pentru un arbore ordonat echilibrat  (cu înăltime minimă), la care înăltimile celor doi subarbori sunt egale sau diferă cu 1. Acest timp este de ordinul log2(n), unde "n" este numărul total de noduri din arbore. Procesul de căutare într-un arbore binar ordonat poate fi exprimat recursiv sau nerecursiv.

   //  căutare recursivă în arbore ordonat

Nod * cautABC ( Nod * r, int x)

   //  căutare nerecursivă în arbore ordonat

Nod * cautABC ( Nod * r, int x)

  return NULL;

}

     Valoarea maximă dintr-un arbore binar de căutare se află în nodul din extremitatea dreaptă, iar valoarea minimă în nodul din extremitatea stângă. O functie pentru determinarea valorii maxime dintr-un arbore binar de căutare se poate scrie iterativ sau recursiv:

     // valoare maxima din arbore binar de cautare

int maxABC ( Nod * r)

     Adăugarea unui nod la un arbore binar ordonat  seamănă cu căutarea, pentru că se caută nodul frunză cu valoarea cea mai apropiată de valoarea care se adaugă. Nodul nou se adaugă ca frunză (arborele creste prin frunze).

   // adaugare nod la arbore binar ordonat

void addABC (Nod ** r, int x)

 if (x < p->val)

  addABC (&(p->st),x);

 else

  addABC (&(p->dr),x);

}

    

     Functia următoare realizează nerecursiv operatia de adăugare nod la un arbore de căutare:

   // adaugare nod la arbore binar ordonat (nerecursiv)

Nod * add (Nod * r, int x)

 if (x <q->val)

   q->st=n;        // n se adauga la stanga lui q

 else

   q->dr=n;        // n se adauga la dreapta lui q

 return r;

}

     Eliminarea  unui nod cu valoare dată dintr-un arbore binar ordonat trebuie să considere următoarele situatii:

 - Nodul de sters nu are succesori (este o frunză);

 - Nodul de sters are un singur succesor;

 - Nodul de sters are doi succesori.

     Eliminarea unui nod cu un succesor sau fără sduccesori este simplă si se reduce la înlocuirea legăturii la nodul sters prin legătura acestuia la succesorul nenul sau prin NULL.

   Eliminarea unui nod cu 2 succesori se face prin înlocuirea sa cu un nod care are cea mai apropiată valoare de cel sters; acesta  poate fi nodul din extremitatea dreaptă a subarborelui stânga sau nodul din extremitatea stânga a subarborelui dreapta.

     Operatia de eliminare nod se poate exprima nerecursiv sau recursiv.

   // eliminare valoare dată dintr-un arbore binar

Nod * delABC (Nod *  r, int x)

     // inlocuieste nodul r cu nodul p

  if (pp != r)

    pp->dr = p->st;

  else

    r->st =NULL;

  r->val =p->val;

      }

     free (p);

   }

 }

 return r;

}

              Expresii reprezentate prin arbori

     O expresie care contine numai operatori binari poate fi reprezentată printr-un arbore binar în care un nod poate contine fie un operator fie un operand. Exemplu de arbore pentru expresia

(a+b) / (c-d)

                                                    /

                                      _______|_______

                                      |                           |

                               ___ +___              ___--___         

                               |              |              |              |

                               a            b             c             d

     Evaluarea expresiei se face de la frunze spre rădăcină, în ordine postfixată. Functia următoare are ca rezultat valoarea unei expresii aritmetice cu operanzi si rezultat de tip "float" :

enum ;          // OP=0, VAL=1

typedef struct  Nod ;

  // evaluare expresie reprez. prin arbore

float eval(Nod * n)

}

     Crearea arborelui corespunzător unei expresii aritmetice fără paranteze si cu operanzi formati dintr-o singură cifră se poate face folosind functiile următoare:

 // creare nod cu operand/operator

Nod * nodnou( char op)

   // creare arbore dintr-o expresie aritmetica fara paranteze

Nod * exparb ( Nod* r, char *exp)

  if (*exp==0)

  else

}

     Rădăcina arborelui "r" este initializată în programul principal cu adresa unui nod ce contine operatorul '+' si care are la stânga un nod cu un operand zero.


Document Info


Accesari: 5131
Apreciat:

Comenteaza documentul:

Nu esti inregistrat
Trebuie sa fii utilizator inregistrat pentru a putea comenta


Creaza cont nou

A fost util?

Daca documentul a fost util si crezi ca merita
sa adaugi un link catre el la tine in site

Copiaza codul
in pagina web a site-ului tau.

 


Copyright © Contact (SCRIGROUP Int. 2014 )