Referat - Arbore binar

Categorie
Referate Informatica
Data adaugarii
acum 4 ani
Afisari
314
Etichete
arbore, binar
Descarcari
209
Nota
0 / 10 - 0 voturi

Arbore binar
     Un arbore binar este un arbore orientat în care fiecare vârf are cel mult doi descendenti, facându-se însa distinctie clara între descendentul drept si descendentul stâng al fiecarui vârf. Se accepta si arborele binar cu 0 vârfuri.      Arborii binari nu reprezinta cazuri particulare de arbori orientati, decât daca se face abstractie de distinctia mentionata între descendentul drept si cel stâng al fiecarui vârf. Într-adevar daca un vârf are un singur descendent, aceasta informatie este suficienta în cazul unui arbore, dar insuficienta în cazul unui arbore binar, când trebuie precizat daca acest descendent este descendent stâng sau descendent drept.                                                              
Definire. Reprezentare.
Prezentam în continuare cîteva 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 ++ ") "
       Într-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 vârfuri si legaturile dintre acestea. Un nod situat pe un anumit nivel este nod tata pentru nodurile legate de el, situate pe ivelul urmator, acestea reprezentând fiii sai. Fiecare nod are un singur tata, cu excepti


Copyright © Toate drepturile rezervare. 2008 - 2024 - Referatele.org