MINISTERUL EDUCA IEI,CERCETĂRII,TINERETULUI IȚ Ș SPORTULUI

COLEGIUL TEHNIC MĂTĂSARI

PROF. COORDONATOR:SĂCEANU ION

ELEV:CIORTAN

ALEXANDRA ANDREEA

CLASA a XII-a BPROFIL:

Matematică-Informatică

1

2

MINISTERUL EDUCA IEI,CERCETĂRII,TINERETULUI IȚ Ș SPORTULUI

COLEGIUL TEHNIC MĂTĂSARI

PROF. COORDONATOR:SĂCEANU ION

ELEV:CIORTAN

ALEXANDRA ANDREEA

CLASA a XII-a BPROFIL:

Matematică-Informatică

3

4

Cuprins

Capitolul I.FORMULAREA TEMEI....................................................................3

1.1.ASPECTE GENERALE LEGATE DE TEMA LUCRĂRII .

DOMENIUL ĨN CARE SE ĨNCADREAZĂ LUCRAREA.....................................3

1.2.EXPLICAREA PROBLEMEI PROPUSE SPRE REZOLVARE....................3

1.3.EXPLICAŢII FINALE LEGATE DE TEMA PROPUSĂ

UTILITATEA TEMEI, ASPECTE REZOLVATE DE ACEASTA, POSIBILITĂŢI DE

DEZVOLTARE A TEMEI....................................................................................4

ARBORI......................................................................................................5

OPERATII ELEMENTARE..........................................................................6 ARBORI PARTIALI....................................................................................8ARBORI BINARI.......................................................................................11 ALGORITMI ELEMENTARI.....................................................................14ARBORI DE SORTARE............................................................................20EVALUREA EXPRESIILOR ARITMETICE...............................................28FORMA POLONEZA A EXPRESIILOR ARITMETICE.............................29BIBLIOGRAFIE.........................................................................................37

5

Capitolul I.FORMULAREA TEMEI

1.1.ASPECTE GENERALE LEGATE DE TEMA LUCRĂRII .

DOMENIUL ĨN CARE SE ĨNCADREAZĂ LUCRAREA

Ĩn momentul de faţă prelucrarea informaţiilor de orice natură cu

ajutorul computerului este utilizată ĩn toate domeniile. Deoarece costul unui

calculator nu este atât de mare şi majoritatea şcolilor au ĩn dotare astfel de

echipamente, ĩnsuşirea cunoştinţelor teoretice din domeniul informaticii se

poate mult ĩmbunătăţi prin utilizarea unor produse soft specializate. Partea

aplicativă constituie o verigă foarte importantă a informaticii şi de aceea,

elevii au nevoie de exerciţiu.

Lucrarea este utilă atât elevilor interesaţi de studiul acestei

discipline,cât şi profesorilor , la lecţiile curente cât şi în cadrul celor

recapitulative.

1.2.EXPLICAREA PROBLEMEI PROPUSE SPRE REZOLVARE

Problema propusă spre rezolvare este de fapt o prezentare completă

a notiunilor teoretice legate de arbori. Fiecare subcapitol cuprinde în afara

prezentării teoretice ( text şi imagini), urmată de o colecţie de programe

aplicative si de o analiză a complexitătii acestoara. Programele sunt descrise

ĩn detaliu ĩn capitolul al II-lea, fiecare dintre ele având numeroase comentarii

care să permită ĩnţelegerea uşoară a metodei de rezolvare, modificarea

totală sau parţială a unei aplicaţii precum şi efectuarea unor operaţii dificile.

Rularea pas cu pas a unei astfel de aplicaţii şi urmărirea rezultatelor parţiale

au un rol parctic foarte important pentru ĩnsuşirea metodei de rezolvare.

Fiecare problemă rezolvată are un format foarte plăcut de introducere

a datelor de intrare şi de afişare a celor de ieşire astfel ĩncât rularea unui

program să fie o plăcere pentru utilizator. Aplicaţiile sunt realizate astfel

ĩncât să nu introducă date eronate.

Noţiunile sunt prezentate gradat, de la cele generale ( arbori văzuţi ca

şi grafuri) până la cazurile particulare ( arbori binari şi de sortare).

6

Lucrarea se încheie cu o aplicaţie interesantă a arborilor – turnee

sort- un exemplu de utilizare eficientă a arborilor.

1.3.EXPLICAŢII FINALE LEGATE DE TEMA PROPUSĂ

UTILITATEA TEMEI, ASPECTE REZOLVATE DE ACEASTA,

POSIBILITĂŢI DE DEZVOLTARE A TEMEI

Utilizarea acestei colecţii de programe are o serie de avantaje

foarte evidente, dintre care enumerăm

confirmarea practică a unor rezultate teoretice

insuşirea algoritmilor de rezolvare, prin urmărirea pas cu pas a

programelor şi vizualizarea rezultatelor parţiale

verificarea dobândirii cunoştinţelor prin lucrul ĩn paralel elev-

calculator

sesizarea progreselor făcute de elevi prin rularea repetată a

unei aplicaţii şi realizarea unei reprezentări a timpului de

răspuns

Posibilităţi de dezvoltare a temei există şi cred că cele mai

importante ar fi următoarele:

adăugarea unei secţiuni care să cuprindă teste grilă cu

itemi rezultaţi din parcurgerea unui modul (arbori,arbori

binary, arbori de sortare)

realizarea unui parallelism grafuri orientate-arbori

7

ARBORI

Definiţie:Un graf conex şi fără circuite se numeşte arbore.Un graf neconex ale cărui componente conexe sunt arbori se numeşte pădure.

Un arbore pentru care se precizează un nod numit rădăcină iar celelalte noduri pot fi repartizate în mulţimi disjuncte, astfel încât în fiecare dintre aceste mulţimi există un nod vecin cu rădăcină iar subgrafurile generate de acestea au aceeaşi proprietate se numeşte arborescenţă..Dacă ordinea subgrafurilor are importanţă atunci arborescenţa se numeşte arbore ordonat.

Grafic nodurile unei arborescenţe se desenează pe nivele.Rădăcina se află pe nivelul 0, vârfurile vecine pe nivelul 1, şi aşa mai departe. Numărul de nivele determină adâncimea arborelui.

Exemple Graful

este un arbore

Dacă precizăm că nodul 2 este rădăcina arborelui atunci putem reprezenta arborescenţa:

-nivel 0 -nivel 1

-nivel 2

-nivel 3

fig.1

8

Dacă nodul v se găseşte pe nivelul k, atunci toate nodurile de pe nivelul k+1,vecine cu nodul v se numesc descendenţii nodului v.Spunem în acest caz că nodul v este nod tată.Descendenţii aceluiaşi nod se numesc fraţi. Nodurile care nu au descendenţi se numesc frunze.Pentru arborescenţa de mai sus avem : -nodul 3 are descendenţii 1,5 şi 4

