3-StructDate - C - Arbori

7/24/2019 3-StructDate - C - Arbori

http://slidepdf.com/reader/full/3-structdate-c-arbori 1/32

Structuri de DateElementare



Structuri arborescente



Arbori - def. recursiva

O structură de arbore (k -arbore), T, de un anume tip de bază

este(a) fe o structură vidă (adică T = ∅ );(b) fe este nevidă, deci conţine un nod de tipul de bază, pecare-l vom numi rădăcină şi l vom nota root(T), plus un numărfnit de structuri dis!uncte de arbori de acelaşi tip, T 1, T 2, ", T k ,

numiţi subarborii lui T (sau fii lui root(T))#$eprezentarea ca %ra& a unui k -arbore'

root(T)

T 1 T 2 T k

Fig.3.1.1. Un k -arbore T , cu nodul rădăcină root(T) şi fii săi,

T 1 , T 2 ,…,T k .



Arbori - liberi

Deniţie. Se numeşte graf G = (X, V) o perece &ormată din

două mulţimi, mulţimea X a nodurilor sau vr&urilor %ra&ului, şimulţimea V a muciilor %ra&ului, unde o mucie v ∈ V este operece ordonată de noduri v=(x,y), x,y ∈ X #n %ra& neorientat este un %ra& n care perecea (x,y) seidentifcă cu perecea (y,x).

n %ra& &ără cicluri este un %ra& n care, pornind de la un vr&dat nu putem a!un%e din nou la el &olosind mucii#

Deniţie. Se numeşte arbore un %ra& H = (X, V) care esteneorientat, cone*, &ără cicluri, cu un nod precizat numit

rădăcină# +entru orice vr& x ∈

X , e*istă un număr fnit devr&uri x 1,...,x n ∈ X asociate lui x , numite descendenţi direcţi

(sau fii) lui x #

Arbori liberi - mai multe caracterizari



Arbori - terminologie

- arborii ordonaţi , arbori n care e*istă o relaţie de

ordine ntre descendenţii unui nod

- arborii neordonaţi , arbori n care nu e*istă o relaţie

de ordine ntre descendenţii unui nod



Arbori - terminologie

gradul arborelui ntre%ul k care reprezintă numărul ma*im de fiai unui nod#

.iecărui nod al arborelui i vom asocia un nivel n &elul următor'(a)rădăcina se a/ă la nivelul 0,(b)dacă un nod se a/ă la nivelul i atunci fii săi sunt la nivelul i+1.

1umim înălţime (sau adâncime) a unui arbore nivelul ma*im alnodurilor sale#

Se numeşte terminal sau frunză un nod &ără descendenţi#

Se numeşte nod interior orice nod care nu e terminal#

n 2-arbore ordonat se numeşte arbore binar # (fu stn%,respectiv fu drept#)



Arbori - aplicatii

•2autare•3mplementari de cozi cu prioritati•Sortare

•Reprezentari• Proceduri de decizie – de estimat costuri

• ‘Epresii! – de ‘evaluat!

• "odicare

•Reprezentari de mutimi• #nion-$ind problem %pb. reuniunii si apartenentei&



Arbori - aplicatii

•2autare 4 cautare, inserare, ster%ere•3mplementari de cozi cu prioritati 4 ins si del•Sortare

•Reprezentari• Proceduri de decizie – de estimat costuri

• ‘Epresii! – de ‘evaluat! -parcurgeri

• "odicare – %de construit arb cu propr ‘bune!&

•Reprezentari de mutimi• #nion-$ind problem %pb. reuniunii si apartenentei&

– e de combinare %merge&



Arbori %oarecari& - traversariSe presupune data o reprezentare in care fecare nod are trei cmpuri' in!o' pentru in&ormaţia din noduri

nr"i' valoarea #$, ntrea%ă, reprezintă numărul de fi ai nodului "i' vector de dimensiune #$ , cu componente pointeri, ast&el nct, "i%&' este pointer către ful & al nodului, iar &= 1,2,,#$.

5l%oritmul de traversare este următorul'

6# Se porneşte de la rădăcină#7# 8a fecare nod curent' (a) se procesează in!o

(b) se introduc ntr-o structură a!utătoare fii nodului curent n vedereaprocesării ulterioare#9# Se e*tra%e din structura a!utătoare un alt nod şi se reia de la punctul 7#

