Arbore binar

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