Lucrul cu Structurile Aborescente

Laborator nr. 2 :„ Lucru cu structurile arborescente ”

Tema: „Arbori binari”

Scopul raportului:Raportul dat are ca scop de a studia noţiunea de arbore binar şi construirea sa Determinarea esenţa structurilor arborescente ,efectuarea operaţiilor cu arboriii binari Studierea şi implementarea metodelor de parcurgere a arborilor

Cuprinsul Raportului:

Sarcina 2

1.Construirea uni arbore binar complet de nivelul 3, în limbajele C++ 2

2.Parcurgerea arborelui prin metoda preordine, inordine şi postordine 4

Concluzie 6

Bibliografie 7

1. Construirea uni arbore binar complet de nivelul 3, în limbajele C++

Un arbore binar este un arbore orientat în care fiecare vârf are cel mult doi descendenti, făcându-se însă distincţie clară între descendentul drept şi descendentul stâng al fiecărui vârf. Se acceptă şi arborele binar cu 0 vârfuri. Arborii binari nu reprezintă cazuri particulare de arbori orientaţi, decât dacă se face abstracţie de distincţia menţionată între descendentul drept şi cel stâng al fiecărui vârf. Într-adevăr dacă un vârf are un singur descendent, această informaţie este suficientă în cazul unui arbore, dar insuficientă în cazul unui arbore binar, când trebuie precizat dacă acest descendent este descendent stâng sau descendent drept.

Se prezintă în continuare cîteva modalităţi de definire a arborilor binari în Haskell.

data Tree a = Nil | T(Tree a, a, Tree a)

data Tree a = Nil | T Tree a a Tree a

Pentru a afişa structurile de date arborescente într-un mod similar cu listele sau tipurile de date simple, este necesara extinderea clasei Show, prin intermediul căreia se realizează afişarea 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 structură de tip arbore, elementele sunt structurate pe nivele ; pe primul nivel, numit nivel 0, există un singur element numit rădăcină, de care sunt legate mai multe elemente numite fii care formează nivelul 1; de acestea sunt legate elementele de pe nivelul 2 ş. a. m. d. Un arbore este compus din elementele numite noduri sau vârfuri şi legăturile dintre acestea. Un nod situat pe un anumit nivel este nod tată pentru nodurile legate de el, situate pe ivelul următor, acestea reprezentând fiii săi. Fiecare nod are un singur tată, cu excepţia rădăcinii care nu are tată. Nodurile fără fii se numesc noduri terminale sau frunze. Termenii ' nod tată', 'fiu' sau 'frate' sunt preluaţi de la arborii genealogici, cu care arborii se aseamănă foarte mult.

Deosebit de utilizată în aplicaţii este structura de tip arbore binar. Un arbore binar este un arbore în care fiecare nod are cel mult doi fii, fiul stâng şi fiul drept (fiul stâng este legat în stânga tatălui şi cel drept în dreapta). Dacă în figură se elimină rădăcina şi legăturile ei, se obţin doi arbori binari care se numesc subarborii stâng şi drept ai arborelui iniţial. Arborele binar este, deci, o structură recursivă de date. Un arbore binar nevid fie se reduce la rădăcină, fie cuprinde rădăcina şi, cel mult, doi subarbori binari. Un arbore binar se poate implementa foarte uşor cu ajutorul adreselor de înlănţuire, fiecare element cuprinzând, în afară de informaţia proriu-zisă asociată nodului, adresa fiului stâng şi adresa fiului drept, acestea exprimând legăturile existente între noduri.Arborele binar este ordonat ,deoarece în fiecare ,nod subarborele stîng se consideră că precede subarborele drept Un nod al unui arbore binar poate să aibă numai un descendent Acesta poate fi subarborele stîng sau subarborele drept.