Parcurgerea arborilor Parcurgerea arborilor binaribinari

ObiectiveObiective

1.1. SemnificaSemnificaţia noţiunii de parcurgere a ţia noţiunii de parcurgere a unui arbore binar;unui arbore binar;

2.2. Tipuri de parcurgeriTipuri de parcurgeri..

1.1. SemnificaSemnificaţia noţiunii de ţia noţiunii de parcurgere a unui arbore binar;parcurgere a unui arbore binar;

► Prin parcurgerea unui arbore se înţelege Prin parcurgerea unui arbore se înţelege examinarea în mod sistematicexaminarea în mod sistematic a nodurilor sale a nodurilor sale astfel încât fiecare nod să fie atins o singură dată.astfel încât fiecare nod să fie atins o singură dată.

► Sinonim: Sinonim: ““vizitareavizitarea”” vârfurilor unui arbore vârfurilor unui arbore..► Scopul parcurgeriiScopul parcurgerii::

Prelucrarea informaţiilor asociate vârfurilor;Prelucrarea informaţiilor asociate vârfurilor; Transformarea arborelui dintr-o reprezentare Transformarea arborelui dintr-o reprezentare

plană într-o structură liniară.plană într-o structură liniară.

2.2. Tipuri de parcurgeriTipuri de parcurgeriExistExistă mai multe modalităţi de ă mai multe modalităţi de parcurgere care diferă prin ordinea de parcurgere care diferă prin ordinea de vizitare a nodurilor:vizitare a nodurilor:

► Parcurgerea în preordineParcurgerea în preordine (RSD);(RSD);► Parcurgerea în inordine (SRD);Parcurgerea în inordine (SRD);► Parcurgerea în postordine (SDR).Parcurgerea în postordine (SDR).

ObsObs.. Putem considera că fiecare nod Putem considera că fiecare nod al arborelui binar subordonează un al arborelui binar subordonează un subarbore stâng şi un subarbore drept.subarbore stâng şi un subarbore drept.

Parcurgerea în preordine Parcurgerea în preordine (RSD)(RSD)

► Plecând de la un arbore binar dat se Plecând de la un arbore binar dat se realizează în ordine următoarele realizează în ordine următoarele operaţii:operaţii:

1.1. Se vizitează rădăcina;Se vizitează rădăcina;2.2. Se vizitează subarborele stâng;Se vizitează subarborele stâng;3.3. Se vizitează subarborele drept.Se vizitează subarborele drept.

► Ca urmare a parcurgerii arborelui se Ca urmare a parcurgerii arborelui se obţine o soluţie sub forma unui tablou obţine o soluţie sub forma unui tablou unidimensional (vector).unidimensional (vector).

Fie arborele binar din figura următoare. Fie arborele binar din figura următoare. Să realizăm împreună parcurgerea în preordine a acestuia.Să realizăm împreună parcurgerea în preordine a acestuia.

1

76

3

4

2

Soluţia este:

5

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

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

► Plecând de la un arbore binar dat se Plecând de la un arbore binar dat se realizează în ordine următoarele realizează în ordine următoarele operaţii:operaţii:

1.1. Se vizitează subarborele stâng;Se vizitează subarborele stâng;2.2. Se vizitează rădăcina ;Se vizitează rădăcina ;3.3. Se vizitează subarborele drept.Se vizitează subarborele drept.

► Ca urmare a parcurgerii arborelui se Ca urmare a parcurgerii arborelui se obţine o soluţie sub forma unui tablou obţine o soluţie sub forma unui tablou unidimensional (vector).unidimensional (vector).

Plecând de la acelaşi arbore binar să realizăm acum Plecând de la acelaşi arbore binar să realizăm acum parcurgerea în inordine a acestuia. parcurgerea în inordine a acestuia.

1

76

3

4

2

5

Soluţia este: 2, 1, 6, 4, 3, 7, 5.

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

► Plecând de la un arbore binar dat se Plecând de la un arbore binar dat se realizează în ordine următoarele realizează în ordine următoarele operaţii:operaţii:

1.1. Se vizitează subarborele stâng;Se vizitează subarborele stâng;2.2. Se vizitează subarborele drept ;Se vizitează subarborele drept ;3.3. Se vizitează rădăcina.Se vizitează rădăcina.

► Ca urmare a parcurgerii arborelui se Ca urmare a parcurgerii arborelui se obţine o soluţie sub forma unui tablou obţine o soluţie sub forma unui tablou unidimensional (vector).unidimensional (vector).

Acum să realizăm parcurgerea în postordine a arboreluiAcum să realizăm parcurgerea în postordine a arborelui:: 1

76

3

4

2

5

Soluţia este: 2, 6, 4, 7, 5, 3, 1.

Aplicaţii

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

a) Care este rădăcina arborelui?b) Care sunt nodurile cu exact doi descendenţi în

arbore?c) Câte noduri are subarborele stâng al nodului 2?d) Câte nivele are arborele?e) Parcurgeţi arborele în cele trei moduri posibile.

f) Care dintre arborii desenaţi mai jos este subarbore drept al rădăcinii?

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

2. Construiţi arborele binar corespunzător tabloului următor ce conţine şirurile T (tată) şi TF (tip de fiu), apoi parcurgeţi arborele creat în cele trei moduri posibile.

TT 22 00 11 22 11 55 44 44 55 88

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

3. Pentru arborele din figura de mai jos să re realizeze parcurgerea lui î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

TEMĂSe consideră un arbore binar cu 8 noduri. Dacă parcurgerea în preordine 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 aceluiaşi arbore?

Lecţie realizată de: profesor Ifrim Aliana, Colegiul Naţional “Dimitrie Cantemir”, Oneşti