2a structur' a(ut'toare putem &olosi una dintre structurile liniare pecare le cunoaştem, stiva sau coada#Dacă &olosim o coadă obţinem traverarea *n ime (-readt "rt) aarborelui#

Dacă &olosim o stivă obţinem traverarea *n ad/n0ime (dept "rt) aarborelui#



Arbori %oarecari& - reprezentare

struct nod: int in&o;

int 1.; numarul de fi ai nodului

nod < fi=1.>; tabloul adreselor descendentilor?;nod < coada=600>; pentru parcur%erea pe niveleint prim, ultim, &rate=600>, !0;

pentru %estionarea cozii



Arbori %oarecari& - creare

nod < 2reare()

: int i, @0;

nod <p (nod<) malloc(sizeo&(nod)); se declara in&ormatia si numarul de descendenti

scan&(ABdBdC,p in&o, p 1.);i& (p 1. 0):

&rate=!> p in&o; !FF;

?&or (i 0; iGp 1.; iFF)

p fi=i> 2reare();return p;

?



Arbori %oarecari& - traversare

1

2 3 4 5

6 7 8

DF (Adancime):1, 2, 3, 6, 7, 8, 4, 5

void D. (nod <p):

int i;i& (p H 188)

:print&(ABd C, p in&o);&or (i0; iGp 1.; iFF)

D. (p fi=i>);?

?

)n adancime



Arbori %oarecari& - traversare

BF (Latime):1, 2, 3, 4, 5, 6, 7, 8

void I. (nod <rad): nod <p; int i, @ -6;

prim ultim 0;

5dau%a(rad); in coada se adau%a radacinado:

p E*tra%eJnod(); e*tra% un nod din coadai& (pH188): print&(ABd A, p in&o);

&or (i0; iGp 1.; iFF)5dau%a(p fi=i>); adau% in coada fi nodului

??Kile(p);

?

)n latime %pe nivele&



Arbori binari

n arbore binar (7-arbore ordonat) L este'

(6) fe un arbore vid (T=∅ ).

(7) fe e nevid, şi atunci conţine un nod numit rădăcină,

mpreună cu doi subarbori binari dis!uncţi numiţi subarborele

stn%, respectiv subarborele drept#

struct nod: int in&o;

nod <le&t, <ri%t;?;

nod < root;



Arbori binari

Fig.3.2.1. Arborele binar ce reprezintăexpresia aritmetică a!b " c##$d-e$f##.

$

e f

$

! -

"a

b

d

c

Eemplu - reprezentari epresii aritmetice



• n +reordine ($SD) (Rădăcină tn%a reapta)

• n 3nordine (S$D) (tăn%a Rădăcină reapta)

• n +ostordine (SD$)(tăn%a reapta Rădăcină)

Arbori binari - traversari inadancime



• n +reordine ($SD) (Rădăcină tn%a reapta)


void RSD (node *r)

