Fituica

Peste 1000 de copiute GRATUITE de la useri si de pe Internet la toate materiile.

Lista materii:

Am lansat versiunea noua (2010) a programului de facut copiute pentru telefonul mobil!

Am lansat cel mai tare site de metode si tehnici de copiat!

Arbori binari ; generalitati

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.
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 ).