Trimite referat
Referatele si lucrarile oferite de Clopotel.ro au scop educativ si orientativ pentru cercetare academica.

Arbore binar

Materie: Informatica
Accesari: 6.580
Download-uri: 834
Nota: 5.29 (1539 note)
Am probleme cu acest referat!

1 2 3
4 5 6
7 8 9


Download Referat - Arbore binar
Publicitate:

Trimis de Aurel
din 25 Iunie 2008

     Un arbore binar este un arbore orientat in care fiecare varf are cel mult doi descendenti, facandu-se insa distinctie clara intre descendentul drept si descendentul stang al fiecarui varf. Se accepta si arborele binar cu 0 varfuri.
    
Arborii binari nu reprezinta cazuri particulare de arbori orientati, decat daca se face abstractie de distinctia mentionata intre descendentul drept si cel stang al fiecarui varf. Intr-adevar daca un varf are un singur descendent, aceasta informatie este suficienta in cazul unui arbore, dar insuficienta in cazul unui arbore binar, cand trebuie precizat daca acest descendent este descendent stang sau descendent drept.
                                                             
Definire. Reprezentare.

Prezentam in continuare citeva modalitati de definire a arborilor binari in Haskell.
                data Tree a = Nil | T(Tree a, a, Tree a)
                data Tree a = Nil | T Tree a a Tree a
       
Pentru a afisa structurile de date arborescente intr-un mod similar cu listele sau tipurile de date simple, este necesara extinderea clasei Show, prin intermediul careia se realizeaza afisarea datelor la consola.

-- Extinderea clasei Show
instance Show a => Show (Tree a) where
show Nil = "Nil"
show (T(l,n,r)) = " T( " ++ show l ++ ", " ++ show n ++ ", " ++ show r ++ ") "

       Intr-o structura de tip arbore, elementele sunt structurate pe nivele ; pe primul nivel, numit nivel 0, exista un singur element numit radacina, de care sunt legate mai multe elemente numite fii care formeaza nivelul 1; de acestea sunt legate elementele de pe nivelul 2 s. a. m. d. ( vezi figura ).
 
       Un arbore este compus din elementele numite noduri sau varfuri si legaturile dintre acestea. Un nod situat pe un anumit nivel este nod tata pentru nodurile legate de el, situate pe ivelul urmator, acestea reprezentand fiii sai. Fiecare nod are un singur tata, cu exceptia radacinii care nu are tata. Nodurile fara fii se numesc noduri terminale sau frunze. Termenii ' nod tata', 'fiu' sau 'frate' sunt preluati de la arborii genealogici, cu care arborii se aseamana foarte mult.
      
Arborii, ca structuri dinamice de date, au extrem de multe aplicatii in informatica. Deosebit de utilizatain aplicatii este structura de tip arbore binar. Un arbore binar este un arbore in care fiecare nod are cel mult doi fii, fiul stang si fiul drept (fiul stang este legat in stanga tatalui si cel drept in dreapta ).
Daca in figura se elimina radacina si legaturile ei, se obtin doi arbori binari care se numesc subarborii stang si drept ai arborelui initial. Arborele binar este, deci, o structura recursiva de date. Un arbore binar nevid fie se reduce la radacina, fie cuprinde radacina si, cel mult, doi subarbori binari. Un arbore binar se poate implementa foarte usor cu ajutorul adreselor de inlantuire, fiecare element cuprinzand, in afara de informatia proriu-zisa asociata nodului, adresa fiului stang si adresa fiului drept, acestea exprimand legaturile existente intre noduri.


Implementarea arborilor binari

     Daca se recurge la implementarea arborilor prin structuri dinamice, atunci aceasta constanta se reprezinta prin NIL. Tipul informatiilor atasate nodurilor dintr-un arbore este specific fiecarei aplicatii in parte. Din acest motiv, vom considera ca informatia atasata fiecarui nod este adresta indirect prin intermediul unui pointer. In majoritatea implementarilor si cei doi subarbori sunt adresati indirect; in functie de varianta de implementare - dinamica sau statica - , adresarea se realizeaza fie prin intermediul pointerilor, fie prin intermediul indicilor de tablou.
   
Alegem implementarea dinamica cea mai simpla forma de reprezentare a nodurilor :
Type
  
NodPtr =".Nod ;
   Nod = record
    info: string ;
 
    stanga: NodPtr ;
    dreapta: NodPtr ;
end
Var
   radacina : NodPtr ;
                                                                

Operatii:

  Operatiile posibile cu arbori sunt la fel ca in cazul listelor:
traversarea arborelui ;
inserarea unui nod ;
cautarea unui nod ;
stergerea unui nod ;
Traversarea arborelui binar consta in parcurgerea pe rand a nodurilor in vederea prelucrarii informatiilor atasate acestora. Traversarea arborelui presupune vizitarea fiecarui nod o singura data, operatie echivalenta cu o liniarizare a arborelui.
 
Exista trei modalitati importante de trvesare a unui arbore binar :

1.) in preordine : seviziteaza radacina, apoi tot in preordine se viziteaza nodurile subarborelui stang si apoi acelea ale subarborelui drept.
    Nodurile arborelui din figura 2 vizitate in preordine, sunt :
                          1 2 4 5 3 6 7 8.
2.) in inordine : se viziteza in inordine nodurile subarborelui stang, apoi radacina si apoi tot in inordine, nodurile subarborelui drept.
Nodurile arborelui di...

Atentie : Textul de mai sus este doar un preview al referatului, pentru a vedea daca continutul acestui referat te poate ajuta. Pentru varianta printabila care poate sa contina imagini sau tabele apasa butonul de 'download' !!!
Download Referat - Arbore binar
Acest site foloseste cookies. Prin navigarea pe acest site, va exprimati acordul asupra folosirii cookie-urilor. Detalii aici OK