arbori binari

Arbori binari Defiie: Un graf conex i fr cicluri se numete arbore.Proprieti care caracterizeaz un arbore:

exist un nod n care nu intr nici un arc, numit rdcina arborelui

cu excepia rdcinii, fiecare nod are proprietatea c n el intr un singur arc. Acesta leag nodul respectiv de un alt nod numit predecesor sau printe

dintr-un nod pot iei unul sau mai multe arce. Fiecare astfel de arc, leag nodul respectiv de un alt nod numit succesor sau fiu al nodului

nodurile sunt organizate pe nivele, primul nivel fiind ocupat de nodul rdcin. Nodurile de pe ultimul nivel se caracterizeaz prin faptul c din ele nu mai iese nici un arc, i se numesc noduri terminale sau frunze.

nodurile pot conine o aa-numit informaie util care poate fi de orice tip. De obicei aceste informaii se numesc i chei ale arborelui;Definiie: un arbore cu proprietatea c fiecare nod, cu excepia frunzelor are cel mult doi descendeni (succesori) se numete arbore binar. ntr-un arbore binar cei doi succesori ai unui nod (dac exist) se numete succesor stng respectiv succesor drept.

Definiie: un arbore cu proprietatea c fiecare nod cu excepia frunzelor are exact doi descendeni se numete arbore binar complet.

Reprezentarea arborilor binari folosind alocarea dinamic ilustreaz mult mai sugestiv legturile dintre noduri. Chiar dac scopul crerii unui arbore este acela de a memora n noduri nite informaii utile, totui la fel de importante sunt i legturile dintre noduri. Folosind alocarea dinamic, n fiecare nod se va memora att informaia util ct i legturile nodului ctre succesorii si. Cu alte cuvinte n fiecare nod vom avea trei elemente: o informaie(de orice tip predefinit sau definit anterior);

dou adrese a succesorului stg. i a succesorului drept (pointeri ctre succesorul stg. respectiv dr.)

?-type PNOD=^NOD;NOD=record

info:integer;

st,dr:PNOD;end;

Parcurgerea arborilor binariPrin parcurgerea unui arbore binar, se nelege vizitarea tuturor nodurilor pe rnd ntr-o anumit ordine.

Un arbore binar poate fi privit ca un ansamblu de trei entiti: rdcina, un subarbore stg al rdcinii i un subarbore drept al rdcinii. Se viziteaz rdcina apoi se parcurge subarborele stg al rdcinii, iar n final se parcurge subarborele drept al rdcinii. Parcurgerea fiecruia dintre cei doi subarbori este absolut similar: subarborele n cauz poate fi privit ca un arbore alctuit din trei componente: o rdcin, un subarbore stg i un subarbore drept al rdcinii. Cu noii subarbori obinui se va proceda la fel .a.m.d. Procesul continu pn cnd nu mai avem subarbori, moment n care putem spune c au fost vizitate toate nodurile, ca rdcini ale unor subarbori. Urmare a acestei similitudini este clar c algoritmul de parcurgere poate fi descris n termeni recursivi. Exist trei algoritmi de parcurgere:1. Algoritmul RSD( rdcin subarbore stg subarbore drept sau parcurgerea n preordine)- se viziteaz mai nti rdcina, apoi subarborele stg al rdcinii i n final subarborele drept al rdcinii. Procedure RSD (p:PNOD);Begin

If pNIL then

Write(p^.info);

RSD(p^.st);

RSD(p^.dr)