8/6/2019 parcurgereaarborilorbinari

http://slidepdf.com/reader/full/parcurgereaarborilorbinari 1/16

Parcurgerea arborilorParcurgerea arborilor

binaribinari

8/6/2019 parcurgereaarborilorbinari

http://slidepdf.com/reader/full/parcurgereaarborilorbinari 2/16

ObiectiveObiective

1.1. SemnificaSemnificaia noiunii de parcurgere a unuiia noiunii de parcurgere a unuiarbore binar;arbore binar;

2.2. Tipuri de parcurgeriTipuri de parcurgeri..

8/6/2019 parcurgereaarborilorbinari

http://slidepdf.com/reader/full/parcurgereaarborilorbinari 3/16

1.1. SemnificaSemnificaia noiunii de parcurgere aia noiunii de parcurgere aunui arbore binar;unui arbore binar;

PrinPrin parcurgereaparcurgerea unuiunui arborearbore sese înelege înelege examinareaexaminarea în înmodmod sistematicsistematic aa nodurilornodurilor salesale astfelastfel încât  încât fiecarefiecare nodnodss fiefie atinsatins oo singursingur datdat..

SinonimSinonim::  vizitareavizitarea vârfurilorvârfurilor unuiunui arborearbore..

ScopulScopul parcurgeriiparcurgerii:: PrelucrareaPrelucrarea informaiilorinformaiilor asociateasociate vârfurilorvârfurilor;;

TransformareaTransformarea arboreluiarborelui dintrdintr--oo reprezentarereprezentare planplan într într--oo structurstructur liniarliniar..

8/6/2019 parcurgereaarborilorbinari

http://slidepdf.com/reader/full/parcurgereaarborilorbinari 4/16

2.2. Tipuri de parcurgeriTipuri de parcurgeri

Exist Exist maimai multemulte modalitimodaliti dede parcurgereparcurgerecarecare diferdifer prinprin ordineaordinea dede vizitarevizitare aanodurilornodurilor::

ParcurgereaParcurgerea în în preordinepreordine (RSD)(RSD);; ParcurgereaParcurgerea în în inordineinordine (SRD)(SRD);; ParcurgereaParcurgerea în în postordinepostordine (SDR)(SDR)..

ObsObs.. PutemPutem consideraconsidera cc fiecarefiecare nodnod alalarboreluiarborelui binarbinar subordoneazsubordoneaz unun subarboresubarborestângstâng ii unun subarboresubarbore drept drept..

8/6/2019 parcurgereaarborilorbinari

http://slidepdf.com/reader/full/parcurgereaarborilorbinari 5/16

8/6/2019 parcurgereaarborilorbinari

http://slidepdf.com/reader/full/parcurgereaarborilorbinari 6/16

Fie arborele binar din figura urmtoare.Fie arborele binar din figura urmtoare.S realizm împreun parcurgerea în preordine a acestuia.S realizm împreun parcurgerea în preordine a acestuia.

1

76

3

4

2

Soluia este:

5

1, 2, 3, 4, 6, 5, 7.

8/6/2019 parcurgereaarborilorbinari

http://slidepdf.com/reader/full/parcurgereaarborilorbinari 7/16

Parcurgerea în inordine (SRD)Parcurgerea în inordine (SRD)

PlecândPlecând dede lala unun arborearbore binarbinar dat dat seserealizeazrealizeaz în în ordineordine urmtoareleurmtoarele operaiioperaii::

1.1. SeSe viziteazviziteaz subarborelesubarborele stângstâng;;2.2. SeSe viziteazviziteaz rdcinardcina ;;3.3. SeSe viziteazviziteaz subarborelesubarborele drept drept..

CaCa urmareurmare aa parcurgeriiparcurgerii arboreluiarborelui sese obineobineoo soluiesoluie subsub formaforma unuiunui tabloutablouunidimensionalunidimensional (vector)(vector)..

8/6/2019 parcurgereaarborilorbinari

http://slidepdf.com/reader/full/parcurgereaarborilorbinari 8/16