-nodul tată al frunzei 6 este 4

OPERATII ELEMENTARE

Pentru a putea realiza prelucrarea unei arborescenţe trebuie să găsim o structură care să permită reprezentarea ei.Vom utiliza structuri dinamice pentru memorarea valorilor din nodurile arborescenţei;Declaraţiile

const max=10;type point=^nod; nod=record cheie,nrfii:byte; fiu:array[1..max] of point end;

precizează că pentru fiecare nod al arborescenţei memorăm informaţia (cheie), numărul de fii şi avem un vector cu pointeri spre descendenţi.

var rad:point; desemnează un pointer spre nodul rădăcină.

Construcţia arborescenţei se realizează conform algoritmului:

Pentru nodul curent citim numărul de fii, alocăm memorie pentru memorarea informaţiilor din fii, citim valorile fiilor şi reluăm procedeul pentru fiecare dintre fii.Precizăm că valoarea din rădăcină se citeşte în programul principal şi se apelează procedura constr cu parametrul rad.

procedure constr(var p:point);var i:byte;

9

begin if p<>nil then begin write('Nr. de fii ai nodului cu cheia ',p^.cheie,' '); readln(p^.nrfii); for i:=1 to p^.nrfii do begin new(p^.fiu[i]); write(' Cheia din fiul ',i,' al nodului cu cheia ',p^.cheie,' '); readln(p^.fiu[i]^.cheie); end; for i:=1 to p^.nrfii do constr(p^.fiu[i]); endend;.……...{programul principal}new(rad);write('Cheia din nodul radacina ');readln(rad^.cheie);constr(rad);………….

Afişarea nodurilor din arborescenţă se poate face în două moduri în adâncimeAfişarea se face recursiv, scriind valoarea din nodul curent şi

repetând procedeul pentru fiecare fiu al acestuia.

procedure afisadanc(p:point);var i:byte;beginif p<>nil then begin write(p^.cheie,' ('); for i:=1 to p^.nrfii do afisadanc(p^.fiu[i]); write(')') end end;

în lăţimeSe utilizeză o coadă în care păstrăm pointeri la nodurile de pe nivelul curent

lista=^nodl; nodl=record val:point; urm:lista end;

-subprogramul care afişează coada se apelează pentru fiecare nivel; în acelaşi subprogram calculăm numărul de noduri de pe nivelul curent

function afislista(p:lista):byte;var k:byte;begin k:=0; while p<>nil do begin write(p^.val^.cheie,' ');

p:=p^.urm;inc(k);

Pentru arborescenţa din fig.1 obţinem şirul:2,3,1,5,4,6

10

end; afislista:=kend;

Paşii algoritmului care realizează afişarea în lăţime sunt:Pas 1:se introduce pointerul spre nodul radăcină în coadăPas 2:afişăm nodurile din coadăPas3:se parcurge coada şi se adaugă în coada toţi descendenţii nodurilor din coadă şi se şterg nodurile afişate(ştergerea unui element se realizează după ce s-au introdus în coadă fii acestuia)Se repetă paşii 2 şi 3 până când obţinem coadă vidă

procedure afislat;

var prim,ultim,q:lista; n,i,j:byte;beginnew(prim);prim^.val:=rad;prim^.urm:=nil;ultim:=prim;while prim<>nil do begin n:=afislista(prim);writeln; {se adaugă în listă fii corespunzatori nodurilor din coada curentă şi se şterg nodurile afişate} for i:=1 to n do begin for j:=1 to prim^.val^.nrfii do begin new(q); q^.val:=prim^.val^.fiuşj]; q^.urm:=nil; ultim^.urm:=q; ultim:=q end; q:=prim;prim:=prim^.urm; dispose(q) end endend;

ARBORI PARTIALI

Definiţie:Fie G=(V(G),M(G)) un graf neorientat.Se numeşte arbore parţial al grafului G, un graf parţial care este arbore.Din această definiţie se poate deduce că există arbori parţiali numai în cazul grafurilor conexe.

Vom considera în continuare graful ponderat.Fiecărei muchii ij din graf i se asociază un număr strict pozitiv numit costul muchiei notat cu cost(ij).Rezultă de aici că avem funcţia cost:M(G)->R+

11

Definim costul unui arbore ca fiind suma costurilor muchiilor sale

Exemplu:Pentru graful

muchiile punctate marchează un arbore parţial

Problemă:Să se construiască şi să se afişeze un arbore parţial de cost minim.

Algoritmul lui Kruskal permite determinarea arborelui parţial de cost minim

Pentru aceasta se pleacă de la n componente conexe,fiecare componentă conexă conţinând un singur nod.

Exemplu:pentru graful reprezentat mai jos

avem initial

.1 .2 3 4 5

componenta componenta componenta componenta componenta conexă nr.1 conexă nr.2 conexă nr.3 conexă nr.4 conexă nr.5

La fiecare pas se selectează o muchie de cost minim care nu a mai fost aleasă şi care nu formează circuite cu cele deja selectate.(o muchie se adaugă în arborele parţial numai dacă uneşte 2 noduri din componente conexe diferite).

1 3 3

1 1

2 2 4

12

Cost (G )= ∑m∈M(G )

cos t(m )

In programul Kruskal.pas tabloul g conţine pe fiecare coloană capetele unei muchii,costul său şi o variabilă ce precizează apartenenţa la arborele de cost minim.

Pentru graful prezentat avem:Pasul 1:se selectează muchia 1-2 ce are costul 1 .Nodurile 1 si 2 se află în componente conexe diferite şi se unifică componente conexe 1 si 2.

1 2 3 4 5

componenta componenta componenta componenta conexă nr.1 conexă nr.3 conexă nr.4 conexă nr.5 Pasul 2: alegem muchia 1-4 ce are costul 1.Componenta convexă în care se găseşte nodul 1este diferită de componenta conexă corespunzătoare nodului 4 şi deci cele două componente conexe vor fi reunite. 1

4 2 .3 . 5 componenta componenta componenta conexă nr.1 conexă nr.3 conexă nr.5 Pasul 3: se alege muchia 2-4.Nu se adaugă pentru că nodurile 2 si 4 sunt în aceeaşi componentă conexă.

Pasul 4: alegem muchia 1-3.Se unifică componentele conexe nr.1 şi nr. 3;

1

5 4 2 3

componenta componenta conexă nr.1 conexă nr.3 Pasul 5: selectăm muchia 4-5 ce are costul 3;

1

13

4 2 3 5

componenta conexă nr.1

Algoritmul se termină atunci când ajungem la o singură componentă conexă(Un arbore este un graf conex fară circuite şi conţine n-1 muchii). program Kruskal; uses crt; const max=30; var a:array[1..4,1..max] of integer; n,m,i,j,nrcomp,k:integer; comp_con:array[1..max] of 0..max; procedure citire;{se introduc elementele grafului} var i:1..max; begin clrscr;write('Ordinul grafului:');readln(n); write('dimensiunea grafului:');readln(m); for i:=1 to m do begin write('muchia ',i,' : ');readln(a[1,i],a[2,i]);

