arbori binari

2
Arbori binari Defiţie: Un graf conex şi fără cicluri se numeşte arbore. Proprietăţi care caracterizează un arbore: - există un nod în care nu intră nici un arc, numit rădăcina arborelui - cu excepţia rădăcinii, fiecare nod are proprietatea că în el intră un singur arc. Acesta leagă nodul respectiv de un alt nod numit predecesor sau părinte - dintr-un nod pot ieşi 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 rădăcină. 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 conţine o aşa-numită informaţie utilă care poate fi de orice tip. De obicei aceste informaţii se numesc şi chei ale arborelui; Definiţie: un arbore cu proprietatea că fiecare nod, cu excepţia frunzelor are cel mult doi descendenţi (succesori) se numeşte arbore binar. Într-un arbore binar cei doi succesori ai unui nod (dacă există) se numeşte succesor stâng respectiv succesor drept. Definiţie: un arbore cu proprietatea că fiecare nod cu excepţia frunzelor are exact doi descendenţi se numeşte arbore binar complet. Reprezentarea arborilor binari folosind alocarea dinamică – ilustrează mult mai sugestiv legăturile dintre noduri. Chiar dacă scopul creării unui arbore este acela de a memora în noduri nişte informaţii utile, totuşi la fel de importante sunt şi legăturile dintre noduri. Folosind alocarea dinamică, în fiecare nod se va memora atât informaţia utilă cât şi legăturile nodului către succesorii săi. Cu alte cuvinte în fiecare nod vom avea trei elemente: - o informaţie(de orice tip predefinit sau definit anterior); - două adrese a succesorului stg. şi a succesorului drept (pointeri către succesorul stg. respectiv dr.) ?- type PNOD= ^ NOD; NOD=record info:integer; st,dr:PNOD; end; Parcurgerea arborilor binari Prin parcurgerea unui arbore binar, se înţelege vizitarea tuturor nodurilor pe rând într-o anumită ordine. Un arbore binar poate fi privit ca un ansamblu de trei entităţi: rădăcina, un subarbore stg al rădăcinii şi un subarbore drept al rădăcinii. Se vizitează rădăcina apoi se parcurge subarborele stg al rădăcinii, iar în final se parcurge subarborele drept al rădăcinii. Parcurgerea fiecăruia dintre cei doi subarbori este absolut similară: subarborele în cauză poate fi privit ca un arbore alcătuit din trei componente: o rădăcină, un subarbore stg şi un subarbore drept al rădăcinii. Cu noii subarbori

Upload: aninis-mihaela

Post on 08-Nov-2015

218 views

Category:

Documents


3 download

TRANSCRIPT

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)