{ if(r != NULL)

{

printf("%d ",r-->info);

RSD( r → eft); RSD( r → rit);

#

#



5rbore de e*presie -- preordine -- notatia pref*


$

e f

$

! -

"a

b

d

c

* + a , b c – d * e f

b i bi i i i



• n 3nordine (S$D) (tăn%a Rădăcină reapta)


void SRD (node *r)

{ if(r != NULL)

{

SRD( r → eft);

printf("%d ",r-->info);

SRD( r → rit); #

#



5rbore de e*presie -- inordine -- notatia inf*


$

e f

$

! -

"a

b

d

c

a + b , c * d - e * f %a + %b , c & &* %d - %e * f &&

A b i bi i i i



n +ostordine (SD$) (tăn%a reapta Rădăcină)


void SDR (node *r)

{

if(r != NULL)

{

SDR( r → eft);

SDR( r → rit);

printf("%d ",r-->info); #

#



5rbore de e*presie -- postordine -- notatia postf*


$

e f

$

! -

"a

b

d

c

a b c , + d e f * - *



E*ercitii -- stive

•De evaluat e*presii cu operatori

binari'

•3n notatie pref*•3n notatie inf*•3n notatie postf*

•tilizand stivastive (M)

•Estimat costuri (timp F spatiu)•5vanta! al unei scrieri &ata decelelalteMMM



•Evaluarea unei e*presii in notatie postf*

$tr&t node

{

&'r tip; tip infor'tiei dintr-n nod (&'r'&ter n'r)

&'r op; , -, *, int n+er; oper'nii

node *eft, *rit;

#;$tr&t $t'&

{

node *d't'./012;

int vf;

#;

a) folosind o stiva

) folosind !n a"o"e de e#$"esii



•Evaluarea unei e*presii in notatie postf* (cont#)

%m$lementa"ea o$e"atiilo" $e stiva (com!ne)

int i$ept3($t'& *$) te$t pentr $tiv' vid'

{

if ($ → vf == -4) retrn 4;

e$e retrn 5;

#

void ept3$t'&($t'&* $) $tiv' vid'

{

$ → vf = -4;#





in$er're' ni nod in $tiv'

void p$($t'&* $, node *ite)

{

if($ → vf == (/01-4)) {

printf("6n 7verfo8");

#

e$e

{ $ → vf;

$ → d't'.$ → vf2=ite;

#

#





eiin're' ni nod din $tiv'

node* pop ($t'&* $)

{

node *ret = NULL; if(!i$ept3($))

{

ret= $ → d't'.$ → vf2;

--$ → vf;

# retrn ret;

#



•Evaluarea unei e*presii in notatie postf* (cu stiva)

int ev''te(&'r *po$tfi9)

{ po$tfi9 - $ir de &'r'&tere introd$

&'r *p = :po$tfi9.52; $e &on$ider' 'dre$' prii &'r'&ter 8ie(*p)

{ $e &'t' pri &'r'&ter nen

if(i$diit(*p)) d'&' '&e$t' e$te n'r $e introd&e in $tiv'

{ n'r intre = &od 0S<< &'r'&ter - (&od &'r'&teri ?5?)

e$e

{ d'&' '&e$t' e$te oper'nd

op4 = pop(:1); $e e9tr' din $tiv' tiee v'ori in$er'te

op@ = pop(:1);

$e 'pi&' oper'nd

p$(:1,ne8node); $e reintrod&e in $tiv' ret't oper'tiei

# p; $e tre&e ' r'tor &'r'&ter

#

re$t = pop(:1);

retrn re$t;

#



•Evaluarea unei e*presii in notatie postf* (cu stiva)

&#em$l! / 0/ 1 , + 2 3 4 * - -

'tiva, d!$a fieca"e $as

45 45

@5

45

@5

A

45

4 4

B

4

B

4

B

C

4

B

@

4

-@A

B



•Evaluarea unei e*presii in notatie postf* (cu arbore)

void po$tfi9@e9ptree(&'r* po$tfi9, node **root)

{

po$tfi9 - $ir de &'r'&tere introd$, i'r root e$te r'd'&in' 'r+orei &'r *p = :po$tfi9.52; $e &on$ider' 'dre$' prii &'r'&ter

8ie(*p)

{ $e &'t' pri &'r'&ter nen

if(i$diit(*p)) d'&' '&e$t' e$te n'r

$e in$ere'' in $tiv' n nod no & infor'tie neri&'

e$e

{ op4 = pop(:1); $e e9tr' din $tiv' tiee v'ori in$er'te

op@ = pop(:1);

* $e in$ere'' in $tiv' n nod no & infor'tie &'r'&ter

&e 're &' $+'r+ori $t'n $i drept v'orie 'nterior e9tr'$e *

p$(:1,ne8node); $e 'd'' no nod in $tiv' #

p; $e tre&e ' r'tor &'r'&ter

#

*root = pop(:1);

#




int ev''tetree(node *9)

{

if( 9 → tip == ?7? ) verifi&'re' tipi (oper'tor oper'nd) { * d'&' e$te oper'tor, 'tn&i $e 'pee'' re&r$iv

ev''re' pe $+'r+oree $t'n, re$pe&tiv pe $+'r+oree drept *

int op4 = ev''tetree( 9 → eft );

int op@ = ev''tetree( 9 → rit );

$8it& ( 9 → op ) {

&'$e ??E retrn op4 op@;

&'$e ?-?E retrn op4 - op@;

&'$e ?*?E retrn op4 * op@;

&'$e ??E retrn op4 op@; def'tE retrn 5;

#

#

e$e

retrn (9 → n+er);

#

E*ercitii Structuri lineare str



E*ercitii -- Structuri lineare 4 strarborescente (binari)

•2ind•Daca•2um

putem codifcareprezentaun arb binar printr-o str liniara 5

Date post:	20-Feb-2018
Category:	Documents
Upload:	alin-marian-mindrut
View:	214 times
Download:	0 times

3-StructDate - C - Arbori

Documents