Arbori binari

Arbori binari

Marime: 29 kb
Descarcari: 13

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. Arborii, ca structuri dinamice de date, au extrem de multe aplicaţii în informatică. 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. Implementarea arborilor binari Dacă se recurge la implementarea arborilor prin structuri dinamice, atunci această constantă se reprezintă prin NIL. Tipul informaţiilor ataşate nodurilor dintr-un arbore este specific fiecărei aplicaţii în parte. Din acest motiv, vom considera că informaţia ataşată fiecărui nod este adrestă indirect prin intermediul unui pointer. În majoritatea implementărilor şi cei doi subarbori sunt adresaţi indirect; în funcţie de varianta de implementare - dinamică sau statică - , adresarea se realizează fie prin intermediul pointerilor, fie prin intermediul indicilor de tablou.

DESCARCA