write('costul muchiei ',a[1,i],' ',a[2,i],' : '); readln(a[3,i]); a[4,k]:=0

end end;{se ordonează muchiile pentru a fi considerate în ordine crescătoare} procedure ordonare_dupa_cost; begin for i:=1 to m-1 do for j:=i+1 to m do if a[3,i]>a[3,j] then begin k:=a[1,i];a[1,i]:=a[1,j];a[1,j]:=k; k:=a[2,i];a[2,i]:=a[2,j];a[2,j]:=k; k:=a[3,i];a[3,i]:=a[1,j];a[3,j]:=k; endend;begincitire;ordonare_dupa_cost;{afi[ăm muchiile ordonate}for k:=1 to 3 do begin for i:=1 to m do write(a[1,i],' ');writeln;

end;for i:=1 to n do comp_con[i]:=i;{iniţializarea}k:=1;nrcomp:=n; {k=numarul de componente conexe}while (k<=m) and (nrcomp>1) do begin{analizează muchia k} if comp_con[a[1,k]]<>comp_con[a[2,k]] then begin a[4,k]:=1;{dacă uneşte două vârfuri diferite se adaugă în arbore}

14

for i:=1 to n do if comp_con[i]=comp_con[a[2,k]] then comp_con[i]:=comp_con[a[1,k]]; dec(nrcomp) end; inc(k) end; if nrcomp>1 then write('Graful nu este conex') else begin write('Arb. partial de cost minim contine muchiile: '); for i:=1 to k do if a[4,i]=1 then

write('(',a[1,i],'',a[2,i],')')end;readlnend.

ARBORI BINARI

Definiţie:Un arbore binar este o muţime finită A de noduri care poate fi

a)mulţimea vidăb)un arbore ordonat în care fiecare nod are cel

mult doi descendenţi.Pentru fiecare nod dintr-un arbore binar distingem

fiul stâng şi fiul drept.Fiul stâng este rădăcina subarborelui stâng iar fiul drept rădăcina subarborelui drept.Reamintim că un nod care nu are fii se numeşte frunză.(sau nod pendant).Vom indica pentru fiecare nod o ,,informaţie utilă” şi legăturile spre fii.

Un arbore binar în care fiecare nod nependant are exact doi fii se numeşte arbore binar complet.

Exemple: rădăcina arborelui binar Acest arbore nu este complet(nodul 3 are un fiu)

Subarborele stâng al nodului 2 Subarborele drept al nodului 2

15

frunze fig.2

Arborele din fig.3 este complet.

fig.3

Un arbore binar în care fiecare nod nependant are exact doi fii şi toate frunzele se găsesc pe acelaşi nivel se numeşte arbore binar plin.

Din această definiţie rezultă că avem 2k-1 noduri dispuse pe nivelurile 0,1,…k-1 şi pe fiecare nivel j avem 2j noduri.

Această proprietate se demonstrează foarte simplu prin inducţie.Pe nivelul 0 avem un singur nod, nodul rădăcină.Numărul de noduri de pe nivelul 0 este egal cu 20.

Presupunem prin inducţie că pe fiecare nivel t avem 2t

noduri, pentru tn.Demonstrăm relaţia pentru nivelul n+1.Fiecare nod de pe nivelul n are exact doi fii.Rezultă de aici că pe nivelul n+1 avem 2*2n=2n+1 noduri.Rezultă de aici

Proprietatea1.Numărul de noduri dintr-un arbore binar plin de înălţime h este egal cu 20+21+22+……+2h=2h+1-1.

Exemplu:

fig.4

Proprietatea2.Un arbore binar plin cu n frunze conţine 2n-1 noduri şi are înălţimea log2(n).

16

Numărul de noduri de pe nivelul k este egal cu 2k.Fie m ultimul nivel.Pe acest nivel vom avea 2m noduri care sunt frunze.Rezultă de aici că n=2m(numărul de frunze într-un arbore binar plin este o putere a lui 2).m=log2(n) şi reprezintă în acelaşi timp înălţimea arborelui.Conform proprităţii 1 avem în arbore un număr total de noduri egal cu 2m+1-1 = 2*2m+1=2n-1.

Un arbore binar echilibrat este un arbore binar în care, pentru orice nod diferenţa dintre numărul nodurilor din subarborele stâng şi numărul celor din subarborele drept este de cel mult o unitate.

Exemplu:

fig.5Observaţii:

Orice arbore binar conţine pe nivelul k cel mult 2k

noduri.Am demonstrat că un arbore binar plin conţine pe fiecare nivel

k exact 2k noduri.Din definiţia arborelui binar plin rezultă că acesta este numărul maxim de noduri ce pot exista pe un nivel k(fiecare nod neterminal are exact 2 descendenţi, număr care este maxim)

Dacă arborele binar are f(f>0) frunze atunci există f-1 noduri ce au exact doi fii în arbore.

Dacă N este numărul total de noduri din arbore atunci numărul nodurilor cu doi fii(pe care îl notăm cu n2) este egal cu N-f-numărul nodurilor cu un singur fiu(notat n1).Relaţia se scrie N=f+n1+n2.(*).

Fiecare nod din arbore, cu excepţia rădăcinii este fiul unui alt nod.Rezultă de aici că avem N-1 fii în arbore.Aceşti fii pot fi unici sau pot avea un frate.Vom nota cu f1 fii unici şi cu f2 fii ce au un frate.Obţinem deci N-1=f1+f2.(**)~ntre nodurile cu un singur fiu şi fiii unici există o corespondenţă biunivocă(fiecare tată corespunde fiului unic), ceea ce revine la f1=n1.Fiecare nod cu doi fii intervine de două ori în suma f2(câte o dată pentru fiecare fiu).Avem deci f2=2n2.

17

Din(**) avem N=1+f1+f2=1+n1+2n2 şi (*) N=f+n1+n2.Rezultă de aici 1+n1+2n2=f+n1+n2 ceea ce implică n2=f-1.

ALGORITMI ELEMENTARI

Reprezentarea arborilor binari se poate realiza cu ajutorul structurilor statice sau cu ajutorul structurilor dinamice.Pentru fiecare nod trebiue să memorăm o cheie(care specifică informaţia utilă ataşată nodului”)şi legăturile spre fii.

~n primul caz putem utiliza a)doi vectori S şi D în care ,pentru fiecare vârf i

specificăm în S[i] fiul stâng iar în D[i] fiul drept.Cheia din nod se păstrază în alt vector cheie.Lipsa unui fiu este dată de valoarea 0.Se precizează în variabila rad nodul rădăcină.Exemplu: pentru arborele din figura 6 în care sunt trecute cheile avem reprezentarea (rad=2):

fig.6