Plecând de la acelai arbore binar s realizm acum parcurgerea înPlecând de la acelai arbore binar s realizm acum parcurgerea îninordine a acestuia.inordine a acestuia.

1

76

3

4

2

5

Soluia este: 2, 1, 6, 4, 3, 7, 5.

8/6/2019 parcurgereaarborilorbinari

http://slidepdf.com/reader/full/parcurgereaarborilorbinari 9/16

Parcurgerea în postordine (SDR)Parcurgerea în postordine (SDR)

PlecândPlecând dede lala unun arborearbore binarbinar dat dat seserealizeazrealizeaz în în ordineordine urmtoareleurmtoarele operaiioperaii::

1.1. SeSe viziteazviziteaz subarborelesubarborele stângstâng;;2.2. SeSe viziteazviziteaz subarborelesubarborele drept drept ;;3.3. SeSe viziteazviziteaz rdcinardcina..

CaCa urmareurmare aa parcurgeriiparcurgerii arboreluiarborelui sese obineobineoo soluiesoluie subsub formaforma unuiunui tabloutablouunidimensionalunidimensional (vector)(vector)..

8/6/2019 parcurgereaarborilorbinari

http://slidepdf.com/reader/full/parcurgereaarborilorbinari 10/16

 A cum s realizm parcurgerea în postordine a arborelui A cum s realizm parcurgerea în postordine a arborelui::

1

76

3

4

2

5

Soluia este: 2, 6, 4, 7, 5, 3, 1.

8/6/2019 parcurgereaarborilorbinari

http://slidepdf.com/reader/full/parcurgereaarborilorbinari 11/16

 Aplicaii

1. Despre un arbore binar cu 7 noduri se tiu vectorul tatT=(6,5,5,2,0,2,6) i vectorul tip de fiu TF=(-1,-1,1,-1,0,1,1).

a) Care este rdcina arborelui?

b) Care sunt nodurile cu exact doi descendeni în arbore?c) Câte noduri are subarborele stâng al nodului 2?

d) Câte nivele are arborele?

e) Parcurgei arborele în cele trei moduri posibile.

8/6/2019 parcurgereaarborilorbinari

http://slidepdf.com/reader/full/parcurgereaarborilorbinari 12/16

f) Care dintre arborii desenai mai jos este subarbore drept al rdcinii?

a)a) b)b)

c)c) d)d)

1

3

5

2

4

3

5

6

4

7

3

45

6 7

5

13

4 2

8/6/2019 parcurgereaarborilorbinari

http://slidepdf.com/reader/full/parcurgereaarborilorbinari 13/16

2. Construii arborele binar corespunztor tablouluiurmtor ce conine irurile T (tat) i TF (tip de fiu),

apoi parcurgei arborele creat în cele trei moduriposibile.

TT 22 00 11 22 11 55 44 44 55 88

TFTF --11 00 11 11 --11 --11 11 --11 11 11

8/6/2019 parcurgereaarborilorbinari

http://slidepdf.com/reader/full/parcurgereaarborilorbinari 14/16

3. Pentru arborele din figura de mai jos s re realizeze parcurgerealui în cele trei moduri posibile.

1

76

11

4

2

14

6

2

4

6

29

1

3

5

21

1

6

13

68

210

8

15

1

12

25

8/6/2019 parcurgereaarborilorbinari

http://slidepdf.com/reader/full/parcurgereaarborilorbinari 15/16

TEMSe consider un arbore binar cu 8 noduri. Dac parcurgerea înpreordine a arborelui este: 1,2,4,6,8,3,5,7 i cea în inordine este:4,2,8,6,1,5,3,7, care este parcurgerea în postordine a aceluiai arbore?

8/6/2019 parcurgereaarborilorbinari

http://slidepdf.com/reader/full/parcurgereaarborilorbinari 16/16

Lecie realizat de:

profesor Ifrim  Aliana,

Colegiul Naional Dimitrie Cantemir, Oneti