09 - arbori binari.ppt

7/18/2019 09 - Arbori binari.ppt

http://slidepdf.com/reader/full/09-arbori-binarippt 1/31

Arbori binari. Aplicaţii



Arbori binari

• Definiţie. Un arbore binar este un arbore orientat cuproprietatea că pentru orice vîrf v, od(v)≤2. Dacă od(v)=2,cei doi descendenţi sînt desemnaţi ca descendent stîn (fiustîna) respectiv descendent drept (fiu dreapta). !entru

vîrfurile cu od(v)=", unicul descendent este specificat fie cafiu stîna, fie ca fiu dreapta

• Definiţie. #e nume$te arbore strict binar un arbore binar cupoprietatea că pentru orice vîrf v, od(v)%".

• Definiţie. #e nume$te nod terminal (sau frunză) orice vîrf v al arborelui cu od(v )=&. 'n ca contrar nodul v esteneterminal .



Arbori binari. #ubarbori



Arbori binari. epreentare.

• epreentarea *iu+*rate (, , *iu, *rate, -nf)

• u structuri dinamice

/ #tructură nod0 informaţie, adresă fiu stîn 1 drept

typedef struct nod { int info;

struct nod* st,*dr;

} TNOD;

• !entru a cunoa$te arborele0 rădăcina

TNOD* r;



Arbori binari. !arcurere

• 'n lăţime / !e niveluri !e niveluri

• 'n adîncime

/ A+!reordine

!reordine / A+!ostordine !ostordine / -nordine

void preordine(TNOD* r)