D 3 5 0 0 0 8 0 0S 2 4 6 0 0 7 0 0

Cheie 2 4 3 5 1 6 7 10Nod 1 2 3 4 5 6 7 8

Nu este necesar să memorăm rădăcina (este nodul care nu are tată => nu apare în tabel pe nici o linie)

b)doi vectori tată si fiu, în care pentru fiecare nod i se precizează nodul tată în tata[i] şi se pune în fiu [i] valoarea –1 dacă i este descendent stâng, valoarea 1 dacă este descendent drept şi 0 dacă i este rădăcină.Se păstrază vectorul cheie cu acceaşi semnificaţie.

18

Pentru acelaşi exemplu avem reprezentarea:Tata 0 1 1 2 2 3 6 6Fiu 0 -1 1 -1 1 -1 -1 1

Cheie 2 4 3 5 1 6 7 101 2 3 4 5 6 7 8

~n reprezentarea cu ajutorul structurilor dinamice, fiecare nod este de tipul

type arb=^nod; nod=record cheie:tip_cheie; st,dr:arb end;

unde cheia ataşată fiecărui nod poate fi de tipul dorit.~n reprezentarea grafică pointerii st şi dr sunt reprezentaţi prin intermediul săgeţilor iar cheia se scrie în fiecare nod.

Generarea arborilor binariPentru a prelucra un arbore binar trebuie să-l construim.Procedura de mai jos realizează generarea recursivă a arborelui(valoarea nil a unui nod este indicată de ‘.’).~n procedură am ales cheia de tip char dar se poate alege orice tip şi în locul caracterului ‘.’ Putem alege o altă constantă de tipul cheii care să indice valoarea nil.Pentru fiecare nod diferit de nil se citeşte cheia şi se apelează procedura pentru fii.

procedure constr(var p:arb);var c:char;beginreadln(c);{dacă se introduce . atunci nodul este nil}if c<>'.' then begin new(p);p^.cheie:=c; writeln('Fiul stang al nodului ',c); constr(p^.st); writeln('Fiul drept al nodului ',c);constr(p^.dr) end else p:=nil end;

Un arbore binar poate fi parcurs utilizând modalităţile generale de parcurgere a unui arbore (în adâncime şi pe lăţime) dar există şi alte trei modalităţi de a parcurge un arbore binar .~n toate cazurile fiul stâng este prelucrat înaintea celui drept pentru orice nod din arbore.

19

a) parcurgerea în preordine-rădăcina este prelucrată înaintea subarborelui stâng

procedure preordine(p:arb);beginif p<>nil then begin write(p^.cheie,' ');

preordine(p^.st); preordine(p^.dr)

endend;

Pentru arborele binar din fig.6 obţinem şirul: 2,4,5,1,3,6,7,10

b) parcurgerea în inordine-rădăcina este prelucrată după prelucrarea subarborelui stâng şi înainte de prelucrarea celui drept.

procedure inordine(p:arb);beginif p<>nil then begin inordine(p^.st); write(p^.cheie,' '); inordine(p^.dr) endend;

Pentru arborele binar din fig.6 obţinem şirul: 5,4,1,2,7,6,10,3

c) parcurgerea în postordine-rădăcina este prelucrată după prelucrarea subarborelui drept

procedure postordine(p:arb);beginif p<>nil then begin postordine(p^.st); postordine(p^.dr); write(p^.cheie,' ') endend;

Extragerea informaţiilor statistice

a)determinarea numărului de frunze dintr-un arbore binar se realizează cu ajutorul unei funcţii frunza(p:arb) ce calculează recursiv numărul de frunze din subarborele cu radăcina p. Această funcţie cercetează nodul p şi dacă acesta este frunză(fiul drept şi cel stâng cu valoarea nil)atunci întoarce valoarea 1 iar altfel numărul de frunze din subarborele cu rădăcina p va fi egal cu

20

suma dintre numărul de frunze din subarborele stâng şi numărul de frunze din subarborele drept.~n cazul în care subarborele curent este vid funcţia întoarce valoarea 0.

function frunza(p:arb):integer;beginif p<>nil then if (p^.st=nil)and (p^.dr=nil)then frunza:=1 else frunza:=frunza(p^.st)+frunza(p^.dr)

else frunza:=0 end;

b)calculul înălţimii unui arbore binarVom considera că înălţimea unui arbore ce conţine un singur nod(numai rădăcina) este 0.Pentru a calcula înălţimea unui arbore cu rădăcina p folosim următoarea definiţie

Definiţia este corectă pentru că fiecare nod tată p este legat de fiecare fiu printr-o muchie care contribuie cu o unitate la înălţimea arborelui de rădăcină p. p

1+ p^.st p^.dr

max(înălţime subarb. stâng, înălţime subarb. drept)

function inaltime(p:arb):integer;var m,n:integer;beginif p<>nil then begin m:=inaltime(p^.st);

n:=inaltime(p^.dr);if m>n then inaltime:=m+1

21

`n\l ] ime( p)=¿ {−1 ,dac\arborele este vid ¿ ¿¿

¿¿

else inaltime:=n+1end

else inaltime:=-1 end;

d) Numărarea arborilor binariFie n R+.Să se calculeze numărul de arbori binari distincţi cu n noduri.Vom nota cu A(n) numărul arborilor cu n noduri.-pentru n=0 avem un singur arbore (vid) iar pentru n=1 tot un arbore ce conţine numai rădăcina.Avem deci A(0)=A(1)=1;-pentru n=2 avem doi arbori(rădăcina şi fiul stâng sau rădăcina şi fiul drept)-pentru n=3 avem A(3)=5 arbori de forma

-pentru un n oarecare vom numerota nodurile din arbore cu 1,2…,n.Fiecare nod i din cele n poate fi rădăcină.Vom avea în subarborele stâng i-1 noduri şi în subarborele drept n-i noduri.Numărul de arbori ce au rădăcina i fixată este egal cu produsul A(i-1)*A(n-i) pentru că există A(i-1) arbori ce se pot forma cu cele i-1 noduri din subarborele stâng şi fiecăruia dintre ei i se poate asocia unul din cei A(n-i) arbori ce pot forma subarborele drept al nodului i.Relaţia fiind adevărată pentru orice i din intervalul [1,n] rezultă că

Pentru a rezolva recurenţa vom considera funcţia

22

f ( x )=∑n≥0

A (n )Xn

d ac\ `nmul ] im ambii termeni ai rela ] iei de recuren ] \cuXn ob ] inem

A(n )Xn=∑i=1

n

A( i−1 )∗A (n−i )X n⇔ A (n )Xn=X∑i=1

n

[ A ( i−1 )X i−1 ]∗[ A (n−i )Xn-i ] ,∀n≥1

Vom face sum\ dup\n≥1⇒

∑n≥1

A( n)Xn=∑n≥1∑i=1

n