{ if(r!=NULL) { //preucrre r"#info preordine(r"#st); preordine(r"#dr); }

}

void postordine(TNOD* r)

{ if(r!=NULL) { postordine(r"#st); postordine(r"#dr); //preucrre r"#info }

}

void inordine(TNOD* r)

{ if(r!=NULL) { inordine(r"#st);

//preucrre r"#info inordine(r"#dr);

}}



Arbori binari. !arcurere

void niveuri(TNOD* r){ TNOD$* c; TNOD* p; int er; if(r != NULL) { c = NULL; c = pus%(c,r);

&%ie(c != NULL) { c=pop(c,'p,'er);

// preucrre p"#info

if(p"#st!=NULL) c = pus%(c,p"#st); if(p"#dr!=NULL) c = pus%(c,p"#dr); }

}}

typedef struct nodc{ TNOD* info;

struct nodc* net; } TNOD$;



Arbori binari. alculul înălţimii

int intie(TNOD* r){ int i,,+; if(r == NULL) i = ; ese

{ = intie(r"#st); + = intie(r"#dr); i = - . (#+ 0 +);

} return(i);

}



Arbori de sortare (căutare)

• Definiţie. Un arbore de sortare este un arbore binar cuurmătoarele proprietăţi

/ fiecărui nod i al arborelui îi este ata$ată o informaţie -*( i )dintr+o mulţime ordonată de valori

/ pentru fiecare nod i , -*(i ) este mai mare decît -*( j ),pentru toate nodurile j din subarborele stîn al arborelui curădăcină i

/ pentru fiecare nod i , -*(i ) este mai mică decît -*( j ),

pentru toate nodurile j din subarborele drept al arborelui curădăcină i

/ pentru orice vîrfuri i $i j daca i ≠ j atunci -*(i ) ≠ -*( j ).



Arbori de sortare (căutare)

10

2

8

1 3

5

4

7 9

6

11

1512

14 16

13

• 3peraţii / !arcureri (pe niveluri, preordine, inordine, postordine) / Adăuare informaţie / 4terere informaţie

• !reordine 0 "&, 5, 6, 2, ", 7, 8, 9, :, ;, "7, "2, "", "8, "6, "5• -nordine 0 ", 2, 7, 6, 8, 5, :, 9, ;, "&, "", "2, "7, "6, "8, "5• !ostordine0 ", 7, 2, 8, 6, :, ;, 9, 5, "", "2, "6, "5, "8, "7, "&

• !e niveluri0 "&, 5, "7, 6, 9, "2, "8, 2, 8, :, ;, "", "6, "5, ", 7



TNOD* inserre(TNOD* r, int , int* er){ *er=;

if(r==NULL)

{ r=(TNOD*)oc(si1eof(TNOD));

r"#info=;

r"#dr=NULL;

r"#st=NULL;

}

ese if(r"#info==) *er=-;

ese if(r"#info#) r"#st=inserre(r"#st, , er);

ese r"#dr=inserre(r"#dr,,er);

return r;}

Arbori de sortare. Adăuare informaţie

10

2

8

1 3

5

4

7 9

6

11

1512

14 16

13

12,5



Arbori de sortare. 4terere informaţie

10

2

8

1 3

5

4

7 9

6

11

1512

14 16

13

7,2

7,37,1

10

2

8

3

4

9

5

1115

12

14 167,2

7,37,1



Arbori de sortare. 4terere informaţie

TNOD* ster2e(TNOD* r, int , int*er){ TNOD* p, *3; *er=; if(r == NULL) *er=-; ese if(r"#info # ) r"#st = ster2e(r"#st,,er); ese if(r"#info 4 ) r"#dr = ster2e(r"#dr,,er);

ese if(r"#st == NULL) { p = r; r = r"#dr; free(p); }

ese if(r"#st"#dr==NULL) { r"#info = r"#st"#info; p = r"#st; r"#st = r"#st"#st; free(p); } ese { p = r"#st; &%ie(p"#dr != NULL) { 3 = p;

p = p"#dr; } r"#info = p"#info; 3"#dr = p"#st; free(p); }

return r;}



Arbori de structură

• Arbore de structură0 arbore strict binar folosit pentru arepreenta e<presiile aritmetice care conţin numai operatoribinari. *iecare nod conţine ca informaţie utilă0

/ un operand , dacă este nod frună

/ un operator , dacă nu e nod frună

• Arborele se construie$te acordînd priorităţi operanilor $ioperatorilor.

• !arcurerea arborelui în preordine = forma poloneză

directă a e<presiei

• !arcurere arborelui în inordine = refacerea e<presiei (cusau fără parantee).



><emplu0 a?(b@c) /(d@e)1(f@)

-

+

b c

a

*

ed

++

f g

/

onstruire arbore0

". alculare priorităţi pentru operani $i operatori

2. onstruire propriu+isă a arborelui




". alculare priorităţi pentru operani $i operatori

• operatorii aditivi primesc prioritatea 1

• operatorii multiplicativi primesc prioritatea 10

• prioritatea fiecărui operator se măre$te cu 10 pentrufiecare perece de parantee care îl include

• fiecare operand prime$te prioritatea ma<imă (maxint )

!riorităţile sînt înscrise într+un vector.

• pBiC= prioritatea elementului i din e<presie (operator sauoperand, în ordinea apariţiei

Elemente expr !" a, *, b, +, c, -, d, +, e, /, f, +, g#

$r%&r%t'(% !"max%nt,10,max%nt,11,max%nt,1,max%nt,11,max%nt,10,max%nt,11,max%nt#


><emplu0 a?(b@c) /(d@e)1(f@)





)&ntr%re arb&re alg&r%tm recr%

1 dac' expre%a crent' ete %d', barb&rele crent ete %d "n%l#

2 altfel e cat' elementl c pr%&r%tate m%n%m' d%n expre%a crent'

3 e creea.' n n&d r'd'c%n' pentr barb&rele crent

4 f%l tng ete barb&rele &b(%nt pr%n repre.entarea bexpre%e% d%n tnga

elementl% crent

5 f%l drept ete barb&rele &b(%nt pr%n repre.entarea bexpre%e% d%n dreapta

elementl% crent


><emplu0 a?(b@c) /(d@e)1(f@)






><emplu0 a?(b@c) /(d@e)1(f@)

+

?

+

-1

a * b + c

"max%nt, 10, max%nt, 11, max%nt#

a * b + c

"max%nt, 10, max%nt, 11, max%nt#

a

"max%nt#

a

"max%nt#

a?(b@c) (d@e)1(f@)

a b@c

(d@e)1(f@)






><emplu0 a?(b@c) /(d@e)1(f@)

aa

??

++

b@c

(d@e)1(f@)

" #

" #

" #

" #

b + c"max%nt, 11, max%nt# b + c"max%nt, 11, max%nt#

aa @@

??

++

(d@e)1(f@)

b c






><emplu0 a?(b@c) /(d@e)1(f@)

aa @@

bb cc

??

++

(d@e)1(f@)

d + e / f + g

"max%nt,11,max%nt,10,max%nt,11,max%nt#

d + e / f + g

"max%nt,11,max%nt,10,max%nt,11,max%nt#

aa @@

bb cc

?? 11

++

f@d@e



!arcurerea arborelui în preordine = forma poloneză directă ae<presiei0

- * a + b c / + d e + f g

!arcurere arborelui în inordine = refacerea e<presiei (cu saufără parantee / #D sau (#)(D) )0

a ? b @ c / d @ e 1 f @

((a)?((b)@(c)))+(((d)@(e))1((f)@()))




Evaluare expresie0 prin parcurere în postordine.

!relucrarea fiecărui nod r constă în

• dacă e nod frună nu se scimbă nimic

• altfel se înlocuie$te informaţia r->inf cu reultatul e<presieiss r->inf sd

unde ss $i sd sînt informaţiile din fiul stîn respectiv drept alnodului curent





77 @@

66 55

@@

"&"& 88

@@

22 ""

?? 11

++2828

a = 7, b = 6, c = 5, d = "&, e = 8, f = 2, = "

"&"&

7&7&

"8"8 77

88



Arbori de structură + implementare

5incude 4stdio6%# 5incude 4oc6%# 5incude 4strin26%# 5incude 4t%6%# 5define 789:NT -

/* repre1entre unei epresii prin rore de structur sievure ei

restrictii0" nui opertori ritetici . " * /

" identifictorii opern1ior forti din nui o iter " fr sptii

*/

typedef struct nod{ c%r inf; fot v; struct nod *s,*d; } TNOD;




c%r* prioritti(c%r *s, int p<, int* n){ int i,,crt,; c%r* r;//i " crcteru curent

// " proritte curent //crt " eeentu curent

//r " epresi fr prnte1e //ccu prioritti = stren(s); for(i==crt=; i4; i..) s&itc%(s<i) { cse >)>0 "=-;re+;

cse >(>0 .=-;re+; cse >.>0 ; cse >">0 p<crt=.-;crt..;re+; cse >*>0 ; cse >/>0 p<crt=.-;crt..;re+; defut 0 p<crt..=789:NT;

}




//eiinre prnte1e

r=(c%r*)oc(stren(s)); strcpy(r,s); i=; &%ie(i4) if( (r<i==>)>) ?? (r<i==>(>) )

{ for(=i.-; 4; ..) r<"-=r<;

r<=>@>; "";

}

ese i..; *n=crt; return r;}



Arbori de structură + implementareTNOD* construireArore(int p, int u, c%r *r, int pr<)

{ TNOD *; int in, po1; in = pr<p; po1 = p; for(int i=p.-; i4=u; i..) if(in #= pr<i)

{ in=pr<i; po1=i;}

=(TNOD*)oc(si1eof(TNOD)); "#inf = r<po1; if(p == u)

"#s = "#d = NULL; ese { "#s = construireArore(p,po1"-,r,pr); "#d = construireArore(po1.-,u,r,pr); } return ;

}




void forApoone1(TNOD* rd, c%r* ep){ int ; if(rd) { = stren(ep); ep< = rd"#inf; ep<.- = >@>;

forApoone1(rd"#s, ep); forApoone1(rd"#d, ep); }}




fot evure(TNOD* rd){ if(rd) if(rd"#s)

s&itc% (rd"#inf) { cse >.>0 rd"#v = evure(rd"#s) . evure(rd"#d); re+;

cse >">0 rd"#v = evure(rd"#s) " evure(rd"#d); re+; cse >*>0 rd"#v = evure(rd"#s) * evure(rd"#d); re+; cse >/>0 rd"#v = evure(rd"#s) / evure(rd"#d);

}

return rd"#v;}




void citireAvoriAopern1i(TNOD* rd){ if(rd) if(rd"#s == NULL) { printf(BCc=B, rd"#inf); scnf(BCfB,'(rd"#v)); }

ese { citireAvoriAopern1i(rd"#s); citireAvoriAopern1i(rd"#d); }}




void in(){ c%r epresie<-, *efp, *fpd; int p<-,n; TNOD* rdcinAroreAstructur; printf(B@npresi de ni1t (corect, confor restrictiior)0@nB); 2ets(epresie); rdcinAroreAstructur=NULL;

//ccu prioritti efp=prioritti(epresie,p,'n); //construire rore rdcinAroreAstructur=construireArore(,n"-,efp,p); //deterinre forei poone1e epresiei fpd=(c%r*)oc(stren(efp)); fpd<=>@>; forApoone1(rdcinAroreAstructur,fpd); printf(B@nEor poone1 direct0 CsB,fpd); //evure epresie printf(B@nForie opern1ior0@nB); citireAvoriAopern1i(rdcinAroreAstructur); evure(rdcinAroreAstructur); printf(B@nFore epresiei este0 CG6Hf@nB,rdcinAroreAstructur"

#v);

}




• Atenţie0 / Dacă mai multe elemente au aceea$i prioritate

minimă, se alee ultimul pentru a fi rădăcină / ><emplu0

–"*c.d

/ a="&&, b=2, c=8, d="&

• !robleme de reolvat / >liminarea spaţiilor / Utiliarea altor operatori / Utiliarea de identificatori mai luni

09 - arbori binari.ppt

Documents