[ A( i−1 )X i−1 ]∗[ A (n−i)Xn-i ]=X∗¿¿

¿

¿

A(n )=¿ {1,dac\n=0sau n=1 ¿ ¿¿¿

Ceea ce indică f(x)-A(0)=X*f 2(X).Notăm f(x) =t şi rezolvăm ecuţia de gradul 2 în t X t2- t+A(0)=0 cu A(0)=1 =1-4X

Vom aplica dezvoltarea binomială pentru g(x)=(1-4X)1/2.Pentru aceasta calculăm mai întâi derivata de ordin n pentru

funcţia g(x). Avem în acest caz

23

t1,2=1±√1−4 X

2 X

g (x )'=(−4 )12(1−4 X )

12−1

g (x )' '=(−4 )2 12∗(12 −1)(1−4 X )

12−2

presupunem prin induc ] ie g( x )(n )=(−4 )n∗12∗(12−1)∗. .. . .∗(12−(n−1 ))(1−4 X )

12−n

[ i demonstr\m rela ] ia pentru n+1

g (x )(n+1)=( g( x )(n))'=((−4 )n∗12∗(12 −1)∗. .. ..∗(12−(n−1 ))(1−4 X )

12−n )

′

=>

g (x )(n+1)=(−4 )n+1∗12∗(12 −1)∗. .. ..∗(12−n)(1−4 X )

12−(n+1 )

ceea ce demonstreaz\ rela ] ia

f ( x )=12 x

[1−√(1−4 x ) ]

f ( x )=12 x

[1−∑n≥0

12(12−1) .. . .(1

2−(n−1 ))

n !(−4 x )n ]=>

f ( x )=12 x

∑n≥1

12(12−1 ). .. . .. .(1

2−n+1)

n!(−1)n+1 22 n−1 xn

A(n) este coeficientul lui Xn din dezvoltare şi este egal cu

ARBORI DE SORTARE

Definiţie:Un arbore binar de căutare (arbore de sortare)este un un arbore binar în care fiecare nod are asociată o ,,cheie de căutare” şi fiecare nod neterminal are cheia mai mare decât cheia oricărui nod din subarborele stâng asociat nodului şi mai mică decât cheia oricărui nod din subarborele drept.

O parcurgere în inordine a unui arbore binar de căutare determină ,,vizitarea” nodurilor în ordinea crescătoare a cheilor.

Exemplu:

parcurgerea în in ordine:3 6 7 8 9 10

24

A(n )=(−1 )n22 n+1

12(12−1 ). .. .(

12−n)

(n+1 )!=>

A(n )=(−1 )n22 n+11(1−2)(1−2⋅2)(1−2⋅3) .. . ..(1−2n )2n+1 (n+1)!

=>

A(n )=2n(2n−1 )[2( n−1)−1 ]. . .. .. .. (2−1)(n+1 )!

=>

A(n )=2nn !(2n−1 )[2( n−1 )−1 ]. . .. .. .. .(2−1 )(n+1)!n !

=>

A(n )=(2n)!(n+1)!⋅n !

=1n+1

C2 nn

Operaţii elementare

Construcţia arborilor binari de sortareSe realizează prin inserarea repetată a valorilor dorite în arborele de sortare.Iniţial acesta este vid.Dacă arborele în care se inserează nodul de cheie x este vid atunci rădăcina acestui arbore va fi dată de nodul care se inserează.Pentru un arbore nevid de rădăcină p se compară cheia rădăcinii cu cheia nodului x.Avem următoarele situaţii:

x<cheia rădăcinii p =>inserăm valoarea x în subarborele stâng

x>cheia rădăcinii p => inserăm valoarea x în subarborele drept

procedure inserare(x:tip_cheie;var p:arb);beginif p=nil then begin new(p); p^.cheie:=x; p^.st:=nil;p^.dr:=nil end else

if p^.cheie>x then inserare(x,p^.st)else inserare(x,p^.dr)

end;

Din definiţia arborilor binari de căutare rezultă că nu putem avea două noduri cu aceeaşi cheie.Există, însă în practică foarte multe situaţii când două sau mai multe noduri au aceeaşi cheie şi trebuie să se găsească în arbore.Vom face următoarea convenţie:Dacă în arbore se adaugă un nod care are aceeaşi cheie cu un nod care se inserează atunci acesta se va afla în subarborele drept al nodului cu aceeasi cheie prin acelaşi procedeu..Procedura de inserare cuprinde şi această situaţie.

Exemplu:Pentru a insera valoarea x=6 în arborele trasat cu linii continue vom parcurge drumul indicat de liniile punctate.

X<9

25

x= 6

x<8 x<7

Parcurgerea arborilor se realizează cu ajutorul procedurilor prezentate în cazul general.

Căutarea unui element de cheie x într-un arbore de sortare

Un element din arborele de sortare poate fi găsit parcurgând cel mai scurt drum de la rădăcină la nodul respectiv, astfel încât să se cerceteze un singur nod pe fiecare nivel până când se întâlneşte nodul sau până când se ajunge la nil.Funcţia recursivă caută întoarce valoarea nil dacă nodul de cheie x nu se găseşte înarbore şi un pointer la nodul respectiv în cazul în care se găseşte.Pentru a găsi valoarea x în subarborele cu rădăcina p se compară cheia rădăcinii cu x. Avem următoarele situaţii:

x=cheia rădăcinii p => funcţia cauta va întoarce pointerul p

x<cheia rădăcinii p =>căutăm valoarea x în subarborele stâng

x>=cheia rădăcinii p => căutăm valoarea x în subarborele drept

function cauta(x:tip_cheie;p:arb):arb;beginif (p=nil)or(p^.cheie=x) then cauta:=p else

if p^.cheie>x then cauta:=cauta(x,p^.st)else cauta:=cauta(x,p^.dr)

end;

Dacă avem noduri cu chei egale atunci în procedura precedentă se testează cheia şi celelalte componente ale informaţiei utile pentru a vedea dacă am ajuns la nodul dorit.Deplasarea se face în acelaşi mod.

Exemplu: ~n arborele de căutare următor fiecare nod conţine informaţiile utile cheie şi literă.Se caută nodul ce are cheia c=6 şi litera ‘A’.Liniile punctate descriu traseul urmat de funcţia caută. ‘m’ c>5 ‘u’

26

‘T’ c=6 dar litera’A’ şi se continuă căutarea în dreapta

‘l’ c<10 ‘v’ c<7

c=6 şi litera=’A’ ’A’ ’k’

Vom analiza în continuare complexitatea algoritmului de căutare.Se observă că la fiecare pas căutarea se restrânge la unul dintre subarborii nodului curent.Rezultă de aici că pe drumul de la rădăcină la nodul căutat sau la nil atunci când nodul nu se găseşte vom considera câte un singur nod de pe fiecare nivel.~n cel mai rău caz nodul nu se găseşte în arbore şi se parcurge cel mai lung drum din arbore, drum ce are o lungime egală cu înălţimea arborelui+1.

Exemplu :Pentru a căuta valoarea 13 în arborele următor se parcurge drumul cel mai lung din arbore şi este trasat punctat :

8 5 16 15 18

14 15 17 19 11

12 nil

Numărul de comparaţii efectuate este egal cu numărul nodurilor prin care trecem + o unitate pentru ultimul fiu care este nil.Rezultă de aici că avem o complexitate timp de O(h) unde h este înălţimea arborelui.Atunci când fiecare nod neterminal are exact un descendent obţinem o înşiruire a nodurilor din arbore şi h=n-1 ceea ce implică O(h)= O(n)ceea ce precizează că avem un algoritm de complexitate O(n)

Exemplu:

27

nil

Calculăm în continuare complexitatea în medie a acestui algoritm.Fie arborele ce conţine valorile a1,a2,a3’………,an cu aiai+1 ,i[1,n-1].Vom presupune că probabilităţile cu care se caută numerele a1,a2,..,an sunt egale şi că intervalele (-,a1),(a1,a2)……(an,+) sunt egal probabile 1/n (probabilitatea de a căuta un număr situat în unul din aceste intervale este aceeaşi).Numărul de comparaţii necesar în cazul unei căutări încheiate cu succes este egal cu nivelul pe care se găseşte vârful respectiv +1(rădăcina se află pe nivelul 0).Notăm cu Cn numărul de comparaţii efectuate pentru căutarea cu succes a unei valori în arborele de sortare cu n noduri.Pentru n=1 avem Cn=1.~n cazul unui arbore cu n>1

noduri,oricare dintre cele n elemente se poate afla în rădăcină.Fie ak acel element.Rezultă de aici că în subarborele stâng se vor afla k-1 elemente şi în subarborele drept n-k elemente,ceea ce indică:

Pentru a găsi un element x într-un subarbore trebuie să comparăm mai întâi x cu valoarea din rădăcină, deci vom avea n-1 comparaţii făcute pentru elemente din subarborii rădăcinii.C0=0 prin definiţie.

Scriem relaţia (*) pentru n-1 şi o scădem din (*) .

28

Cn=¿ {1, n=1¿ ¿¿¿

Cn=n−1+ 2n∑k=2

n

Ck−1

nCn=n(n−1)+2∑k=1

n

Ck−1 (∗)(n−1)Cn−1=(n−1 )(n−2)+2∑k=1

n

Ck−1

nCn−(n−1 )Cn−1=n (n−1 )−( n−1)( n−2 )+2Cn−1

Obţinem în continuare:

Scriind ultima relaţie pentru n=2,3,…,n-1,n şi adunând relaţiile obţinute avem:

…………………………………………..

Avem deci o complexitate medie de O(ln n)

{tergerea unui nod din arborele de sortareAceastă operaţie trebuie să se execute astfel arborele rămas să fie arbore de sortare.Operaţiile efectuate diferă în funcţie de tipul nodului care se şterge.~n fiecare caz se eliberează zona rezervată nodului care se şterge.

Caz1.{tergem o frunză Dacă arborele avea un singur nod atunci rădăcina acestuia devine nil iar altfel fie t pointerul spre nodul tata al nodului care se şterge.Dacă frunza care se şterge este fiu stâng atunci t^.st devine nil iar altfel t^.dr:=nil.

29

nCn=(n+1)Cn−1+(n−1)( n−n+2 )nCn=(n+1)Cn−1+2(n−1)Cnn+1

=Cn−1

n+2n−1n (n+1)

=Cn−1

n+4n+1

−2n,∀n≥2

Cnn+1

=Cn−1

n+4n+1

−2n

Cn−1

n=Cn−2

n−1+4n−2n−1

C3

4=C2

3+4

4−2

3C2

3=C1

2+4

3−2

2

Cnn+1

=12+∑

2

n4k+1

−∑2

n2k=1

2+2∑

k=3

n1k+4n+1

−22=2∑

3

n1k+4n+1

−12

Cnn+1

≃2∑k=1

n1k≃2∫

1

n1xdx=2 lnn

t

Arborele obţinut este arbore de sortare pentru că s-au păstrat relaţiile existente între nodurile rămase.

Caz 2.{tergem un nod care are un singur fiu.Fie acest nod p. Dacă p este rădăcina arborelui atunci pointerul rad devine egal cu adresa fiului existent iar altfel fie t pointerul spre nodul tată al nodului care se şterge.~n acest caz subarborele cu rădăcina p este înlocuit cu subarborele nevid al nodului p (dacă p este fiu stâng şi are doar fiul drept al lui t atunci t^.st devine p^.dr).

t p

f

Arborele obţinut este un arbore de sortare .Fie f fiul nodului care se şterge.~nainte de ştergere p şi f se găsesc în acelaşi subarbore a lui t şi după ştergere f rămâne în acelaşi subarbore , deci se păstrează relaţiile.(Pentru exemplul nostru: toate nodurile din subarborele stâng al lui f sunt mai mici decât valoarea din f, se găsesc în subarborele stâng al lui t, deci toate valorile din subarborele stâng al lui f sunt mai mici decât valoarea din t. Nodurile din subarborele drept al lui f erau şi rămân mai mici decât valoarea din f şi se găsesc la rândul lor în subarborele stâng al lui t,deci sunt mai mici decât valoarea din t)

30

Caz3.{tergem un nod care are ambii fii. ~n acest caz se înlocuieşte valoarea din nodul care se şterge cu valoarea din cel mai din stânga nod al subarborelui drept sau cu valoarea din cel mai din dreapta nod din subarborele stâng şi apoi se şterge acel nod (care se găseşte în unul din primele două cazuri).Exemplu:Se şterge rădăcina

Se alege un astfel de nod pentru ca arborele să rămână arbore de sortare.

Vom arăta acest lucru în cazul în care se înlocuieşte valoarea din nodul care se şterge cu valoarea din cel mai din dreapta nod al subarborelui stâng.(pentru situaţia a doua demonstraţia se face analog).

Valoarea din nodul care se şterge este mai mare decât toate valorile din subarborele stâng.Cea mai mare valoarea din acest subarbore se găseşte în cel mai din dreapta nod al subarborelui stâng (pentru orice arbore de sortare valorile din subarborele drept sunt mai mari decât valoarea din rădăcină şi relaţia de ordine este tranzitivă Prin înlocuirea valorii din nodul care se şterge cu cea mai mare valoare din subarborele stâng şi ştergerea acestui nod obţinem un nou subarbore stâng care în care toate elementele sunt mai mici decât valoarea din rădăcină.Elementele din subarborele drept nu se modifică şi sunt mai mari decât noua valoare din rădăcină întrucât aceasta se găsea iniţial în subarborele drept.

uses crt;type arb=^nod;nod=record

=>

=>

31

cheie:byte; car:char; st,dr:arb end; var rad:arb; r,n,c:byte; car:char; procedure inserare(c:byte;car:char;var p:arb); begin if p=nil then begin new(p); p^.cheie:=c; p^.car:=car; p^.dr:=nil;p^.st:=nil end else if c<p^.cheie then inserare(c,car,p^.st) else inserare(c,car,p^.dr) end;

procedure inordine(p:arb); begin if p<>nil then begin inordine(p^.st); writeln(p^.cheie:5,p^.car:2); inordine(p^.dr) end; end;

function cauta(c:byte;car:char;p:arb):arb; begin if (p=nil)or((p^.cheie=c)and(p^.car=car)) then cauta:=p else if p^.cheie>c then cauta:=cauta(c,car,p^.st) else cauta:=cauta(c,car,p^.dr) end;

procedure sterge(c:byte;car:char;var p:arb); var q,t:arb; begin if p=nil then write('nodul nu se gaseste in arbore') else if (p^.cheie=c)and(p^.car=car) then{se sterge nodul} begin q:=p; if p^.dr=nil then { nodul care se sterge nu are fiul drept sau nu are ambii fii} p:=p^.st else if p^.st=nil then { nodul care se sterge are numai fiul drept} p:=p^.dr else begin {nodul are ambii fii} {cauta cel mai write('cheia nodului ');readln(c); write('caracterul corespunzator :');readln(car); end; case r of 1:inserare(c,car,rad); 2:begin inordine(rad);readln end;

32

3:begin if cauta(c,car,rad)=nil then write('Nodul nu se gaseste in arbore') else write('Nodul se gaseste in arbore'); readln end; 4:sterge(c,car,rad); else r:=5 end until r=5 end.

EVALUREA EXPRESIILOR ARITMETICE

Problemă: Se introduce de la tastatură un şir de caractere ce reprezintă o expresie aritmetica.Să se verifice dacă expresia este corectă şi in caz afirmativ să se evalueze.Expresia conţine operatorii -,+(unari si binari),*,/ şi paranteze rotunde.

FORMA POLONEZA A EXPRESIILOR ARITMETICE

O aplicaţie importantă a arborilor binari o constituie forma poloneză a expresiilor aritmetice.

Definiţie.Numim expresie aritmetică o construcţie definită prin următoarele diagrame de sintaxă: +expresie aritmetică termen

- + -

termen factor

* /

constanta

Factor

33

( expresie )

constantă cifra . cifra

Oricărei expresii E i se poate asocia un arbore binar , construit după următoarele reguli: unei expresii formată dintr-un singur operand îi asociem un

arbore binar format doar din nodul rădăcină ce conţine operandul respectiv

dacă expresia E este de forma - E1 atunci arborele binar asociat este de forma:

-

E1

dacă expresia este de forma E=+E1 atunci arborele ataşat expresiei E coincide cu cel al expresiei E1

dacă expresia este de forma E=E1 op E2 ,unde op este un operator binar din lista prezentată anterior atunci arborele asociat expresiei este

op

E1 E2

dacă E=(E1), unde E1 este o expresie aritmetică atunci arborele binar asociat expresiei aritmetice E coincide cu arborele binar asociat expresiei E1.

Exemplu:arborele asociat expresiei E= –55+78*(+31-23+34/2+3)-6 este de forma

-

+ 6 - *

55 78 +

34

- *

+ 23 / 3

31 34 2

fig.1

Parcurgând în postordine arborele binar asociat expresiei aritmetice,obţinem forma poloneză postfixată a expresiei aritmetice.

Notaţia a fost introdusă de matematicianul polonez J.Lukasiewicz..Se observă că se obţine o expresie fără paranteze .Fie E o expresie aritmetică.Prin definiţie avem:

1)Dacă expresia aritmetică E este formată dintr-un operand atunci forma poloneză este egală cu E.

2)Dacă E1 este o expresie aritmetică atunci forma poloneză asociată expresiei -E1 este forma poloneză asociată expresiei E1urmată de operatorul unar -;dacă E=+E1 atunci forma poloneză asociată expresiei E1 coincide cu forma poloneză asociată expresiei E1

3) Dacă E1 şi E2 sunt expresii aritmetice şi op este un operator binar, atunci forma poloneză asociată expresiei E=E1+E2

este forma poloneză(E1)forma poloneză( E2)op4)Forma poloneză asociată expresiei (E) coincide cu forma

poloneză asociată expresiei E.

Pentru arborele binar din fig.1 obţinem prin parcurgere în postordine şirul:55 _78 31 23 – 34 2 / 3 *+ * + 6 - . Acelaşi şir se obţine prin transformări succesive ale expresiei E= –55+78*(+31-23+34/2*3)-6 aplicând regulile date de definiţia formei poloneze:Vom nota cu fp(E) forma poloneză asociată unei expresii aritmetice.Rezultă de aici

fp(–55+78*(+31-23+34/2*3)-6)=fp(–55+78*(+31-23+34/2*3))6-=

fp(–55)fp(78*(+31-23+34/2*3))+6-=fp(55)_fp(78)fp(+31-

23+34/2*3)*+6- =

35

55_78 fp(+31-23) fp(34/2*33)+*+6- =55_78fp(+31)fp(23)-

fp(34/2)fp(3)*+*+6-=

55_78 31 23 -fp(34)fp(2)/3*+*+6- =55_78 31 23 – 34 2 /

3*+*+6-.

Teoremă.Parcurgerea în postordine a unui arbore binar asociat unei expresii aritmetice E construieşte forma poloneză postfixată a expresiei E.

Demonstraţie.~ntre regulile de constucţie a arborelui binar şi definiţia formei poloneze există o corespondenţă biunivocă.

Orice expresie aritmetică are una din formele indicate în definiţia formei poloneze(E=constanta,E=E1,E=E1 op E2,E=(E1).Fiecăreia dintre aceste forme îi corespunde în mod unic un arbore binar şi o formă poloneză.Parcurgerea arborelui binar asociat expresiei E în postordine, în cele 4 cazuri , dă forma poloneză corespunzătoare expresiei E.(E1-,E1E2op,E1) .Rezultă de aici că parcurgerea arborelui binar asociat expresiei E în postordine, dă forma poloneză corespunzătoare expresiei E.

Expresia aritmetică se introduce de la tastatură sub forma unui şir de caractere.

Pentru a construi arborele binar ataşat expresiei aritmetice vom păstra în câmpul v al oricărui nod operatorul curent (atunci când ne aflăm pe un caracter diferit de operator punem simbolul ’$’).Câmpul număr este utilizat pentru păstrarea numărului curent.Pentru ca expresia să fie corectă trebuie să avem în şirul introdus numai cifre şi caracterele ’-’,’+’,’*’,’/’,’)’,’(‘,’.’. Dacă această primă condiţie nu este îndeplinită atunci expresia nu este corectă.Pentru determinarea corectă a valorii expresiei trebuie să eliminăm spaţiile din şirul introdus(se vor considera pe rând caracterele din şir şi ele trebuie să indice un operator sau un operand, deci trebuie să fie diferite de caracterul ’ ’).

Se parcurge şirul începând cu primul caracter.Arborele binar corespunzător expresiei va avea rădăcină rad.

Procedura expresie(var p:arb)construieşte recursiv arborele de rădăcină p ataşat expresiei.

Dacă primul caracter al expresiei este ’-’unar atunci câmpului v din nodul rădăcină indicat de p i se atribuie simbolul ‘_’(pentru a face diferenţă între – unar şi – binar) , fiul stâng al lui

36

p are valoarea nil şi se construieşte(conform diagramei de sintaxă) arborele corespunzător termenului care urmează după operatorul unar -. Rădăcina acestui subarbore se atribuie fiului drept al lui p.

Atunci când primul caracter al expresiei este + ,se ignoră acest caracter şi se atribuie variabilei p rădăcina arborelui ataşat expresiei care începe după operatorul+.

Dacă expresia nu începe cu un operator unar atunci trebuie să înceapă cu un termen.Pentru a construi arborele de rădăcină p executăm paşii următori:pas1)construim în p arborele asociat termenului care începe la poziţia curentă;pas2)cât timp urmează unul dintre operatorii ’+’ şi ’-’ păstrăm acest operator în q^.v,punem în fiul stâng al lui q arborele p şi în dreapta construim arborele ataşat termenului următor.După acest pas rădăcina noului arbore se atribuie lui p.

Exemplu:arborele corespunzător expresiei 45+56-3 se construieşte astfel:

Primul caracter al expresiei nu este operator unar,expresia este corectă,deci va începe cu o cifră.Vom nota cu i poziţia curentă în şir.Iniţial i=1.

pas1.Construim în p arborele dat de primul termen.Vom obţine:

45 p

pas2.i=3.operatorul de pe poziţia a doua este +, deci vom avea un nou arbore în care rădăcina q este ‘+’,în stânga se găseşte arborele de rădăcină p,în dreapta se construieşte arborele asociat următorului termen .După acest pas avem p=q.Obţinem arborele:

+ p

45 56

şi i=6 ceea ce indică operatorul -.Repetăm secvenţa de mai sus(q^.st:=p; q^.v=’-’ şi în dreapta construim arborele ataşat termenului următor.Obţinem

-

37

p + 3

45 56

Celelalte proceduri construiesc (pe baza definiţiilor şi a diagramelor de sintaxă) în mod asemănător arborii asociaţi şi dacă se întâleşte eroare atunci şirul introdus nu este o expresie corectă.

Pentru a calcula valoarea expresiei după ce am construit arborele se consideră valoarea din rădăcină.Dacă ea reprezintă un număr atunci acel număr este valoarea expresiei iar altfel se determină valorile corespunzătoare fiilor şi se realizează cu acestea operaţia indicată de operatorul din rădăcină.

uses crt; type inter=0..3; arb=^nod; nod=record v:char;nr:real; st,dr:arb end;

const m=['0'..'9','+','-','*','/','(',')','.']; numar=['0'..'9','.']; var exp:string; rad:arb;c:char;i:byte; x:pointer;

procedure postordine(p:arb); begin if p<>nil then begin postordine(p^.st);postordine(p^.dr); if p^.v='$' then write(p^.nr:5:2,' ') else write(p^.v) end end; procedure eroare; begin write('Expresie eronata');readln; halt(0) end;

procedure citire; var j:byte; begin clrscr;write('Expresia:');readln(exp); {se elimina spatiile din sir} j:=0; while j<length(exp) do

38

begin inc(j); if not(exp[j] in m)then eroare; if exp[j]=' ' then begin delete(exp,j,1);dec(j) end end; exp:='('+exp+')';writeln(exp); end;

procedure expresie(var p:arb);forward; procedure termen(var p:arb);forward; procedure factor(var p:arb); {se costruieste nodul teminal p sau subarborele cu radacina p asociat unei expresii cuprinsa intre paranteze} var er:integer; y:string; begin if c='(' then begin inc(i);c:=exp[i]; expresie(p) {c are aici valoarea ')'} end else begin new(p); p^.v:='$'; dec(i); val(y,p^.nr,er);if er<>0 then eroare end; inc(i);c:=exp[i] end;

procedure termen; var q:arb; begin factor(p); while c in ['*','/'] do begin new(q);q^.v:=c;q^.st:=p; {se mai citeste un caracter pentru ca operandul 2 incepe dupa c care indica un operator} inc(i);c:=exp[i]; {creeaza si leaga in dreapta nodului q subarborele asociat operandului 2 al oeratorului c} factor(q^.dr); p:=q end end; procedure expresie; var q:arb; begin if c in ['+','-'] then {- sau + unar} if c='-' then begin new(p); p^.v:='_';p^.st:=nil; inc(i);c:=exp[i]; termen(p^.dr) end else begin inc(i);c:=exp[i]; termen(p) end else termen(p);while c in ['+','-'] do begin new(q); q^.v:=c;q^.st:=p;

39

inc(i);c:=exp[i]; termen(q^.dr); p:=q end end;

function evaluare(p:arb):real;var a,b:real;beginif p<>nil then begin a:=evaluare(p^.st); b:=evaluare(p^.dr); case p^.v of '+':evaluare:=a+b; '-':evaluare:=a-b; '*':evaluare:=a*b; '/':evaluare:=a/b; '$':evaluare:=p^.nr; '_':evaluare:=-b end end else evaluare:=0

end;

begincitire;readlnend.

Cuprins

Capitolul I.FORMULAREA TEMEI....................................................................3

1.1.ASPECTE GENERALE LEGATE DE TEMA LUCRĂRII .

DOMENIUL ĨN CARE SE ĨNCADREAZĂ LUCRAREA.....................................3

1.2.EXPLICAREA PROBLEMEI PROPUSE SPRE REZOLVARE....................3

1.3.EXPLICAŢII FINALE LEGATE DE TEMA PROPUSĂ

40

UTILITATEA TEMEI, ASPECTE REZOLVATE DE ACEASTA, POSIBILITĂŢI DE

DEZVOLTARE A TEMEI....................................................................................4

ARBORI......................................................................................................5

OPERATII ELEMENTARE..........................................................................6 ARBORI PARTIALI....................................................................................8ARBORI BINARI.......................................................................................11 ALGORITMI ELEMENTARI.....................................................................14ARBORI DE SORTARE............................................................................20EVALUREA EXPRESIILOR ARITMETICE...............................................28FORMA POLONEZA A EXPRESIILOR ARITMETICE.............................29BIBLIOGRAFIE.........................................................................................37

Bibliografie

1.Tudor Sorin-Tehnici de programare

2.Cristian Udrea-Pascal Teorie si Aplicatii

41

42