UNIVERSITATEA VALAHIA DIN TÂRGOVIŞTE

DEPARTAMENTUL PENTRU PREGĂTIREA PERSONALULUI DIDACTIC

LUCRARE METODICO – ŞTIINŢIFICǍ

PENTRU OBŢINEREA GRADULUI DIDACTIC I ÎN
ÎNVĂŢĂMÂNT

ARBORI ECHILIBRAŢI ŞI APLICAŢIILE LOR

ÎN INFORMATICĂ

COORDONATOR ŞTIINŢIFIC:
Prof. dr. ing. Luminiţa DUŢĂ
CANDIDAT:
Prof. BĂNIŢĂ Mariana (căs. TROFIMESCU)

TÂRGOVIŞTE
2016

CUPRINS

1
Capitolul 1. Introducere.......................................................................................................................4

1.1. Importanta temei.........................................................................................................................4

1.2. Locul structurilor de date arborescente în programa şcolară....................................................5

Capitolul 2. Arborii, ca structuri de date..............................................................................................6

2.1. Noţiuni generale.........................................................................................................................6

2.2. Arbore liber................................................................................................................................7

2.2.1. Definitii, denumiri, notaţii, proprietăţi, teoreme.....................................................7

2.3. Arborele parțial.........................................................................................................................12

2.3.1 Definiția arborelui parțial.....................................................................................12

2.3.2. Definiția arborelui parțial de cost minim..............................................................13

2.3.4. Algoritmul lui Kruskal............................................................................................14

2.3.5. Algoritmul lui Prim.................................................................................................19

2.4. Arborele cu rădăcină................................................................................................................25

2.4.1. Definiția arborelui cu rădăcină..............................................................................25

2.4.2 Implementarea arborelui cu rădăcină....................................................................27

2.4.3 Algoritmi pentru parcurgerea unui arbore cu rădăcină........................................29

[Link]. Algoritmul de parcurgere în lățime............................................................................29

[Link] Algoritmul de parcurgere în adâncime........................................................................30

2.5. Arbori oarecare.........................................................................................................................33

2.5.1. Reprezentarea arborilor oarecare..........................................................................33

2.5.2. Parcurgerea arborilor oarecare.............................................................................34

Capitolul 3. Arbori binari....................................................................................................................36

3.1. Definirea arborilor binari.........................................................................................................36

3.2. Proprietăţi ale arborilor binari.................................................................................................37

3.3. Parcurgerea arborilor binari....................................................................................................38

3.4. Implementarea statică a arborilor binari.................................................................................38

3.5. Alocarea dinamică a arborilor binari.......................................................................................40

Capitolul 4. Echilibrarea arborilor binari..............................................................................45

4.1. Generalităţi....................................................................................................................45

2
 4.2. Caracteristici ale arborilor AVL..................................................................................47

4.3. Definiţii..........................................................................................................................49

4.4. Cazuri de echilibrare.....................................................................................................52

4.5. Probleme rezolvate........................................................................................................57

Capitolul 5. Considerații metodice.........................................................................................65

5.1 Tipologia lecţiei de informatică..................................................................................65

5.2. Avantajele tipologizării................................................................................................65

5.3 Tipuri de lecţii specifice obiectului „Informatică”...................................................66

5.4. Tehnologie didactică şi strategii didactice...................................................................68

5.5. Strategii didactice de tip expozitiv-euristic..................................................................70

5.6. Metode si procedee explozitiv – euristice în predarea informaticii............................72

5.7. Obiectivele didactice ( generalităţi ).............................................................................78

5.7.1. Precizarea obiectivelor............................................................................................81

5.7.2. Clasificarea obiectivelor.........................................................................................82

5.8. Competenţele specifice dobândite prin studierea algoritmilor....................................85

5.9. Elaborarea strategiei didactice.....................................................................................86

[Link] didactice utile în predarea arborilor binari – Puncte cheie ale proiectării..88

5.11. Modele de proiectare didactică...................................................................................91

5.12. Probleme rezolvate....................................................................................................115

Concluzii.................................................................................................................................124

Bibliografie.............................................................................................................................126

3
Capitolul 1. Introducere

Argument

Am ales această tema deoarece am observat că arborii echilibraţi reprezintă una dintre cele
mai interesante ramuri ale informaticii care, din pacate nu se studiază la clasele de liceu.
Elevii şi studenţii au şansa de a programa la un alt nivel. Programa scolara acordă un loc
foarte puţin şi nu foarte clar precizat, cu toate ca, această parte a arborilor (adica echilibrarea
lor) se foloseste foarte mult in programe pentru criptare a datelor.

1.1. Importanta temei

Noţiunile şi algoritmii sunt prezentaţi într-un limbaj cât mai natural, însoţiţi de exemple cât se
poate de explicite. Limbajul pseudocod utilizat este conform cu manualele şcolare actuale.
Am ales codificarea în limbajul C++, fiind limbajul pe care îl predau şi care este foarte
asemănător limbajelor Java, Java Script, Pascal, limbaje ce vor permite ulterior dezvoltarea de
programe integrabile în AEL.
Numeroase probleme practice impun rezolvarea problemei echilibrarii arborilor binari.
În informatică, algoritmii pentru arbori echilibraţi sunt utilizaţi în primul rând în probleme de
criptare a informaţiei, căutarea în baza de date după o cheie, generarea unor figuri geometrice
simetrice, gestionarea memoriei interne.
Structurile de date alese pentru modelarea datelor care urmează să fie prelucrate
determină succesul unei aplicaţii. Interesul major a fost axat pe analiza diverselor modalităţi
de reprezentare şi prelucrare a structurilor de date arborescente.
Arborii sunt analizaţi ca structuri de date neliniare predominante atât în memoria
internă cât şi în memoria secundară. Azi, prin mărirea considerabilă a capacităţii de
memorare a sistemelor de calcul, importanţa acestor structuri a crescut semnificativ. Modelul
de date relaţional, apărut in 1970, s-a dezvoltat în numeroase direcţii: tipuri de date abstracte,
modele orientate obiect, la baze de date on-line. În momentul actual, eficienţa procesului de
căutare după chei în cadrul unei colecţii de date este o cerinţă imperativă. Dar, o mare
realizare este că avem multe structuri de date, de cele mai multe ori structuri arborescente prin
care se rezolvă probleme de căutare conceptual similare. De obicei, mulţimea acestor date este
dinamică şi problema se reduce la alegerea structurii de date potrivite în funcţie de tipul şi
statistica datelor care urmează a fi indexate, de proprietăţile intrinseci ale datelor şi, nu în
ultimul rând, de utilizarea lor.

4
 1.2. Locul structurilor de date arborescente în programa şcolară
Structurile de date arborescente sunt prevăzute de programa şcolară în curriculum clasei a
XI a, clase de matematică – informatică. Aşa cum se prevede în curriculumul şcolar,
„Predarea informaticii va fi orientată pe rezolvarea de probleme, utilizându-se preponderent
metoda învăţării prin descoperire şi punându-se accent pe analiza problemei. Realizarea
proiectelor în cadrul activităţilor practice va urmării dezvoltarea abilităţilor de lucru în
echipă.”
Competenţele urmărite în curriculumul şcolar pentru clasa a XI-a sunt:
Competenţe generale
1. Identificarea datelor care intervin într-o problemă şi aplicarea algoritmilor fundamentali de
prelucrare a acestora;
2. Elaborarea algoritmilor de rezolvare a problemelor;
3. Implementarea algoritmilor într-un limbaj de programare
Competenţe specifice:
1.1. Descrierea operaţiilor specifice structurilor arborescente şi elaborarea unor
subprograme care să implementeze aceste operaţii;
1.2. Analizarea în mod comparativ a avantajelor utilizării diferitelor metode de structurare
a datelor necesare pentru rezolvarea unei probleme ;
1.3. Aplicarea în mod creativ a algoritmilor fundamentali în rezolvarea unor probleme
concrete;
1.4. Elaborarea unui proiect în care să se aplice cunoştinţele de structurare a datelor şi de
abstractizare a prelucrării acestora.
Referitor la tema lucrării de faţă, pentru atingerea acestor competenţe, programa şcolară
prevede studierea următoarelor conţinuturi:
Structuri de date arborescente
• Arbori cu rădăcină (definiţie, proprietăţi, reprezentare cu referinţe ascendente, reprezentare
cu referinţe descendente).
• Arbori binari (definiţie, proprietăţi specifice; reprezentarea arborilor binari cu referinţe
descendente; operaţii specifice)
• Tipuri speciale de arbori binari
- Arbore binar complet – definiţie, proprietăţi, reprezentare secvenţială

5
 - Arbore binar de căutare – definiţie, proprietăţi, operaţii specifice (inserare nod,
ştergere nod, căutare element)
- Heap-uri – definiţie, proprietăţi, operaţii specific (inserare nod, extragerea nodului cu
cheie maximă/minima.

Capitolul 2. Arborii, ca structuri de date

2.1. Noţiuni generale

Din punct de vedere structural, cele mai simple grafuri sunt cele numite arbori. Acestea
sunt de fapt și cele mai folosite în practică. De-a lungul timpului, de studiul arborilor s-au
ocupat matematicieni și fizicieni de prima mărime. (Arborii au fost numiți astfel de către
Cayley în 1875, datorită aspectului asemănător cu arborii din botanica. Cayley a studiat arborii
și posibilitatea aplicării lor în chimia organica, iar Kirchoff a sudiat grafurile bazându-se pe
considerente din fizică, și anume rețelele electrice.) Organizarea ierarhică este întâlnită în cele
mai diverse domenii, de la organizarea administrativă a unei țări, la planificarea meciurilor în
cadrul unui turneu sportiv, de la structurarea unei cărți, până la stabilirea ordinii de execuție a
operațiilor efectuate pentru determinarea valorii unei expresii aritmetice.
De exemplu, cataloagele în care sunt grupate fișierele de pe discurile fixe sau flexibile
au o structură ierarhică. Această organizare este impusă, în principal, de rațiuni de
gestionare cât mai comodă a fișierelor de diverse tipuri, aparținând diverșilor utilizatori ai
aceluiași sistem de calcul. Și exemplele pot continua. Generalizând, într-o variantă sistemică,
orice entitate din natură sau societete poate fi reprezentată ca un tot sau ca o ierarhie de
componente. Pentru vârfurile unui arbore vom folosi termenul de nod.
Figurativ, o structură de tip arbore arată ca un arbore, în înțeles general, doar că este
răsturnat. Fiecare element din această structură poate fi privit ca o rădacină de la care pornesc
ramuri către rădăcinile altor arbori. În reprezentarea grafică a unui arbore nodurile se
desenează pe niveluri astfel: rădăcina se află pe primul nivel, vârfurile adiacente cu rădăcina
pe următorul nivel, și așa mai departe.
O primă definiție, intuitivă, a structurii de arbore este următoarea: un arbore A este fie
vid, fie format dintr-un nod rădăcină (R), căruia îi este atașat un număr finit de arbori.
Aceștia sunt denumiți subarbori ai lui A, datorită relației de “subordonare” față de rădăcină.
Deci, într-un arbore, orice nod este rădăcina unui subarbore, iar orice arbore poate fi sau poate
deveni subarbore. Între doi subarbori nu poate exista decât o relație de incluziune (unul este
subarbore al celuilalt) sau de excluziune (cei doi subarbori nu au noduri comune, dar aparțin
aceluiași arbore).

6
Mulți termeni folosiți în studiul arborilor sunt împrumutați din terminologia utilizată în cazul
arborilor genealogici sau din natură. Astfel, pentru a desemna o relație direct între două
noduri se folosesc termenii: tată, fiu și frate, cu semnificația obișnuită. Pentru relațiile
indirecte, de tipul “fiul fiului . . . fiului”, se folosesc termenii descendent sau urmaș și
respective ascendent sau strămoș. Nodurile fără descendent sunt numite noduri terminale,
sau, prin analogie cu arborii din natură, fruze.
Accesul de la rădăcina unui (sub)arbore nevid la oricare alt nod presupune parcurgerea unei
căi formate din a arce (a≥0) pe care se găsesc q noduri (q=a+1). Valoarea q reprezintă nivelul
pe care se găsește nodul față de rădăcină, aceasta fiind considerată, prin convenție, pe nivelul
0.
Înalțimea unui arbore se poate defini ca maximul dintre nivelurile nodurilor terminale,
sau, o altă definiție, recursivă: înalțimea unui arbore este egală cu 1 + maximul dintre
înălțimile subarborilor săi.
Numărul de descendenți direcți ai unui nod reprezintă ordinul nodului. În funcție de
ordinul nodurilor arborii se clasifică astfel:

Fig. 2.1. Clasificarea arborilor în funcţie de ordinul nodurilor

2.2. Arbore liber

2.2.1. Definitii, denumiri, notaţii, proprietăţi, teoreme

Definiție 2.2.1: Se numește arbore liber A un graf neorientat conex si fără cicluri.
Observație: De obicei se omite adjectivul „liber”, referirea la un graf conex aciclic făcându-se
numai cu numele arbore.
Definiție 2.2.2: Se numește subarbore al arborelui A=(X,U), orice arbore S=(Y,V) care are
proprietatea: Y⊆X și V⊆U.

7
 Exemplu: figura 2.2. Graful G1 cu 8 noduri este un arbore (un graf conex și aciclic), iar
graful G2 este un subarbore al acestuia.

a) G1 b) G2
Fig. 2.2. a) graf conex și aciclic;
2.2. b) subarbore al acestuia

Definiție 2.2.3: (Definiție recursivă dată de D.E. Knuth). Se numește arbore o mulțime finită
T de nouri care îndeplinesc proprietățile:
- există un nod cu rol special numit rădăcină (tulpină);
- celelalte noduri sunt repartizate în q ≥ 0 mulțimi disjuncte T1,. . . , Tq, unde fiecare
dintre acestea este un arbore.
Definițiile 2.2.1 și 2.2.3 sunt echivalente. Echivalența celor două definiții este justificată in
continuare.

Direct. (Definiția 2.2.1 definiția 2.2.3).

Fie arborele G, deci se presupune că G este conex și fără cicluri. Se cere să se arate că
sunt îndeplinite condițiile din definiția 2.2.3.
Se alege un nod oarecare x al lui G, ce vafi considerat drept rădăcina arborelui. Se notează cu

q numărul vecinilor acestui nod, notați x1, x2, . . . ,xq. Se consideră mulțimile Tk = {x X |

există un lanț de la x la x k } {xk}, k {1, 2, . . ., q}. Fiecare Tk poate fi considerat ca fiind

subgraf al lui G, deoarece pentru fiecare k {1, 2, . . ., q}, se rețin nodurile care alcătuiesc

mulțimea Tk și muchiile care au extremități în Tk.

Vom arăta că mulțimile Tk sunt disjuncte. Se procedează prin reducere la absurd. Se

presupune că j > i, j {1, 2, . . ., q}, i≠j, astfel încât Ti Tj≠ . Fie x Ti Tj. Deoarece x Ti,

din modul în care a fost definită mulțimea Ti rezultă că există un lanț de la xi la x. Analog
există un lanț de la xj la x. De aici se obține că în G există un lanț de la xi la xj (trecând prin

8
nodul rădăcină x). Dar cum în graful G există deja un lanț de la xi la xj, se contrazice faptul că
G este conex fără cicluri. Deci mulțimile Tk sunt disjuncte.
Vom demonstra că subgrafurile Tk sunt arbori. Din modul în care au fost construite aceste
mulțimi sunt conexe și sunt fără cicluri (altfel graful G ar conține cicluri), deci Tk sunt arbori.
S-a obținut astfel, descompunerea lui G în q arbori.

Reciproc. (Definiția 2.2.3 definiția 2.2.1)

Fie graful G. În condițiile din definiția 2.2.3, se cere să se arate că G este conex și fără cicluri,
adică arbore. În accepțiunea definiției 2.2.3, unind rădăcinile arborilor Tk, care sunt mulțimi
disjuncte, se va obține un graf conex și fără cicluri, deci definiția 2.2.1.

Proprități generale ale arborilor liberi

Teorema 2.3.1.
Următoarele afirmații sunt echivalente pentru un graf G cu n noduri și m muchii:
(1) G este un arbore (conex și fără cicluri).
(2) G este un graf aciclic cu n-1 muchii.
(3) G este graf conex cu n-1 muchii.
(4) G este un graf fără cicluri maximal (dacă în graful fără cicluri G unim două noduri
oarecare neadiacente printr-o muchie, graful obținut conține un ciclu).
(5) G este un graf conex minimal (dacă în graful conex G suprimăm o muchie oarecare,
graful obținut nu mai este conex).
(6) Oricare pereche de noduri este legată printr-un lanț și numai unul.

Demonstrație:

Este suficient să se demonstreze implicațiile (1) (2), (2) (3), (3) (4), (4) (5), (5)

(6) și (6) (1). Prin tranzitivitatea acestor implicații rezultă implicațiile (2) (1), (3)

(2), (4) (3), (5) (4), (6) (5) și (1) (6). Din aceste implicații rezultă că (1)

(2), (2) (3), (3) (4), (4) (5), (5) (6) și (6) (1). Din tranzitivitatea relației de

echivaeță rezultă oricare două din cele 6 propoziții sunt echivalente.

(1) (2). Ipoteza: Graful G este conex și aciclic (1).

Concluzie: Graful G este aciclic și are n-1 muchii (2).

9
Proprietatea că graful G este aciclic este comună ipotezei și concluzie. Trebuie demonstrat
doar că un graf conex aciclic are n-1 muchii. Dacă G este conex aciclic, nu trebuie eliminată
nici o muchie pentru a se oține un graf parțial conex aciclic. Cum numărul de muchii care
trebuie eliminate dintr-un graf conex pentru a obține un graf parțial conex aciclic este egal cu
m-n+1, înseamnă că în acest caz, m-n+1=0. Rezultă că m=n-1.

(2) (3). Ipoteza: Graful G este aciclic și are n-1 muchii (2).

Concluzie: Graful G este conex și are n-1 muchii (3).

Proprietatea că graful G are n-1 muchii este comună ipotezei și concluzie. Trebuie demonstrat
doar că un graf cu n-1 muchii fiind aciclic este și conex. Se știe că într-un graf cu p
componente conexe, numărul de muchii care trebuie eliminate pentru a obține un graf parțial
aciclic este cu m-n+p. Graful G este aciclic (m-n+p=0) și are n-1 muchii (m=n-1) și (n-1)-
n+p=0. Rezultă că p=1 (graful are o singură componentă conexă, deci este conex).

(3) (4). Ipoteza: Graful G este conex și are n-1 muchii (3).

Concluzie: Graful G este aciclic maximal (4).

Graful G fiind conex, numărul de componente conexe p este egal cu 1. Numărul de muchii m
ale grafului G este egal cu n-1. Rezultă că numărul de muchii care trebuie eliminate din graful
G ca să se obțină un graf parțial aciclic este egal cu: m-n+p=(n-1)-n+1=0, dică nici o muchie.
Rezultă că graful G este aciclic. Graful este maximal pentru această proprietate, deoarece
fiind conex, orice muchie [xi,xj] care se va adăuga va forma un ciclu cu lanțul L(xi,xj) –
existența acestui lanț rezultă din conexitatea grafului G.

(4) (5). Ipoteza: Graful G este aciclic maximal (4).

Concluzie: Graful G este conex minimal (5).

a. Presupunem că graful G nu este conex. El are cel puțin două componente conexe: C1 și C2.

Înseamnă că există două noduri x C1 și y C2 pe care le putem lega cu muchia [x,y]. Dar din

ipoteză, rezultă că orice muchie am adăuga la graf, el va conține un ciclu. Rezultă că prin
adăugarea muchiei [x,y] graful va conține un ciclu și că, între nodurile x și y există deja un
lanț și ele aparțin aceleași componente conexe, ceea ce contrazice presupunerea făcută.
Înseamnă că graful G este conex.
b. Presupunem că graful G care este conex nu este minimal cu această proprietate. Înseamnă
că prin eliminarea unei muchii se obține graful parțial H care are n noduri și m-1 muchii, este
conex și aciclic. Graful G fiind conex și aciclic, înseamnă că numărul de muchii care trebuie
eliminate pentru a obține un graf parțial conex aciclic este egal cu 0, adică m-n+1=0 și m=n-

10
1. Numărul de muchii ale grafului H este egal cu m-1=n-2. Fiind aciclic înseamnă că numărul
de muchii care trebuie eliminate pentru a obține un graf parțial aciclic este egal cu 0, adica (n-
2)-n+p=0. Rezultă că p=2, adică graful H conține două componente conexe, ceea ce
contrazice presupunerea că el este conex.

(5) (6). Ipoteza: Graful G este conex minimal (5).

Concluzie: Oricare pereche de noduri este legată printr-un lanț și numai unul (6).
Graful G fiind conex, inseamnă că există cel puțin un lanț care leagă oricare două noduri x și
y. Presupunem că există cel puțin două lanțuri între nodurile x și y: L1 și L2. Înseamnă că
suprimând o muchie din lanțul al doilea, graful rămâne conex, deoarece nodurile x și y vor fi
legate prin lanțul L1, ceea ce contrazice ipoteza că graful G este conex minimal. Rezultă că
cele două noduri x și y nu sunt legate decât printr-un singur lanț.

(6) (1). Ipoteza: Oricare pereche de noduri este legată printr-un lanț și numai unul (6).

Concluzie: Graful G este conex și aciclic (1).

Deoarece în graful G, orice pereche de noduri x și y este legată printr-un lanț, înseamnă că
graful G este conex. Presupunem că graful G conține cel puțin un ciclu. Considerând două
noduri oarecare x și y care aparțin acestui ciclu, înseamnă că între cele două noduri există
două lanțuri diferite, ceea ce contrazice ipoteza. Rezultă că graful G este aciclic.

Proprietatea 2.3.2.
Orice arbore cu n≥2 noduri conține cel puțin două oduri terminale.
Demonstrație: - prin reducere la absurd.
Presupunem că nu există decât un singur nod terminal x. Oricare alt nod din arbore are cel
puțin gradul 2. Alegem din arbore, dintre lanțurile elemenare care au o extremitate în nodul x,
lanțul de lungime maximă: L(x,y). Nodul y având gradul mai mare decât 1, înseamnă că mai
există, în afara nodului care îl precede în lanț, cel puțin un nod z care este adiacent cu el.
Lanțul fiind elementar, înseamnă că nodul y nu există în lanț decât la extremitatea lui, iar
muchia [y,z] nu face parte din lanț și putem adăuga această muchie la lanț. Lanțul fiind de
lungime maxima, înseamnă că nodul z aparține lanțului și prin adăugarea acestei muchii la
lanț se închide un ciclu, ceea ce contrazice definiția arborelui (graf aciclic).

Proprietatea 2.3.3.
Un graf cu n noduri este arbore dacă și numai dacă are n-1 muchii și nu conține cicluri.
Demonstrație:

11
“ ” Dacă graful este arbore, atunci este conex și nu conține cicluri. Trebuie demonstrat că

are n-1 muchii. Se demonstrează prin inducție matematică după n.

Dacă n=1, atunci există un singur arbore (de fapt arborele conține doar un singur nod) care are
1-1=0 muchii.
Dacă n=2, atunci există, de asemenea, un singur arbore si o singură muchie, adică 2-1=1
muchie.
Se presupune că s-a demonstrat că afirmația este adevărată pentru n=k, adică s-a demonstrat
că un arbore cu n=k noduri are k-1 muchii. Să demonstrăm că este adevărat și pentru n=k+1
noduri.
Folosind proprietatea anterioară, arborele are cel puțin două noduri terminale. Fie x unul
dintre acestea. Prin eliminarea din arbore a nodului x împreună cu muchia incidentă cu el, se
obține un arbore cu n=k noduri, care conform ipotezei de inducție are k+1-1=k muchii.
Adăugând la loc această muchie, se revine în arborele inițial, care are k+1 muchii, ceea ce
trebuia demonstrat.

“ ” Se presupune că graful are n-1 muchii și fără cicluri. Pentru a demonstra că este arbore,

trebuie demonstrat că este conex. Se reduce la absurd. Se prespune că graful nu este conex și
fie G1, G2, . . . ,Gp componentele sale conexe. Fiecare Gk îndeplinește condițiile:
1) este conexă, deoarece așa a fost aleasă;
2) nu conține cicluri, deoarece G nu are cicluri.

De aici, se poate concluziona că fiecare Gk este arbore. Pentru fiecare k {1, 2, . . . , p}, fie nk

numărul de noduri și mk numărul de muchii pentru graful G k. Avem Gk – arbore, deci mk=nk-
1. Suma nodurilor celor k componente conexe trebuie să dea totalul nodurilor grafului G și
suma muchiilor celor k componente conexe trebuie să dea totalul muchiilor grafului G, adică
n1 + . . . + nk = n și m1 + . . . +mk = m. Știind că graful are n-1 muchii, se obține: m 1 + . . .
+mk=n-1. Înlocuind valorile mk = nk -1, se obține: n1 -1 + . . . + n p -1 = n-1, adică n1 + . . . +
np=n-p-1. Dar cum graful G are n noduri, rezultă n-p-1=n, de unde p=1, adică G are o singură
componentă conexă, care nu conține cicluri, deci este arbore.

2.3. Arborele parțial

2.3.1 Definiția arborelui parțial

Definiție 2.3.1: Dacă un graf parțial al unui graf G este arbore, el se numește arbore
parțial al grafului G.

12
 a) b)
Figura 2.3. a)arbore b) arbore partial

Teorema 2.3.2: Un graf G conține un arbore parțial dacă și numai dacăeste un graf conex.
Demonstarție: Notăm cele două propoziții, astfel:
(1) – Graful G conține un arbore parțial.
(2) – Graful G este conex.

Trebuie să demonstrăm că (1) (2) și (2) (1).

(1) (2) Să considerăm că graful G conține arborele parțial H. Din definiția arborelui

rezultă că H este un graf conex. Din definiția arborelui parțial rezultă că H este graf parțial al
grafului G. Deoarece graful G se obține prin adăugarea de muchii la un graf conex (H), este și
el un graf conex.

(2) (1) Dacă G este un graf conex minimal, înseamnă că este arbore (din Teorema 2.3.1:

(1) (5)) și H=G. Dacă G este un graf conex minimal, înseamnă că există o muchie [x,y] pe

care o putem elimina astfel încât să obținem un graf parțial conex G 1. Dacă graful parțial G1
este un graf conex minimal, însemnă că H=G1; astfel se repetă procesul de eliminare a câte
unei muchii până se obține un graf parțial conex minimal. Acesta va fi arborele parțial H.

2.3.2. Definiția arborelui parțial de cost minim

Considerăm un graf conex G=(X,U), o funcție c:U R+ care asociază fiecărei muchii u

un număr real pozitiv c(u), numit costul muchiei, și un graf H=(X,V) care este graf parțial al
grafului G (V⊆U). Funcția c se numește funcția cost. Definim:
Costul grafului este suma costurilor muchiilor grafului.
costul grafului G:


13
 costul grafului parțial H:


Definiția 2.3.2: Se numește graf parțial de cost minim al unui graf G conex, cu funcția de cost
c, un graf parțial conex H care are costul minim.
Teorema 2.3.3: Graful parțial de cost minim al unui graf conex G, cu funcția de cost c, este un
arbore.
Demonstarție: - prin reducere la absurd.
Dacă graful G este un arbore, atunci H=G, deoarece orice muchie am elimina din G și-ar
pierde proprietatea de conexitate. Dacă graful G nu este un arbore, înseamnă că el conține un
număr finit de grafuri parțiale conexe. Alegem dintre aceste grafuri parțiale graful H care este
graful parțial de cost minim. Presupunem că acest graf parțial nu este arbore. Înseamnă că el
conține cel puțin un ciclu și există o muchie u=[x,y] pe care o putem elimina astfel încât să
obținem un alt graf parțial conex H1. Rezultă că:
c(H)=c(H1)-c(u)> c(H1)
Inegalitatea c(H)> c(H1) contrazice faptul că graful parțial H este de cost minim. Înseamnă că
graful parțial este arbore.
Definiția 2.3.4: Arborele care este un graf parțial de cost minim al grafului conex G, cu
funcția de cost c, se numește arbore parțial de cost minim (APM).
Exemple de aplicații în care se folosește arbore parțial de cost minim:
Orice rețea de transport, de calculatoare, rutieră, de cale ferată, aeriană,de telecomunicații, de
canalizare etc. este un graf neorintat conex. Construirea cu costuri financiare minime a unei
astfel de rețele se rezolvă prin găsirea arborelui parțial de cost minim al grafului asociat
rețelei.

2.3.3. Algoritmi de determinare a arborelui parțial de cost minim

Algoritmii pentru determinarea arborelui parțial de cost minim folosesc strategia greedy.
Pas1: Se alege un subarbore al arborelui parțial de cost minim – Hinit.
Pas2. Cât timp nu s-a format arborele parțial de cost minim execută:
Pas3. Se alege o muchie sigură din mulțimea muchiilor nealese (rămase).
Pas4. Se adaugă muchia la subarbore.
Muchia sigură trebuie să îndeplinească următoarele condiții:

să aibă costul minim;

să aparțină arborelui parțial de cost minim.

14
 Determinarea arborelui parțial de cost minim se poate face prin:
Algoritmul lui Kruskal;
Algoritmul lui Prim.
Cei doi algoritmi diferă prin:

modul în care se alege subarborele de la care se pornește;

modul în care este găsită o muchie sigură.

2.3.4. Algoritmul lui Kruskal

Graful parțial al grafului G=(X,U) care nu conține nici o muchie (are numai noduri
izolate) este format din n arbori parțiali disjuncți:

Se pornește de la doi arbori parțiali disjuncți Hi și Hj care se unifică prin adăugarea unei
muchii sigure. Muchia sigură trebuie să îndeplinească următoarele condiții:
 să aibă costul minim;
 să nu formeze cicluri cu muchiile deja alese, adică extremitățile sale să aparțină celor două

mulțimi disjuncte Xi și Xj - muchia este [xi, xj] cu xi Xi și xj Xj.

Pentru implementarea grafului se folosește ca structură de date lista muchiilor. Pentru a găsi
mai ușor muchia cu costul minim, lista muchiilor este sortată crescător, după cost.
Algoritmul pentru determinarea arborelui parțial de cost minim este următorul:
PAS1. Pentru fiecare nod i din graf execută: se formeză arborii parțiali Hi.
PAS2. Se sortează muchiile din U în ordinea crescătoare a costului c.
PAS3. Se alege muchia u cu costul minim.
PAS4. Se inițializează APM cu muchia u.
PAS5. Cât timp nu s-au selectat cele n-1 muchii execută:
PAS6: Se alege o muchie sigură din mulțimea muchiilor nealese (rămase) și se formează un
arbore parțial cu această muchie.
PAS7. Se unifică APM cu arborele format cu muchia sigură.
Pentru a ține evidența arborilor parțiali Hi care se dezvoltă, se folosește lista L. În fiecare
element L(i) al listei se memoreză numărul de ordine al arborelui parțial din care face parte
nodul i. Inițial, existând n arbori parțiali Hi, fiecare din ei conținând un nod al grafului,

15
 elementele listei vor L(i)=i, pentru i {1, 2, 3, . . . ,n}. Pe parcursul executării algoritmului,

L(i)=j înseamnă că nodul i aparține arborelui cu numărul de ordine j.

Pentru ca muchia [x,y] care se alege să fie o muchie sigură trebuie să îndeplinească
condițiile:
 să aibă costul minim – muchiile se aleg în ordine, din lista muchiilor, unde ele sunt aranjate în
ordinea crescătoare a costului;
 extremitățile sale să aparțină la doi arbori parțiali diferiți – trebuie ca L(x)≠L(y).
După ce s-a găsit o muchie sigură, unificarea arborilor se face astfel:
 dacă L(x)<L(y), se adaugă arborele parțial din care face parte nodul y la arborele parțial din
care face parte nodul x, adică se înlocuiesc toate elementele L(i)=L(y) cu valoarea L(x).
 dacă L(x) >L(y), se adaugă arborele parțial din care face parte nodul x la arborele parțial din
care face parte nodul y, adică se înlocuiesc toate elementele L(i)=L(x) cu valoarea L(y).
Pentru graful din figura 2.4.a. de mai jos se obține arborele parțial de cost minim din figura
2.4.b.

Figura 2.4.a graf Figura 2.4.b arbore partial de cost minim

Algoritmul se execută astfel:

Lista muchiilor
Muchia u [1,2] [1,3] [2,3] [2,4] [3,4] [3,6] [4,5] [4,6] [5,6] [5,7] [6,7]
Costul c 5 8 11 10 15 9 2 7 10 4 12

Lista muchiilor sortată crescător după cost

Muchia u [4,5] [5,7] [1,2] [4,6] [1,3] [3,6] [2,4] [5,6] [2,3] [6,7] [3,4]
Costul c 2 4 5 7 8 9 10 10 11 12 15

Lista arborilor parțiali – inițiali este:

Nodul i 1 2 3 4 5 6 7 Arbori parțiali
L[i] 1 2 3 4 5 6 7

16
 Muchia cu costul minim este [4,5].

L[4]=4, 4 5 L[4] L[5] Nodul i 1 2 3 4 5 6 7 m=1

L[5]=5, 4<5 L[5]=L[4]=4 L[i] 1 2 3 4 4 6 7 m n-1=6

Arborii parțiali sunt: H4=({4,5}, {[4,5]}) și

Următoarea muchie cu cost minim este [5,7].

L[5]=4, 4 7 L[5] L[7] Nodul i 1 2 3 4 5 6 7 m=2

L[7]=7, 4<7 L[7]=L[5]=4 L[i] 1 2 3 4 4 6 4 m n-1=6

Arborii parțiali sunt: H4=({4,5,7}, {[4,5], [5,7]}) și

Următoarea muchie cu cost minim este [1,2].

L[1]=1, 1 2 L[1] L[2] Nodul i 1 2 3 4 5 6 7 m=3

L[2]=2, 1<2 L[2]=L[1]=1 L[i] 1 1 3 4 4 6 4 m n-1=6

Arborii parțiali sunt: H1=({1,2}, {[1,2]}), H4=({4,5,7}, {[4,5], [5,7]}) și

Următoarea muchie cu cost minim este [4,6].

L[4]=4, 4 6 L[4] L[6] Nodul i 1 2 3 4 5 6 7 m=4

L[6]=6, 4<6 L[6]=L[4]=4 L[i] 1 1 3 4 4 4 4 m n-1=6

Arborii parțiali sunt: H1=({1,2}, {[1,2]}), H4=({4,5,6,7}, {[4,5], [4,6], [5,7]}) și

H3=({3}, ).

Următoarea muchie cu cost minim este [1,3].

L[1]=1, 1 3 L[1] L[3] Nodul i 1 2 3 4 5 6 7 m=5

L[3]=3, 1<3 L[3]=L[1]=1 L[i] 1 1 1 4 4 4 4 m n-1=6

Arborii parțiali sunt: H1=({1,2,3}, {[1,2], {[1,3]}), H4=({4,5,6,7}, {[4,5], [4,6],

[5,7]}).
Următoarea muchie cu cost minim este [3,6].

L[3]=1, 1 4 L[3] L[6] Nodul i 1 2 3 4 5 6 7 m=6

L[6]=4, 1<4 L[6]=L[3]=1 L[i] 1 1 1 1 1 1 1 m=n-1=6

Se observă că L[7]= L[6]= L[5]= L[4]= L[3]=1.

17
 Arborele parțial de cost minim este: H1=({1,2,3,4,5,6,7}, {[1,2], {[1,3], [3,6], [4,5], [4,6],
[5,7]}).
Pentru implementarea algoritmului se folosesc următoarele variabile și structuri de date:
 variabilele n și m pentru numărul de noduri, respective numărul de muchii ale grafului;
 vectorul u cu m elemente, pentru lista muchiilor;
 vectorul L, cu n elemente, pentru lista arborilor parțiali;
 variabila ct pentru a calcula costul total al arborelui;
 variabila k pentru a număra muchiile adăugate la arborele parțial; se inițializează cu 0
(arborele nu conține nici o muchie) si ajunge la valoarea n-1 (numărul de muchii ale unui
arbore cu n noduri);
 variabila i pentru indicele cu care se parcurge lista muchiilor;
 variabilele x și y pentru a memora nodurile de la extremitățile unei muchii;
și subprogramele:
 funcția procedurală citire creează lista muchiilor u prin preluarea datelor din fișier – în fișierul
[Link] pe primul rând se citește o valoare numerică ce reprezintă numărul de noduri al
grafului, iar pe următoarele rânduri trei valori numerice separate printr-un spațiu ce reprezintă
nodurile de la extremitățile unei muchii și costul asociat muchiei;
 funcția procedurală init inițializează lista L a arborilor parțiali Hi cu cei n arbori formți din
cele n noduri izolate (arborii care nu conțin muchii);
 funcția procedurală sortare sortează lista muchiilor crescător după costul asociat;

#include<fstream>
# include<iostream>
int n, m, L[20], i, j;
struct muchie {
int x, y, c; // x, y = noduri muchie; c = costul muchiei;
};
muchie u[20], aux;
void init ( )
{
for (i=1; i<=n; i++)
L[i]=i;
}
void citire ( )
{
ifstream f(“[Link]”);
int x, y, c;
f>>n;
i=0;
while(f>>x>>y>>c)
{
i++;
u[i].x=x;
u[i].y=y;
u[i].c=c;
}

18
 m=i;
[Link]( );
}
void sortare ( )
{
for (i=1; i<m; i++)
for (j=i+1; j<=m; j++)
if (u[i].c>u[j].c) {aux=u[i];
u[i]=u[j];
u[j]=aux;}
}
int main ( )
{
int k=0, x, y, ct=0;
citire ( );
sortare ( );
init ( );
cout<<”APM este format din muchiile: ”<<endl;
while (k<n-1)
{
if (L[u[i].x]!=L[u[i].y]) {
k++;
ct=ct + u[i].c; // se allege muchia i pentru a unifica doi arbori
cout<<”[“<<u[i].x<<”,”<<u[i].y<<”]”<<” “;
x=L[u[i].y]; //se unifică cei doi arbori prin muchia [x,y]
y=L[u[i].x];
for (j=1; j<=n; j++)
if (L[j]==x) L[i]=y;
}
i++; // se trece la muchia următoare din lista muchiilor
}
cout<<endl<<” costul total= “<<ct;
return 0;
}

Complexitatea algoritmului lui Kruskal

Pasul 1 are ordinul de complexitate O(n). Pasul 2 are ordinul de complexitate în
funcție de algoritmul de sortare ales. Algoritmii de sortare prin metoda selecției directe sau
metoda bulelor au ordinul de complexitate O(m2). Pasul 3 nu se poate preciza de câte ori se
execută. În cazul cel mai defavorabil, se parcurg toate cele m muchii, deci se execută de m
ori. În cazul pasului 3, pentru fiecare muchie aleasă, se parcurg toate cele n elemente ale listei
L. Rezultă că pasul 3 are ordinul de complexitate O(nxm). Ordinul de complexitate al
algoritmului va fi: O(n) + O(m2) + O(nxm) = O(max(m2, nxm)). Dacă graful are foarte
multe muchii, atunci ordinul său de complexitate este O(m2).

2.3.5. Algoritmul lui Prim

Algoritmul lui Prim se aseamăna cu algoritmul lui Dijkstra pentru determinarea
drumurilor de lungime minimă într-un graf. În graful G=(X,U), subarborele de la care se
pornește Hinit este format dintr-un nod inițial numit rădăcină (r – care se comunică
algoritmului împreună cu datele despre graf) și crește până acoperă toate nodurile din

19
mulțimea X. Dacă arborele parțial care se dezvoltă este H=(A, V), definim graful GA=(X-A,

). Nodurile care fac parte din GA sunt memorate într-o coadă de priorități Q. Coada de

priorități se deosebește de o coadă simplă, prin aceea că di nea un se extrage primul element
introdus, ci elementul cu valoarea cea mai mică (sau cea mai mare, în funcție de proprietatea
aleasă).

În coada de priorități Q se memorează pentru fiecare nod i, eticheta nodului j A cu

care formează muchia cu costul minim. La fiecare adăugare a unui nod la arbore, acesta
trebuie eliminat din coada de priorități, iar coda trebuie reactualizată pentru toate nodurile
rămase, deoarece s-a modificat mulțimea A, iar un nod din coada de așteptare poate să aibă
muchia cu costul minim cu noul nod adăugat la arborele parțial. Arborele care se dezvoltă este
memorat în lista H, astfel: pentru fiecare nod i care se adaugă la arborele parțial, se

memorează nodul j A cu care este legat prin muchie. Inițial Hinit=({r}, ), GA=(X-{r}, ), în

lista H toate elementele cu valoarea 0, iar în coada de priorități Q, fiecărui nod i≠r i se va
atribui valoarea r (Q(i)=r).

Muchia sigură trebuie să îndeplinească următoarele condiții:

 să aibă costul minim;
 să nu formeze cicluri cu muchiile deja alese, adică să unească un nod din H cu un nod
izolat din GA – extremitățile sale aparțin celor două mulțimi disjunte A și X-A (muchia este

[xi,xj] cu xi A și xj X-A).

Structura de date folosită pentru implementarea grafului este matricea costurilor.

Algoritmul pentru determinarea APM este următorul:
PAS1. Se inițializează APM cu nodul rădăcină r.
PAS2. Se inițializează lista H astfel:

pentru fiecare nod i din graf execută: H(i) 0.

PAS3. Se inițializează coada de priorități Q astfel:

Q(r) 0

pentru fiecare nod i≠r din graf execută: Q(i) r.

PAS4. Cât timp nu s-au selectat cele n-1 muchii execută:

20
PAS5. Se alege o muchie sigură din mulțimea muchiilor nealese – muchia [i,j] cu i A și j

X-A

PAS6. Se adaugă muchia la lista H: H(j) Q(j).

PAS7. Se elimină din coada de priorități nodul j adăugat la arbore, atribuindu-i valoarea 0:

Q(j) 0.

PAS8. Se actualizează coada de priorități pentru nodurile nealese, astfel:

pentru fiecare nod i din Q execută:

caută nodul j A cu care formează muchia cu costul minim

Coada de priorități Q este implementată cu un vector cu n elemente. Inițial:

În timpul execuției algoritmului:

La terminarea execuției algoritmului Q(i)=0, pentru orice i ( ).

Lista H este implementată cu un vector cu n elemente. Inițial: H(i)=0, pentru orice i (

).

În timpul execuției algoritmului:

La terminarea execiției algoritmului:

21
 Pentru ca muchia [i,j] care se alege să fie o muchie sigură trebuie să îndeplinească condițiile:
 să aibă costul minim – se caută nodul j care în mtricea costurilor elementul a[Q[j]][j] are
valoarea minimă.
 extremitățile sale să aparțină la doi arbori parțiali diferiți – trebuie ca Q(i)≠0 și Q(j)=0.
După ce s-a gasit o muchie sigură, ea este adăugată la arbore prin T(j)=Q(j).
Pentru graful din figura 3, considerând r=1, algoritmul se execută astfel:
Lista muchiilor:
Muchia u [1,2] [1,3] [2,3] [2,4] [3,4] [3,6] [4,5] [4,6] [5,6] [5,7] [6,7]
Costul c 5 8 11 10 15 9 2 7 10 4 12

Arborele parțial (H) și coada de priorități Q – inițial sunt:

Nodul i 1 2 3 4 5 6 7 Arborele inițial
H[i] 0 0 0 0 0 0 0
Q[i] 0 1 1 1 1 1 1 min=5
Costul muchiei [i,Q[i]] - 5 8 VMAX VMAX VMAX VMAX j=2

Muchia de cost minim este [Q[j],j]=[Q[2],2]=[1,2].

Nodul i 1 2 3 4 5 6 7
H[2]=Q[2] H[i] 0 1 0 0 0 0 0
Q[2]=0 Q[i] 0 0 1 1 1 1 1
Costul [i,Q[i]] - - 8 VMAX VMAX VMAX VMAX

Actualizare Q[i] 0 0 1 2 1 1 1 min=8

Q Costul [i,Q[i]] - - 8 10 VMAX VMAX VMAX j=3

Arborele parțial H=({1,2}, {[1,2]}) și X-A={3,4,5,6,7} m=1.

Muchia de cost minim este [Q[j],j]=[Q[3],3]=[1,3].

Nodul i 1 2 3 4 5 6 7
H[3]=Q[3] H[i] 0 1 1 0 0 0 0
Q[3]=0 Q[i] 0 0 0 1 1 1 1
Costul [i,Q[i]] - - - 10 VMAX VMAX VMAX

Actualizare Q[i] 0 0 0 2 1 3 1 min=9

22
 Q Costul [i,Q[i]] - - - 10 VMAX 9 VMAX j=6

Arborele parțial H=({1,2,3}, {[1,2], [1,3]}) și X-A={4,5,6,7} m=2.

Muchia de cost minim este [Q[j],j]=[Q[6],6]=[3,6].

Nodul i 1 2 3 4 5 6 7
H[6]=Q[6] H[i] 0 1 1 0 0 3 0
Q[6]=0 Q[i] 0 0 0 2 1 0 1
Costul [i,Q[i]] - - - 10 VMAX - VMAX

Actualizare Q[i] 0 0 0 6 6 0 6 min=7

Q Costul [i,Q[i]] - - - 17 10 - 12 j=4

Arborele parțial H=({1,2,3,6}, {[1,2],[1,3], [3,6]}) și X-A={4,5,7} m=3.

Muchia de cost minim este [Q[j],j]=[Q[4],4]=[6,4].

Nodul i 1 2 3 4 5 6 7
H[4]=Q[4] H[i] 0 1 1 6 0 3 0
Q[4]=0 Q[i] 0 0 0 0 6 0 6
Costul [i,Q[i]] - - - - 10 - 12
Actualizare Q[i] 0 0 0 0 4 0 6 min=2
Q Costul [i,Q[i]] - - - - 2 - 12 j=5

Arborele parțial H=({1,2,3,4,6}, {[1,2],[1,3], [3,6],[4,6]}) și X-A={5,7} m=4.

Muchia de cost minim este [Q[j],j]=[Q[5],5]=[4,5].

Nodul i 1 2 3 4 5 6 7
H[4]=Q[4] H[i] 0 1 1 6 4 3 0
Q[4]=0 Q[i] 0 0 0 0 0 0 6
Costul [i,Q[i]] - - - - - - 12
Actualizare Q[i] 0 0 0 0 0 0 5 min=4
Q Costul [i,Q[i]] - - - - - - 4 j=7

Arborele parțial H=({1,2,3,4,5,6}, {[1,2],[1,3], [3,6],[4,5],[4,6]}) și X-A={7} m=5.

Muchia de cost minim este [Q[j],j]=[Q[7],7]=[5,7].

23
 Nodul i 1 2 3 4 5 6 7
H[4]=Q[4] H[i] 0 1 1 6 4 3 5
Q[4]=0 Q[i] 0 0 0 0 0 0 0
Costul [i,Q[i]] - - - - - - -
Actualizare Q[i] 0 0 0 0 0 0 0 X-A=

Q Costul [i,Q[i]] - - - - - - -

Arborele parțial H=({1,2,3,4,5,6,7}, {[1,2],[1,3], [3,6],[4,5],[4,6],[5,7]}) m=6.

Pentru implementarea algoritmului se folosesc următoarele variabile si structuri de date:

 variabilele n și r pentru numărul de noduri, respectiv pentru nodul rădăcină;
 matricea pătratică A, cu dimensiunea n, pentru matricea costurilor asociată grafului;
 vectorul Q, cu n elemente, pentru coada de priorități;
 vectorul H, cu n elemente, pentru lista muchiilor din APM;
 variabila ct pentru a calcula costul total al arborelui;
 variabila k pentru a număra muchiile adăugate la arborele parțial; initial are valoarea 0 –
arborele nu conține nici o muchie – si ajunge la valoarea n-1 (numărul de muchii ale unui
arbore cu n noduri);
 variabile i și j pentru indicele cu care se parcurge coada de priorități, respectiv pentru nodul
care se adaugă la arbore;
și subprogramele:
 funcția procedurală init_mc inițializează matricea costurilor;
 funcția procedurală citire_mc actualizează matricea costurilor cu datele din fișier;
 funcția procedurală init_Q inițializează coada de priorități Q;
 funcția operand muchie caută o muchie sigură în mulțimea muchiilor nealese;
 funcția procedurală actualizează_Q actualizează coada de priorități Q după ce a fost adăugată
muchia la arborele parțial;
 funcția procedurală afișare afișează APM.
#include<iostream>
#include<fstream>
int a[50][50], Q[50], H[50], n, r;
cons tint VMAX=5000;
ifstream f(“[Link]”);
void init_mc ( )
{
int i, j;
f>>n;
for (i=1; i<=n; i++)

24
 for (j=1; j<=n; j++)
if (i!=j) a[i][j]=VMAX;
}
void citire_mc ( )
{
int i, j, c;
while (f>>i>>j>>c)
{
a[i][j]=c;
a[j][i]=c;
}
[Link] ( );
}
void init_Q ( )
{
for ( int i=1; i<=n; i++)
if (i!=r) Q[i]=r;
}
int muchie ( )
{
int i, j, min=VMAX;
for (i=1; i<=n; i++)
if (Q[i]!=0 && a[Q[i]][i]<min) { min= a[Q[i]][i];
j=i; }
return 0;
}
void actualizeaza_Q (int j)
{
for (int i=1; i<=n; i++)
if (Q[i]!=0 && a[i][Q[i]]>a[i][j]) Q[i]=j;
}
void afisare ( )
{
cout<<”APM este format din muchiile: “<<endl;
for (int i=1; i<=n; i++)
if (H[i]!=0) cout<<”[“<<H[i]<<”,”<<i<<”]”<<” “;
}

int main ( ) {
int i, j, k=0, ct=0;
init_mc ( );
citire_mc ( );
cout<<”Nodul initial: “;
cin>>r;
init_Q ( );
while (k<n-1)
{
j=muchie ( );
H[j]=Q[j];
Q[j]=0;
actualizeaza_Q ( j);
k++;

25
 }
cout<<”costul total = “<<ct<<endl;
afisare ( );
return 0 }

Complexitatea algoritmului lui Prim

Pasul 2 și pasul 3 au ordinal de compexitate O(n). Pasul 4 se execută de n-1 ori. În cazul
pasului 3, pentru fiecare muchie aleasă, se execută pasul 5 și pasul 8 de n ori. Rezultă că Pasul
3 are ordinal de complexitate O((n-1)x(n+n))=O(n2). Ordinul de complexitate al algoritmului
va fi: O(n)+O(n)+O(n2)=O(n2).

2.4. Arborele cu rădăcină

2.4.1. Definiția arborelui cu rădăcină

Dediniția 3.1.1: Se numește arbore cu rădăcină un arbore A în care există un nod
privilegiat numit nod rădăcină.
Terminologie – mulți din termenii folosiți sunt preluați din terminologia arborilor genealogici
sau a arborilor din natură.

Fig. 2.5 Arbore cu rădăcină

 Muchiile unui arbore se numesc ramuri sau arce.

 Nodul rădăcină mai este numit vârf sau tulpină. În nodul rădăcină nu intră nici un arc.
 Într-un nod intră un singur arc (exceptând rădăcina) care îl leagă de un alt nod numit părinte
sau predecesor.
 Dintr-un nod pot să iasă niciunul, unul sau mai multe arce care îl leagă de un alt nod numit fiu
sau succesor.
 Nodurile fără succesori (din care nu iese nici un arc) se numesc frunze sau noduri terminale.
Nodurile care nu sunt terminale se mai numesc noduri de ramificare.

26
 Două noduri adiacente din arbore sunt în relația tată-fiu sau părinte-fiu, iar muchiile sunt
legături de tip tată-fiu. Între mai multe noduri se poate stabili o relație de tipul fiul fiului . . .
fiului sau tatăl tatălui . . . tatălui. În primul caz se poate spune că nodul este descendent sau
urmaș al unui alt nod, iar în al doilea caz că nodul este ascendent sau strămoș al unui nod.
 Două noduri care descind direct din același nod tată se numesc noduri frate.
 Ordinul unui nod este dat de numărul de descendenți direcți.
 Nodurile sunt organizate pe niveluri. Numerotând nivelurile nodurilor, rădăcina se găsește pe
nivelul 0, descendenții ei pe nivelul 1, descendenții acestora pe nivelul 2 etc. Nivelul unui nod
este egal cu numărul de noduri parcurse pe calea de la rădăcină la el.
 Un arbore cu rădăcină este arbore vid (arborele nul) dacă nu are nici un nod.
 Înălțimea unui arbore este dată de maximul dintre nivelurile nodurilor terminale (lungimea
celui mai lung lanț care pornește din rădăcină)
Caracteristici:
 Nodul rădăcină este considerat privilegiat. El nu are părinte (ascendent), ci numai fii
(descendenți). Este nodul de la care se consideră că pornesc ramurile către rădăcinile altor
arbori. Orice nod al arborelui poate fi considerat nod rădăcină.
 Un arbore A este fie vid fie format dintr-un nod rădăcină R căruia îi este atașat un număr finit
de arbori. Acești arbori sunt subordonați rădăcinii și se numesc subarbori ai arborelui A .
Orice nod dintr-un arbore este rădăcina unui subarbore.
 Între doi subarbori nu pot exista decât două tipuri de relații:
- relația de incluziune: unul dintre subarbori este subarborele celuilalt
- relația de excluziune: cei doi subarbori nu au noduri comune, dar aparțin
aceluiași arbore.
 Accesul la rădăcina unui arbore (subarbore) nevid la oricare nod, înseamnă parcurgerea unui
lanț format din m arce, care trec ptin n noduri (m=n+1), n reprezentând nivelul pe care se
găsește nodul față de rădăcină.

Definiții recursive:
Definiția arborelui. Un arbore nevid este o mulțime finite A de noduri care au următoarele
proprietăți:
a. Există un nod care poate fi considerat nod rădăcină.
b. Celelalte noduri pot fi repartizate în i (i≥0) mulțimi disjuncte (A1, A2, . . . , Ai), fiecare dintre
aceste mulțimi fiind considerate la rândul lor arbori.
Definiția înălțimii: Înălțimea unui arbore este egală cu 1+maximul dintre înălțimile
subarborilor săi.

27
 Definiție: Se numește arbore ordonat un arbore cu rădăcină în care fii fiecărui nod sunt
ordonați.
Observație: Într-un arbore ordonat, dacă un nod are k fii, atunci există un prim fiu, un al
doilea fiu, . . . , un al k-lea fiu.
Definiție: Se numește arborescență sau structură arborescentă un arbore cu rădăcină în cre s-a
stabilit nodul rădăcină.

2.4.2 Implementarea arborelui cu rădăcină

Implementarea structurilor de date de tip arbore cu rădăcină se poate face prin:
 matrice de adiacență;
 listă de adiacență;
 referințe descendente – legătura de tip tată
 referințe ascendente – legătura de tip părinte nod terminal.
Arborele, fiind un graf neorientat cu anumite proprietăți, pentru implementarea sa statică se
pot folosi aceleași metode ca și la grafuri, dar aceste implementări sunt ineficiente. Arborilor
le sunt specificate implementarea cu legătura de tip tată si implementarea cu legătura de tip
părinte nod terminal. În următoarele implementări se consideră că arborele are n noduri și
rădăcina are eticheta r.
1) Implementarea prin referințe descendente
Legătura de tip tată.
Arborele este reprezentat sub forma unui vector t cu n elemente în care se memorează,
pentru fiecare nod, eticheta părintelui său. Algoritmul de construire a vectorului este
următorul:
PAS1. Pentru fiecare nod i din arbore execută:

PAS2. Dacă nodul i=r, atunci t[i] 0;

altfel t[i] j, unde j reprezintă nodul părinte al nodului i.

Exemplu: Vectorul tată pentru arborele din figura de mai jos este:

28
 Fig. 2.6. Arbore

Părinte (t[i]) 3 3 0 3 1 2 4 1 6
Nod (indice i) 1 2 3 4 5 6 7 8 9
Din vectorul de tați putem obține următoarele informații:
- eticheta nodului rădăcină – indicele i pentru care t[i]=0;
- etichetele nodurilor de tip frunză (nodurile terminale) – nodurile j a căror etichetă nu există în
vectorul t;
- eticheta părintelui unui nod j - t[j];
- etichetele fiilor unui nod j – indicii i pentru care t[i]=j;
- etichetele fraților unui nod j – indicii i pentru care t[i]=t[j].
2) Implementarea prin referințe ascendente
Legătura de tip părinte nod terminal.
Arborele este reprezentat sub forma a doi vectori cu n-1 elemente: vectorul t în care
sunt memorate nodurile, în ordine, pornind de la nodurile terminale, și vectorul pt în care sunt
memorate nodurile părinte ale nodurilor terminale. Algoritmul de construire a celor doi
vectori este:
PAS1. Pentru fiecare indice i de la 1 la n-1 execută:
PAS2. Se caută nodul terminal cu eticheta cea mai mică.
PAS3. Se atribuie această etichetă lui t[i].
PAS4. Se atribuie lui pt[i] eticheta nodului părinte al nodului terminal t[i].
PAS5. Se elimină din arbore nodul terminal t[i].

29
 Exemplu. Pentru arborele din figura 2. 7 de mai jos, cei doi vectori se completează astfel:

Fig.2.7. Arbore

- inițial nodurile terminale au etichetele: 5, 8, 9 și 7. Se alege nodul terminal cu eticheta cea mai
mică (5). Se scrie eticheta sa în primul element al vectorului t, iar eticheta părintelui său (1) în
primul element al vectorului pt. Se înlătură nodul 5 din arbore.
- nodurile terminale au etichetele: 8, 9 și 7. Se alege nodul terminal cu eticheta cea mai mică
(7). Se scrie eticheta sa în al doilea element al vectorului t, iar eticheta părintelui său (4) în al
doilea element al vectorului pt. Se înlătură nodul 7 din arbore.
- nodurile terminale au etichetele: 8, 9 și 4. Se alege nodul terminal cu eticheta cea mai mică
(4). Se scrie eticheta sa în al treilea element al vectorului t, iar eticheta părintelui său (3) în al
treilea element al vectorului pt. Se înlătură nodul 4 din arbore.
- procedeul de adăugare în vectorul t a nodului cu eticheta cea mai mică și a părintelui său în
vectorul pt, urmată de eliminarea din arbore a nodului adăugat, continuă până când în arbore
nu mai rămâne decât nodul care are cea mai mare etichetă.
Vectorii t și pt pentru arborele din figura 2.7 sunt:
Părinte nod terminal (pt[i]) 1 4 3 1 3 2 6 9
Nod terminal (t[i]) 5 7 4 8 1 3 2 6
(indice vector i) 1 2 3 4 5 6 7 8

Vectorii t și pt sunt aceași pentru un arbore, indiferent de nodul rădăcină ales.

2.4.3 Algoritmi pentru parcurgerea unui arbore cu rădăcină

Parcurgerea unui arbore cu rădăcină se poate face prin:
 Algoritmul de parcurgere în lățime;
 Algoritmul de parcurgere în adâncime;

30
 [Link]. Algoritmul de parcurgere în lățime
Metoda: se prelucrează mai întâi informația din nodul rădăcină, după care sunt prelucrate, de
la stânga la dreapta, nodurile aflate pe primul nivel, apoi pe cel de al doilea etc.
Structura de date folosită este coada (c) în care se adaugă fii nodului prelucrat.
Algoritmul pentru prelucrarea arborelui este următorul:
PAS1. Se inițializează coada cu nodul rădăcină r.
PAS2. Cât timp coada nu este vidă execută (prim<=ultim):
PAS3. Este extrasdin coadă primul nod și este prelucrat.
PAS4. Sunt adăugați în coadă fii nodului prelucrat.

Fig.2.8. Parcurgerea arborelui în lăţime

Exemplu: Coada de așteptare la parcurgerea arborelui din figura 2.8 de mai sus:
Pas 1 3 4 3 4 3 4 3 4 3 4 3 4 3 4 3
Nod curent 1 2 3 4 5 6 7 8
Coada 1 - 23 3 34 4 456 56 56 6 678 78 78 8 8 -

Nodurile sunt parcurse în ordinea: 1, 2, 3, 4, 5, 6, 7, 8.

[Link] Algoritmul de parcurgere în adâncime

Metoda: pornind de la nodul rădăcină se prelucrează fiii unui nod de la stânga la dreapta,
iar trecerea, de la nodul curent la fratele din dreapta, se face numai după ce au fost vizitați toți
descendenții nodului curent, deci ai întrgului subarbore dezvoltat din acesta. În funcție de
ordinea relativă de prelucrare a nodului rădăcină și, respectiv, a subarborilor, există algoritmi:
 Algoritmul de parcurgere în preordine. Informația din nodul rădăcină este prelucrată înaintea
informațiilor din celelalte noduri ale subarborilor. Implementarea arborelui se face prin
referințe descendente.

31
 Algoritmul de parcurgere în postordine. Informația din nodul rădăcină este prelucrată după
ce au fost prelucrate informațiile din toate celelalte noduri ale subarborilor. Implementarea
arborelui se face prin referințe ascendente.
 Algoritmul de parcurgere în preordine
Structura de date folosită este stiva (st) în care informația este formată din perechi (nod
tată, următorul fiu neprelucrat al acestuia). Inițial, se consideră că nodul prelucrat este nodul
rădăcină. Notăm: NC= nod curent
NP= nod prelucrat (nodul care s-a vizitat)
PFNNC= primul fiu neprelucrat al nodului curent
PFNNP= primul fiu neprelucrat al nodului prelucrat
În vârful stivei se va memora perechea (NP, PFNNP).
Algoritmul pentru parcurgerea arborelui este următorul:
PAS1. Se inițializează stiva cu perechea (nodul rădăcină, primul fiu al rădăcinii).
PAS2. Cât timp stiva nu este vidă (mai există noduri în stivă) execută:
PAS3. Se extrag informații din vârful stivei despre:

- Nodul prelucrat devine nod curent NC st[vf]. NP (la prima parcurgere NC 1)

- Primul fiu neprelucrat al nodului prelucrat devine primul fiu neprelucrat al nodului curent

PFNNC st[vf]. PFNNC (la prima parcurgere PFNNC 3).

- Primul fiu neprelucrat al nodului curent devine nod prelucrat NP PFNNC (la prima

parcurgere NP 2).

- Primul fiu neprelucrat al nodului prelucrat devine primul fiu neprelucrat al nodului prelucrat

PFNNP st[vf]. PFNNP (la prima parcurgere PFNNC 4).

PAS4. Dacă nodul curent mai are și alți fii neprelucrați, atunci la stivă se adaugă perechea (NC,
PFNNC). La prima parcurgere perechea este (1, 3).
PAS5. Dacă nodul prelucrat nu este nod terminal și mai are fii neprelucrați, atunci la stivă se
adaugă perechea (NP, PFNNP). La prima parcurgere perechea este (2, 4).
Exemplu: Stiva la parcurgerea arborelui din figura 2.8:

PAS Stivă NC NP PFNNC PFNNP

1 (1, 2) 1 2

32
 3 - 1 2 3 4

4 (1, 3) 1 2 3 4

5 (1, 3); (2, 4) 1 2 3 4

3 (1, 3) 2 4 - -

4 (1, 3) 2 4 - -

5 (1, 3) 2 4 - -

3 - 1 3 - 5

4 - 1 3 - 5

5 (3, 5) 1 3 - 5

3 - 3 5 6 7

4 (3, 6) 3 5 6 7

5 (3, 6); (5, 7) 3 5 6 7

3 (3, 6) 5 7 8 -

4 (3, 6); (5, 8) 5 7 8 -

5 (3, 6); (5, 8) 5 7 8 -

3 (3, 6) 5 8 - -

4 (3, 6) 5 8 - -

5 (3, 6) 5 8 - -

3 - 3 6 - -

4 - 3 6 - -

5 - 3 6 - -

Nodurile sunt parcurse în ordinea: 1, 2, 4, 3, 5, 7, 8, 6.

Prin parcurgerea în lățime a unui arbore cu rădăcină, prelucrarea informațiilor din noduri se
face pe niveluri ierarhice, iar prin parcurgerea în adâncime în preordine a unui arbore,
prelucrarea informațiilor din noduri se face după relațiile de subordonare.

 Algoritmul de parcurgere în postordine

33
 Nodului rădăcină i se va atribui cea mai mare etichetă. Prelucrarea se face prin parcurgerea
simultană a celor doi vectori și căutarea nodurilor care aparțin aceluiași subarbore. Evidența
nodurilor prelucrate este ținută prin intermediul vectorului vizitat.
Algoritmul pentru parcurgerea arborelui în postordine este următorul:
PAS1. Se inițilizează cu 0 elementele vectorului vizitat.
PAS2. Cât timp mai sunt noduri nevizitate execută:
PAS3. Se caută în vectorul t indicele k al primului nod nevizitat.
PAS4. Se prelucrează nodul t[k] și se declară vizitat.
PAS5. Pentru toate nodurile t[i] frate cu nodul t[k] execută:
PAS6. Se prelucrează nodul t[i] și se declară vizitat.
PAS7. Se prelucrează părintele nodului t[k] și se declară vizitat.

2.5. Arbori oarecare

2.5.1. Reprezentarea arborilor oarecare

Nodurile unui arbore oarecare pot fi reprezentate sub forma unei zone de memorie
alocată dinamic sau sub forma unui tablou de date alocate static. Fie următorul arbore:

Fig.3.1. Arbore oarecare

Reprezentarea unui arbore oarecare se poate face astfel:
a) Scrierea parantezată: Fiind dat un arbore cu vârfurile etichetate (numere sau caractere),
definim scrierea lui parantezată ca fiind scrierea parantezată a rădăcinii sale. Ea constă în
scrierea etichetei ataşată nodului urmată, numai dacă are descendenţi, de scrierea parantezată
a descendenţilor cuprinsă între paranteze.
Pentru arborele de mai sus, scrierea parantezată este:
4(11(5,10),7,8(2,3,1(6)),9(12))

34
Pentru un nod oarecare putem folosi următoarea reprezentare cu informaţiile alocate dinamic:
informaţia; adresa primului descendent (fiu) stâng; adresa primului frate drept.

Această structură poate fi reprezentată astfel:

typedef struct nod
int inf;
nod *fiu_stang, *frate_drept;
ARBORE;
Pentru fiecare nod se poate stoca: informaţia; numărul de descendenţi; adresa fiecărui
descendent;
Implementarea poate fi făcută astfel:
typedef struct nod
int inf;
int nr; //numărul descendenţilor
nod *fiu[NR_MAXIM_FII]; //tablou cu adresele descendenţilor
ARBORE;

2.5.2. Parcurgerea arborilor oarecare

Prin parcurgere se înţelege vizitarea în mod sistematic a nodurilor arborelui în scopul
prelucrării informaţiei ataşate nodurilor sau a liniarizării nodurilor.
Vom exemplifica metodele de parcurgere pe următorul arbore:
Un arbore oarecare poate fi parcurs astfel:
în preordine: se vizitează rădăcina şi apoi descendenţii direcţi ai fiecărui nod de la stânga la
dreapt
Pentru arborele din fig. 3.1, succesiunea în preordine a nodurilor este:
4,11,5,10,7,8,2,3,1,6,9,12
în postordine: se parcurg de la stânga la dreapta descendenţii direcţi ai fiecărui nod şi apoi se
vizitează rădăcina
Pentru arborele de mai sus, succesiunea postordine a nodurilor este:
5,10,11,7,2,3,6,1,8,12,9,4
pe nivele: se parcurg în ordine nodurile de pe fiecare nivel de la stânga la dreapta, începând
de la primul nivel la ultimul nivel:
Pentru arborele de mai sus, succesiunea postordine a nodurilor este:
4,11,7,8,9,5,10,2,3,1,12,6
După cum se observă definirea celor trei moduri de parcurgere este recursivă.

35
 Pentru parcurgerea în preordine procedăm astfel: se vizitează nodul rădăcină şi se
apelează recursiv funcţia de parcurgere pentru fiecare descendent, de la stânga la dreapta.
Pentru parcurgerea în postordine se apelează recursiv funcţia pentru parcurgerea
tuturor descendenţilor şi apoi se va afişa informaţia nodului rădăcină.
Pentru parcurgerea pe nivele (orizontală) se utilizează o parcurgere de tip coadă pentru
că este o parcurgere BF (în lăţime). Cât timp coada nu este vidă se extrage nodul curent din
coadă şi se adaugă la capătul opus al cozii toţi descendenţii nodului.
Programul următor gestionează un arbore oarecare reprezentat prin metoda a treia
descrisă în secţiunea anterioară: pentru fiecare nod se precizează informaţia ataşată, numărul
de descendenţi şi tabloul cu adresele acestor descendenţi. Programul ilustrează modul de
creare a unui astfel de arbore, cele trei metode de parcurgere descrise precum şi ştergerea
din memorie a arborelui creat. Pentru ştergere se va proceda astfel: se şterg mai întâi toşi
descendenţii unui nod, după care se şterge nodul tată. Ultimul nod şters va fi rădăcina
arborelui.
#include<iostream>
using namespace std;
#define NMAX 30 //numarul maxim de descendenti ai unui nod
typedef struct nod{
int inf;
int n; //numarul de descendenti
nod *leg[NMAX]; //tabloul adreselor descendentilor
}ARB;
ARB *coada[100]; //coada pentru parcurgerea pe nivele
int prim,ultim; //pentru gestionarea cozii
ARB* Creare() //creaza arborele oarecare si returneaza adresa radacinii
{
int info,nr,i; ARB *p;
cout<<"informatia nodului: "; cin>>info;
p=new ARB; p->inf=info;
cout<<"numarul descendentilor pentru "<<info<<": ";
cin>>nr; p->n=nr;
//se descriu in ordine descendentii de la stanga la dreapta si in adancime
for(i=0;i<p->n;i++) p->leg[i]=Creare();
//apelez recursiv functia pentru crearea descendentilor
return p; //radacina arborelui
}
void Preordine(ARB *p) //afiseaza nodurile in preordine
{
int i;
if(p)
{
cout<<p->inf<<" "; //afisez nodul tata
for(i=0;i<p->n;i++) Preordine(p->leg[i]); //afisez descendentii
}
}

36
void Postordine(ARB *p) //afiseaza nodurile in postordine
{
int i;
if(p)
{
for(i=0;i<p->n;i++)
if(p->leg[i]) Postordine(p->leg[i]); //afisez descendentii
cout<<p->inf<<" "; //afisez nodul tata
}
}
void Adauga(ARB *p) //adauga un nod in coada
{
if(prim>ultim) cout<<"Coada este plina\n";
else coada[ultim++]=p;
}
ARB* Extrage_nod() //extrage un nod din coada
{
if(prim==ultim) return 0;
else return coada[prim++];
}
void Traversare_nivele(ARB *rad)
{
ARB *p; int i;
prim=ultim=0;
Adauga(rad); //in coada se introduce nodul radacina
do{
p=Extrage_nod(); //extrag un nod din coada
if(p)
{
cout<<p->inf<<" "; //afisez informatia nodului
for(i=0;i<p->n;i++)
Adauga(p->leg[i]); //adaug in coada descendentii nodului
}
}while(p);
cout<<"\n";
}
void Sterge(ARB *p) //stergerea unui nod din arbore
{
int i;
if(p)
for(i=0;i<p->n;i++) Sterge(p->leg[i]);
//mai intai sterg descendentii nodului
delete p; //sterg nodul tata
}
int main()
{
ARB *rad; //radacina arborelui oarecare
cout<<"\n\t\tIntroduceti arborele:\n";
rad=Creare(); //arborele a fost creat
cout<<"\n\t\tTraversarea in preordine:\n";
Preordine(rad);
cout<<"\n\t\tTraversarea in postordine:\n";

37
 Postordine(rad);
cout<<"\n\t\tTraversarea pe nivele:\n";
Traversare_nivele(rad);
Sterge(rad); //stergerea arborelui din heap
return 0;}

Capitolul 3. Arbori binari

3.1. Definirea arborilor binari

Un arbore binar este o mulţime finită de noduri care este fie vidă, fie reprezintă un arbore
ordonat în care fiecare nod are cel mult doi descendenţi.

Fig. 3.1. Arbore binar

Un arbore binar conţine cel mult doi subarbori, pe care îi numim subarbore stâng, respectiv
subarbore drept. Ei se pot obţine prin suprimarea rădăcinii şi a nodurilor incidente cu
aceasta. Un nod fără descendenţi se numeşte nod terminal sau frunză.Un arbore binar în care
fiecare nod are 0 sau 2 descendenţi se numeşte arbore binar complet. Un astfel de arbore
apare în figura de mai jos.

38
 Fig.3.2. Arbore binar comple

3.2. Proprietăţi ale arborilor binari

1. Un arbore binar complet care are n noduri terminale, toate situate pe acelaşi nivel, are
în total 2n-1 noduri. În consecinţă, un arbore binar complet are un număr impar de noduri.
2. Numărul maxim de noduri de pe nivelul i al unui arbore este 2i.
3. Numărul maxim de noduri dintr-un arbore binar cu înălţimea h este 2h+1-1.
4. Un arbore binar cu n noduri are înălţimea mai mare sau egală cu [log2n].

3.3. Parcurgerea arborilor binari

Prin parcurgerea arborilor binari se înţelege, ca şi la grafurile obişnuite, examinarea
în mod sistematic a nodurilor astfel încât fiecare nod să fie atins o singură dată. Această
procedură se mai numeşte şi vizitare a nodurilor arborelui în scopul prelucrării informaţiei
conţinută de fiecare dintre acestea. Deoarece arborii sunt o structură neliniară de date, rolul
traversării este tocmai obţinerea unei aranjări liniare a nodurilor, pentru ca trecerea de la unul
la altul să se realizeze cât mai simplu posibil. Există trei modalităţi de parcurgere a arborilor
binari, toate utilizând modul standard de reprezentare (sau alocarea dinamică): în preordine
(Rădăcină-Stânga-Dreapta), în inordine (Stânga-Rădăcină-Dreapta) şi în postordine (Stânga-
Dreapta-Rădăcină). Aceste trei sunt definite recursiv şi parcurgerea se face în trei etape:
a) Traversarea în preordine (RSD)
- se vizitează rădăcina
- traversează subarborele stâng
- traversează subarborele drept
b) Traversarea în inordine (SRD)
- se traversează subarborele stâng
- se vizitează rădăcina
- se traversează subarborele drept
c) Traversarea în postordine (SDR)
- se traversează subarborele stâng
- se traversează subarborele drept
- se vizitează rădăcina
Pentru arborele binar din figura 3.2 de mai sus, avem următoarele rezultate ale parcurgerilor:

39
- metoda RSD: 1, 2, 4, 5, 6, 7, 8, 9, 3
- metoda SRD: 4, 2, 6, 5, 8, 7, 9, 1, 3
- metoda SDR: 4, 6, 8, 9, 7, 5, 2, 3, 1

3.4. Implementarea statică a arborilor binari

Există mai multe posibilităţi de reprezentare a arborilor binari. În continuare sunt
descrise trei metode de reprezentare statică a arborilor binari. Vom considera pentru
exemplificare următorul arbore binar:

Fig.3.3. Arbore binar

a) Implementarea standard se bazează pe următorul principiu: pentru fiecare nod în

parte se precizează, dacă există, descendentul stâng şi descendentul drept. Dacă un nod este
terminal, atunci acest lucru se precizează punând 0 în locul descendenţilor săi. Pentru aceast
se utilizează fie doi vectori numiţi, de exemplu, S-pentru descendenţii din stânga şi D-pentru
descendenţii din dreapta. Dacă pentru reprezentarea unui arbore binar cu n noduri se folosesc
vectorii S şi D, atunci pentru fiecare nod i1,2,....n componenta S[i] conţine descendentul
stâng al nodului i, iar componenta D[i] conţine descendentul drept al nodului i.
De exemplu, pentru arborele binar de mai sus, cei doi vectori vor avea următoarea
structură:

40
 Nodul i 1 2 3 4 5 6 7 8 9

S[i] 2 4 0 0 6 0 8 0 0
D[i] 3 5 0 0 7 0 9 0 0

Se observă că nu este important să se precizeze rădăcina, deoarece ea nu este descendenta nici

unui nod.
b) Legături de tip tată. Se folosesc doi vectori: TATA şi DESC. Pentru fiecare nod i,
TATA[i] precizează care nod îi este ascendent (nodul părinte). DESC[i] poate lua două
valori: -1 dacă i este descendent stâng pentru TATA[i] şi 1 dacă este descendent drept pentru
acesta. Pentru nodul rădăcină, care nu are un nod părinte asociat, valoarea corespunzătoare în
cei doi vectori este 0. Pentru arborele binar de mai sus, configuraţia celor doi vectori este:

Nodul i 1 2 3 4 5 6 7 8 9

TATA[i] 0 1 1 2 2 5 5 7 7

DESC[i] 0 -1 1 -1 1 -1 1 -1 1

c) Implementarea cu paranteze (parantezată). Pentru a obţine o reprezentare a

arborelui folosind paranteze, se procedează în felul următor:
1. se scrie nodul rădăcină
2. fiecare nod al arborelui va fi urmat de:
- paranteză rotundă deschisă
- descendent stâng
- virgulă
- descendent drept
- paranteză rotundă închisă
Pentru arborele din figura anterioară, reprezentarea parantezată este:
1( 2 (4 , 5 ( 6 , 7 ( 8 , 9 ) ) ) , 3)

3.5. Alocarea dinamică a arborilor binari

În acest mod de alocare, fiecare nod este o structură cu trei câmpuri: informaţia ataşată
nodului, adresa fiului stâng şi adresa fiului drept. Absenţa unui fiu este marcată cu pointerul
nul. Se observă că acest mod de reprezentare este similar cu reprezentarea standard de la
alocarea statică a arborilor binari. Pentru descrierea unui nod putem folosi declaraţiile:
typedef struct nod

41
 int inf; //sau orice alt tip pentru informaţie
nod *st,*dr; //adresele fiilor
ARB;

Crearea unui arbore binar alocat dinamic se realizează cel mai uşor aplicând metoda Divide
et Impera astfel:
- se generează un nod, adică se alocă spaţiu în heap şi se încarcă informaţia
- pentru fiecare nod se construieşte subarborele său stâng, apoi subarborele său drept şi
se completează adresele descendenţilor nodului cu adresele acestor subarbori
- un descendent vid trebuie marcat printr-o proprietate stabilită asupra informaţiei (spre
exemplu apariţia valorii 0 drept conţinut informaţional al nodului curent)
Spre exemplu, pentru arborele binar urmator şirul datelor furnizat la intrare va arăta astfel:
1240057000306800900 ceea ce corespunde unei liste în preordine a nodurilor.

Fig.3.4. Arbore binar

Funcţia care crează un arbore binar furnizat ca mai sus este:

typedef struct nod{
int inf;
nod *st,*dr;
}ARB;
void Creare(ARB* &r)
{
int x;
cin>>x;
if(!x) //urmeaza subarbore vid
r=0;
else
{
r=new ARB; r->inf=x;
//creare nod curent si memorare informatie
Creare(r->st); Creare(r->dr); //crearea subarborilor
}
}

42
Funcţia Creare() se poate proiecta astefel încât să întoarcă adresa rădăcinii arborelui. În acest
caz, funcţia va avea antetul: ARB* Creare(ARB* &r).
Întotdeauna este reprezentat subarborele stâng și apoi subarborele drept. Dacă un nod nu are
un succesor, succesorul va fi considerat arborele vid.
Definiție. Se numește arbore vid un arbore care are adresa NULL.
Algoritmul pentru crearea unui arbore binar implementat dinamic folosește strategia divide et
impere prin descompunerea probleme în trei subprobleme:

1. crearea nodului rădăcină (cazul de bază);

2. crearea subarborelui stâng;
3. crearea subarborelui drept.
Descompunerea problemei continuă până când subarborele care se crează este arborele
vid. Combinarea soluțiilor se face prin legătura nodului rădăcină de cei doi subarbori.
void creare(nod *&r) //funcție procedural;
{int n;
cout<<”eticheta nod”;
cin>>n;
if(n==0) r=NULL;
else { r=new nod;
r nr=n;

creare(r s);

creare(r d); }
}
}

Observație: Datorită definiției arborilor binari, algoritmii utilizați, pentru prelucrarea lor
pot folosi tehnica recursivității (definiția recursivă a arborilor binari) și strategia divide et
impera (fiecare nod nu are decât doi descendenți – prelucrarea unui nod se descompune în
două subprobleme: prelucrarea subarborelui stâng și prelucrarea subarborelui drept, urmată de
compunerea celor două soluții).

Algoritmul RSD
Metoda: se prelucrează rădăcina, subarborele stâng, subarborele drept
Implementare statică Implementare dinamică
void rsd (int i) void rsd ( nod *r)
{ cout<<i<<” “; { if (r!=NULL) { cout<<r nr<<” “;
if (st[i]!=0) rsd(st[i]);

43
 if (dr[i]!=0) rsd(dr[i]);} rsd (r s);
void main ( )
{ . . . rsd (r); cout<<endl; . . . } rsd (r d);}}

void main ( )
{ . . . rsd (r); cout<<endl; . . . }

Algoritmul SRD
Metoda: se prelucrează subarborele stâng, rădăcina, subarborele drept
Implementare statică Implementare dinamică
void srd (int i) void srd ( nod *r)
{ if (st[i]!=0) srd(st[i]); { if (r!=NULL) { srd (r s);
cout<<i<<” “;
if (dr[i]!=0) srd(dr[i]);} cout<<r nr<<” “;
void main ( )
{ . . . srd (r); cout<<endl; . . . } srd (r d);}}

void main ( )
{ . . . srd (r); cout<<endl; . . . }

Algoritmul SDR
Metoda: se prelucrează subarborele stâng, subarborele drept, rădăcina
Implementare statică Implementare dinamică
void sdr (int i) void sdr ( nod *r)
{ if (st[i]!=0) sdr(st[i]); { if (r!=NULL) { sdr (r s);
if (dr[i]!=0) sdr(dr[i]);
cout<<i<<” “;} sdr (r d);
void main ( )
{ . . . sdr (r); cout<<endl; . . . } cout<<r nr<<” “;}}

void main ( )
{ . . . sdr (r); cout<<endl; . . . }

44
Programul care implementează cele trei metode de parcurgere (bazate pe o strategie DEI) este
prezentat în continuare:
#include<iostream>
using namespace std;
#define N 30
int S[N],D[N],rad,n;
void SRD(int k) //parcurgere inordine
{
if(S[k]) SRD(S[k]);
cout<<k<<" ";
if(D[k]) SRD(D[k]);
}
void RSD(int k) //parcurgere preordine
{
cout<<k<<" ";
if(S[k]) RSD(S[k]);
if(D[k]) RSD(D[k]);
}
void SDR(int k) //parcurgere postordine
{
if(S[k]) SDR(S[k]);
if(D[k]) SDR(D[k]);
cout<<k<<" ";
}
int main()
{
int i;
cout<<"numar varfuri, n=";
do{
cin>>n;
}while(n<1||n>N);
cout<<"radacina arborelui: ";
do{
cin>>rad;
}while(rad<1||rad>n);
//memorarea arborelui prin vectorii S,D
for(i=1;i<=n;i++)
{
cout<<"descendentii stanga,dreapta ("<<i<<"): ";
cin>>S[i]>>D[i];
}
cout<<"\n\tParcurgerea in preordine:\n";
RSD(rad);
cout<<"\n\n\tParcurgerea in inordine:\n";
SRD(rad);
cout<<"\n\n\tParcurgerea in postordine:\n";
SDR(rad);
cout<<"\n";
return 0;
}

45
Capitolul 4. Echilibrarea arborilor binari

4.1. Generalităţi
Se caută ca în programarea arborilor să se lucreze cu arbori echilibraţi care să asigure
un timp de execuţie bun atât pentru operaţiile de cautare, inserare, ştergere, cât şi în cazul
unor operaţii complexe. Arborii AVL sau arborii echilibraţi sunt arbori binari ordonaţi, care
au în plus o proprietate de echilibru .
Proprietatea de echilibru e valabilă pentru orice nod al arborelui si spune că: “înălţimea
subarborelui stâng al nodului diferă de înălţimea subarborelui drept al nodului prin cel mult o
unitate”.
Pentru a descrie gradul de echilibru al structurilor arborescente sunt definite două abordări:

Arbori perfecţi echilibraţi în care pentru fiecare nod, diferenţa dintre numărul de noduri ale
subarborelui drept şi stâng ia valori în mulţimea {-1 ; 0 ; +1}. Într-un arbore perfect echilibrat
de înălţime h, toate nodurile frunză sunt pe acelaşi nivel şi orice nod de pe nivelurile
intermediare 1..h-2 are numărul maxim de fii.
De exemplu, figura 4.1 descrie un arbore binar de căutare perfect echilibrat;

46
 Fig.4.1 Arbore binar perfect echilibrat

Cea mai simplă metoda de a obţine un astfel de arbore se bazează pe parcurgerea prin metoda
divide et impera a şirului de chei ordonate crescător şi inserarea valorii din mijloc în arbore;
această metodă este ineficientă în practică deoarece presupune realizarea unui volum mare de
calcule după fiecare operaţie de inserare sau ştergere. Efortul ridicat de prelucrare este dat de
parcurgerea în inordine a arborelui pentru a obţine şirul sortat crescător al cheilor si de
reconstrucţia structurii. Considerând un arbore binar de căutare, metoda utilizată în acest
sens, echilibrareArb, are ca parametrii şirul sortat crescător al valorilor, vectorul chei,
dimensiunea acestuia, dim, limitele intervalului curent, stanga, respectiv, dreapta, şi rădăcina
arborelui ce va fi creat. Menţinerea unei astfel de structuri reprezintă o operaţie cu grad de
complexitate foarte ridicat, fapt care conduce la recrearea arborelui perfect echilibrat după
fiecare operaţie de inserare sau ştergere cu metoda echilibrareArb;

void echlibrareArbore(int *chei, int dim, int stanga, int dreapta, NodArbore
*&radacina) {
if (dreapta>=stanga) {
int mijloc=(dreapta+stanga)/2;
if (dreapta-stanga==1) {
radacina =inserareArbore(radacina, chei[stanga]); radacina =
inserareArbore (radacina, chei[dreapta]);
}

else {
if (dreapta==stanga)
radacina = inserareArbore (radacina, chei[stanga]);
else {
radacina = inserareArbore (radacina, chei[mijloc]); echlibrareArbore
(chei,dim,stanga, mijloc -1, radacina); echlibrareArbore (chei,dim,
mijloc +1,dreapta, radacina);
}
}
}

47
 }

Imperfect echilibrat în care pentru fiecare nod, diferenţa dintre înălţimea subarborelui drept
şi înălţimea subarborelui stâng ia valori în mulţimea {-1 ; 0 ; +1}. Crearea unei astfel de
structuri se bazează pe utilizarea metodei prezentate anterior pornind de la un set de valori
sortate crescător sau descrescător. Menţinerea gradului de echilibru al structurii după
operaţiile de inserare sau ştergere este posibilă prin metode cu un grad de complexitate
acceptabil şi care sunt specifice unor structuri arborescente echilibrate particulare, AVL,
arbori B, arbori Rosu & Negru. Aceste metode implică un efort de prelucrare mai mic decât
volumul operaţiilor asociat reconstrucţiei arborelui prin metoda echilibrareArb.
Structurile arborescente sunt structuri de date dinamice în care elementele sunt
poziţionate ierarhic în funcţie de legătura părinte – copil ce există între două elemente. Din
punct de vedere al minimizării efortului de regăsire, această organizare este mai eficientă în
raport cu structurile dinamice liniare, deoarece reduce numărul de comparări necesar
identificării unui element. În cazul unei structuri de date liniare, cel mai nefavorabil caz
descrie o complexitate egală cu O(m), unde m reprezintă numărul de elemente, şi este generat
de căutarea ultimului element. Această situaţie este întâlnită şi în cazul structurilor
arborescente ineficient construite, în care fiecare nod are maxim un fiu şi care au asociată
imaginea unei liste.
Pentru a evita acest lucru şi pentru de a beneficia de efectele pozitive ale utilizării
structurilor arborescente în operaţiile de căutare se definesc reguli stricte de realizare ale unei
astfel de structuri. Prin prisma acestor reguli, structurile arborescente se diferenţiază pe mai
multe tipuri. Dintre acestea, structurile arborescente echilibrate ocupă o pondere ridicată în
dezvoltarea de soluţii eficiente deoarece descriu un nivel constant de efort apropiat de cel
optim.

4.2. Caracteristici ale arborilor AVL

Un arbore AVL, definit prima dată de G.M. Adelson-Velskii şi E.M. Landis în
[Ande62], este un arbore binar de căutare echilibrat pe înălţime. Un arbore binar de căutare
este AVL dacă gradul de echilibru al fiecărui nod ia valori în mulţimea {-1,0,1}.
Pentru a măsura gradul de echilibru al unui nod se defineşte indicatorul GE ce descrie relaţia:
GE = H(SD) – H(SS)

unde H() reprezintă funcţia de calcul a înălţimii unei structuri arborescente. Pentru a
determina înălţimea unui arbore, al cărui nod rădăcină este rad, se utilizează formula:

48
 H(rad) = 1 + max (H(subarbore drept), H(subarbore stâng))
în care funcţia max() este utilizată pentru a determina maximul dintre două valori.
int max(int valoare_1, valoare_2)
{
return valoare_1 < valoare_2 ? valoare_2 : valoare_1;
}

Pentru valoarea indicatorului GE = 0, nodul este echilibrat, iar pentru valorile 1 si -1,
nodul descrie un dezechilibru la dreapta, respectiv la stânga. Figura 4.2, descrie arborele binar
de căutare pentru care s-a determinat gradul de echilibru.
Situaţiile în care GE are valoarea -1 sau 1 sunt acceptate deoarece, pentru un număr
par de valori este imposibil sa se definească un arbore binar de căutare în care toate nodurile
sunt perfect echilibrate.

Fig.4.2. Arbore binar de cautare echilibrat

Arborele AVL, reprezintă un arbore binar de căutare echilibrat. Pornind de la această

ipoteza, acest tip de arbore moşteneşte toate operaţiile implementate de arborii binari de
căutare. Caracteristica de echilibru se gestionează prin verificarea atentă a gradului de
echilibru, pentru fiecare nod în parte, în urma operaţiilor de inserare şi ştergere.
Aceste tipuri de prelucrări afectează structura arborelui şi conduc la situaţii de dezechilibru.
Pentru a menţine arborele AVL, după fiecare operaţie de inserare, respectiv ştergere, sunt
căutate situaţiile de dezechilibru puternic, identificate prin intermediul nodurilor pentru care
indicatorul GE ia valori în mulţimea {-2,2}.
Structura elementelor unui arbore echilibrat poate fi reprezentată astfel:
struct nod
{
int key; int ech;

49
nod *left, *right;
};
nod * rad;

unde
- key reprezintă eticheta nodului (un numar intreg),
- ech- reprezintă factorul de echilibrare
- left şi right reprezintă pointeri către copilul din stânga, respectiv din drapta.

4.3. Definiţii
Def1: Se numeste inaltime a unui arbore ca fiind lungimea celui mai lung drum de la
nodul radacină la unul din nodurile terminale.
Înălțimea arborelui binar
int max(int x, int y)
{ if(x>y) return x;
else return y;}
int h(int i)
{ if (st[i]==0&&dr[i]==0) return 0;
else return 1+max(h(st[i]), h(dr[i]));}
int main()
{ int r;
.......
cout<<h(r);
.........
}

Def2: Se numeste factor de echilibrare diferenta dintre înălţimea subarborelui drept şi

înălţimea subarborelui stang.
Def3: Atasând fiecarui nod un camp care reprezinta factorul de echilibrare al sau, se spune că
arborele binar este echilibrat când toţi factorii de echilibrare ai nodurilor sunt -1,0,+1.
Formal, acest lucru se traduce astfel:
X

hs hd

50
 Fig. 4.3. Înălţimea arborelui
| hs – hd | ≤ 1, oricare ar fi nodul X apartinând arborelui, unde hs si hd reprezintă înălţimea
subarborelui stang, respectiv înălţimea subarborelui drept.
De exemplu, fie arborele din figura 4.4.

Fig.4.4. Arbore binar

Exemple de proceduri pentru calculul înălţimii unui subarbore şi a factorilor de
echilibru

- înălţimea întregului arbore este 5, adică lungimea celui mai lung drum de la nodul
radacină la unul din nodurile terminale.
- înălţimea subarborelui stâng al rădăcinii este 4, adică lungimea celui mai lung drum de
la nodul cu eticheta 7 la unul din nodurile terminale, cu etchetele 2 respectiv 1.
- pentru a afla factorul de echilibru al rădăcinii scădem înălţimea subarborelui stâng din
înălţimea subarborelui drept, adică 1-4=-3.
- factorul de echilibru al nodului cu eticheta 6 este foarte simplu de determinat. Observăm
că nodul nu are niciun copil şi atunci factorul de echilibru este 0.
- pentru a afla factorul de echilibru al nodului cu eticheta 5 scădem înălţimea subarborelui
stâng din înălţimea subarborelui drept, adică 2-1=1.
Vom prezenta în continuare funcţia drum, care calculează cel mai lung drum de la un nod
curent, adică înălţimea unui subarbore:

void drum_maxim(nod* p, int &max, int lung)

{ if (p!=NULL)
{
drum(p->right,max,lung+1);}
if ((p->left==NULL) && (p->right==NULL) && (max<lung))
max=lung;
drum(p->left,max,lung+1); }

51
Folosindu-ne de această funcţie putem determina indicatorul de echilibru al fiecarui nod al
arborelui cu funcţia fact_ech:

void calcul_factor_echilibru (nod *p)

{ int hLeft, hRight;
h_left=1;
h_right=1;
if(p->left!=NULL){
drum_maxim(p->left,h_left,1);
else
h_left=0; }
if(p->right!=NULL){
drum_maxim(p->right,h_right,1);
else
h_right=0;
p->ech=h_right-h_left; }}

Practic, arborii AVL se comporta la fel ca arborii binari ordonati simpli, mai puţin în
cazul operaţiilor de inserţie şi suprimare de chei.
O inserţie într-un arbore binar ordonat poate duce la dezechilibrarea anumitor noduri,
dezechilibrare manifestată prin nerespectarea formulei | hs – hd | ≤ 1 pentru respectivele
noduri.
În principiu, o cheie se inserează într-o primă fază, ca şi într-un arbore binar ordonat
obişnuit, adică se porneşte de la rădăcină şi se urmează fiul stâng sau fiul drept, în funcţie de
relaţia dintre cheia de inserat şi cheia nodurilor prin care se trece, până se ajunge la un fiu nul,
unde se realizează inserţia propriu-zisă.
În acest moment se parcurge drumul invers (care este unic) şi se caută pe acest drum primul
nod care nu este echilibrat, adică primul nod ai carui subarbori diferă ca înălţime prin 2
unităţi. Acest nod trebuie echilibrat şi el se va afla întotdeauna într-unul din cele 4 cazuri
prezentate în continuare. Reechilibrarea arborelui binar de căutare şi păstrarea caracteristicilor
aferente arborilor AVL se realizează prin operaţii de rotire:
- rotire simpla la stânga;
- rotire simpla la dreapta;
- dubla rotire la stânga ;
- dubla rotire la dreapta.
Este important de reţinut că printr-o singură rotaţie, selectată în funcţie de situaţie, un
arbore AVL dezechilibrat în urma operaţiei de inserare va fi reechilibrat. În schimb, operaţie
de reechilibrare în urma ştergerii unui nod este mult mai complexă, necesitând minim o
rotaţie.

52
4.4. Cazuri de echilibrare
Cazul 1-rotatie simpla dreapta

Fig. 4.5. Rotaţie simplă dreapta

Cazul 1 - Rotaţie simplă stânga – este simetric în oglindă fată de cazul 1- rotaţie simplă
dreapta

Fig. [Link]ţie simplă stânga

53
Cazul 2 - Rotaţie dublă dreapta

Fig. 4.7. Rotaţie dublă dreapta

54
Cazul 2 - Rotaţie dublă stanga – simetric în oglindă fată de cazul 2 - rotaţie dublă dreapta

Fig. 4.8. Rotaţie dublă stânga

Exemplu:
Se va considera secvenţa de chei 4,5,7,2,1,3,6 care se inserează într-un arbore AVL iniţial
vid. Evoluţia arborelui şi echilibrarile sunt:
-nodurile cu cheile 4,5 se vor insera ca şi la arborii binari de cautare
-în mod normal nodul cu cheia 7 ar fi inserat în dreapta nodului cu eticheta 5.
În acest caz arborele este dezechilibrat.

55
 4
5 (0)

5 (1)
4 (0) 7 (0)
7 (0)

Fig.4.9. Exemplu de echilibrare

-nodul cu cheia 2 se va insera in stanga nodului cu cheia 4 fara ca arborele sa se

dezechilibreze
-nodul cu cheia 1 se va insera in stanga nodului cu cheia 2, dar in acest caz arborele este
dezechilibrat:

Fig.4.10. Exemplu de echilibrare

-dupa inserarea nodului 3 arborele se va dezechilibra din nou:

56
 Fig.4.11. Exemplu de echilibrare

-nodul cu cheia 6 s-ar insera in stanga nodului cu cheia 7, dar in acest caz arborele ar fi
dezechilibrat:

Fig.4.12. Exemplu de echilibrare

Arborii AVL reprezintă o alternativă puţin costisitoare la arborii binari obişnuiţi. Cu

preţul unor reechilibrări suplimentare şi fără a modifica semnificativ performanţa inserţiei şi
suprimării cheilor (celelalte operaţii rămânând nemodificate), proprietatea de echilibru AVL a
unui arbore binar ordonat duce la căutari mult mai rapide decât în cazul unui arbore binar
ordonat obişnuit, datorită înălţimii mai mici.
S-a demonstrat că un arbore echilibrat AVL va avea întotdeauna înălţimea cuprinsă între
[log2N+1] si [1,43·log2N+1], unde N reprezintă numarul de chei din arbore si [x] este partea
întreaga a lui x.

57
 Spre comparatie, un arbore binar ordonat perfect echilibrat va avea întotdeauna
înălţimea egală cu [log2N+1] dar a-l menţine perfect echilibrat este mult mai costisitor (ca
timp) decât în cazul arborilor AVL.
De asemenea, un arbore binar ordonat obişnuit va avea înălţimea cuprinsă între
[log2N+1] si N, deci poate ajunge la înaltimi mult mai mari decât un arbore AVL cu aceleaşi
chei.

4.5. Probleme rezolvate

Parcurgerile arborilor binari

1. Se citesc din fisierul [Link] de pe prima linie două numere n şi R reprezentând numărul de
noduri şi rădăcina unui arbore binar. De pe a doua şi a treia linie se vor citi câte n elemente
reprezentând rădăcinile subarborilor stâng şi respectiv drept al fiecărui nod, sau 0 dacă nu există
subarborele.
Afişaţi pe ecran şirurile parcurgerilor RSD, SRD şi SDR ale arborelui citit.
[Link] Rezultate
81 RSD: 1 2 4 5 6 3 7 8
24700000 SRD: 4 2 5 6 1 7 3 8
35806000 SDR: 4 6 5 2 7 8 3 1

1. #include<fstream>
2. #include<iostream>
3. using namespace std;
4. int i,n,St[101],R,Dr[101];
5. void citire()
6. {
7. ifstream f("[Link]");
8. f>>n>>R;
9. for(i=1;i<=n;i++) f>>St[i];
10. for(i=1;i<=n;i++) f>>Dr[i];
11. [Link]();
12. }
13. void RSD(int p)
14. {
15. if(p>0)
16.
17. { cout<<p<<' ';
18. RSD(St[p]);
19. RSD(Dr[p]);
20. }
21. }

58
22. void SRD(int p)
23. {
24. if(p>0)
25. {
26. SRD(St[p]);
27. cout<<p<<' ';
28. SRD(Dr[p]);
29. }
30.
31. }
32. void SDR(int p)
33. {
34. if(p>0)
35. {SDR(St[p]);
36. SDR(Dr[p]);
37. cout<<p<<' ';}
38.
39. }
40. int main()
41. {
42. citire();
43. cout<<"RSD: ";
44. RSD(R);
45. cout<<endl;
46. cout<<"SRD: ";
47. SRD(R);
48. cout<<endl;
49. cout<<"SDR: ";
50. SDR(R);
51. }

59
Vectorul de taţi
2. Se citesc din fisierul [Link] de pe prima linie două numere n şi R reprezentând numărul de noduri şi
rădăcina unui arbore binar. De pe a doua şi a treia linie se vor citi câte n elemente reprezentând rădăcinile
subarborilor stâng şi respectiv drept al fiecărui nod, sau 0 dacă nu există subarborele.
Afişaţi pe ecran vectorul de taţi al arborelui citit.
[Link] Rezultate
81 81
24700000 01122533
35806000

1. #include<fstream>
2. #include<iostrea>
3. using namespace std;
4. int i,n,St[101],R,Dr[101],T[101];
5. void citire()
6. {
7. ifstream f("[Link]");
8. f>>n>>R;
9. for(i=1;i<=n;i++) f>>St[i];
10. for(i=1;i<=n;i++) f>>Dr[i];
11. [Link]();
12. }
14. void tati(int x,int p)
15. {
16. if(x>0)
17. {
18. T[x]=p;
19. tati(St[x],x);
20. tati(Dr[x],x);
21. }
22. }
24. void tipar()
25. {
26. int i;
27. cout<<n<<' '<<R<<'\n';
28. for(i=1;i<=n;i++)
29. cout<<T[i]<<' ';
30. }
32. int main()
33. {
34. citire();
35. tati(R,0);
36. tipar();
37. }

60
Lista nodurilorarborelui
3. Se citesc din fisierul [Link] de pe prima linie două numere n şi R reprezentând numărul de
noduri şi rădăcina unui arbore binar. De pe a doua şi a treia linie se vor citi câte n elemente reprezentând
rădăcinile subarborilor stâng şi respectiv drept al fiecărui nod, sau 0 dacă nu există subarborele.
Afişaţi pe ecran lista nodurilor terninale, lista nodurilor cu un singur fiu şi lista nodurilor care au exact
doi fii.
[Link] Rezultate
81 Noduri terminale (frunze): 4 6 7 8
24700000 Noduri cu un fiu: 5
35806000 Noduri cu doi fii: 1 2 3
2. #include<iostream>
3. using namespace std;
4. int i,n,St[101],R,Dr[101];
5. void citire()
6. {
7. ifstream f("[Link]");
8. f>>n>>R;
9. for(i=1;i<=n;i++) f>>St[i];
10. for(i=1;i<=n;i++) f>>Dr[i];
11. [Link]();
12. }
14. void fii(int p,int k)
15. {
16. int f=0;
17. if(p>0)
18. {
19. if(St[p]>0) f++;
20. if(Dr[p]>0) f++;
21. if(f==k) cout<<p<<' ';
22. fii(St[p],k);
23. fii(Dr[p],k);
24. }
25. }
27. int main()
28. {
29. citire();
30. cout<<"Noduri terminale (frunze): ";
31. fii(R,0);
32. cout<<'\n';
34. cout<<"Noduri cu un fiu: ";
35. fii(R,1);
36. cout<<'\n';
38. cout<<"Noduri cu doi fii: ";

61
39. fii(R,2)}

62
Numărul nodurilor

4. Se citesc din fisierul [Link] de pe prima linie două numere n şi R reprezentând numărul de
noduri şi rădăcina unui arbore binar. De pe a doua şi a treia linie se vor citi câte n elemente
reprezentând rădăcinile subarborilor stâng şi respectiv drept al fiecărui nod, sau 0 dacă nu există
subarborele.
Afişaţi pe ecran numărul nodurilor terninale, numărul nodurilor cu un singur fiu şi numărul nodurilor
care au exact doi fii.

[Link] Rezultate
81 Noduri terminale (frunze): 4
24700000 Noduri cu un fiu: 1
35806000 Noduri cu doi fii: 3

1. #include<fstream>
2. #include<iostream>
3. using namespace std;
4. int i,n,St[101],R,Dr[101];
5. void citire()
6. {
7. ifstream f("[Link]");
8. f>>n>>R;
9. for(i=1;i<=n;i++) f>>St[i];
10. for(i=1;i<=n;i++) f>>Dr[i];
11. [Link]();
12. }
14. int fii(int p,int k)
15. {
16. int f=0;
17. if(p>0)
18. {
19. if(St[p]>0) f++;
20. if(Dr[p]>0) f++;
21. if(f==k)
22. return 1+fii(St[p],k)+fii(Dr[p],k);
23. Else
24. return fii(St[p],k)+fii(Dr[p],k);
25. }
26. }
28. int main()
29. {
30. citire();
31. cout<<"Noduri terminale (frunze): "<<fii(R,0);
32. cout<<'\n';
34. cout<<"Noduri cu un fiu: "<<fii(R,1);
35. cout<<'\n';

63
37. cout<<"Noduri cu doi fii: "<<fii(R,2);}

64
Înălţimea unui arbore binar

5. Se citesc din fisierul [Link] de pe prima linie două numere n şi R reprezentând numărul de
noduri şi rădăcina unui arbore binar. De pe a doua şi a treia linie se vor citi câte n elemente
reprezentând rădăcinile subarborilor stâng şi respectiv drept al fiecărui nod, sau 0 dacă nu există
subarborele.

Afişaţi înălţimea arborelui binar citit.

[Link] rezultate
81 Inaltimea arborelui: 3

24700000
35806000

1. #include<fstream>
2. #include<iostream>
3. using namespace std;

4. int i,n,St[101],R,Dr[101];
5.
6. void citire()
7. {
8. ifstream f("[Link]");
9. f>>n>>R;
10. for(i=1;i<=n;i++) f>>St[i];
11. for(i=1;i<=n;i++) f>>Dr[i];
12. [Link]();
13. }
14.
15. int h(int p, int k)
16. {
17. int a,b;
18. if((St[p]==0)&&(Dr[p]==0)) return k;
19. Else
20. {
21. a=h(St[p],k+1);
22. b=h(Dr[p],k+1);
23. if(a>b) return a;
24. else return b;
25. }
26. }
27.
28. int main()
29. {
30. citire();
31. cout<<"Inaltimea arborelui: "<<h(R,0);
32. }

65
66
Arbore binar strict
6. Se citesc din fisierul [Link] de pe prima linie două numere n şi R reprezentând numărul de
noduri şi rădăcina unui arbore binar. De pe a doua şi a treia linie se vor citi câte n elemente
reprezentând rădăcinile subarborilor stâng şi respectiv drept al fiecărui nod, sau 0 dacă nu există
subarborele.
Verificaţi dacă arborele citit este un arbore binar strict, adică fiecare nod are 0 sau 2 noduri fii.
[Link] rezultate
81 Nu este arbore binar strict
24700000
35806000

1. #include<fstream>
2. #include<iostream>
3. using namespace std;

4. int i,n,St[101],R,Dr[101];

5. void citire()
6. {
7. ifstream f("[Link]");
8. f>>n>>R;
9. for(i=1;i<=n;i++) f>>St[i];

10. for(i=1;i<=n;i++) f>>Dr[i];

11. [Link]();
12. }
13.
14. int fii(int p,int k)
15. {
16. int f=0;
17. if(p>0)
18. {
19. if(St[p]>0) f++;
20. if(Dr[p]>0) f++;
21. if(f==k)
22. return 1+fii(St[p],k)+fii(Dr[p],k);
23. Else
24. return fii(St[p],k)+fii(Dr[p],k);
25. }
26. else return 0;
27. }
29. int main()
30. {
31. citire();
32. if(fii(R,1)==0)
33. cout<<"Arbore binar strict";
34. Else
35. cout<<"Nu este arbore binar strict";}

67
68
Arbore echilibrat
7. Se citesc din fisierul [Link] de pe prima linie două numere n şi R reprezentând numărul
de noduri şi rădăcina unui arbore binar. De pe a doua şi a treia linie se vor citi câte n elemente
reprezentând rădăcinile subarborilor stâng şi respectiv drept al fiecărui nod, sau 0 dacă nu
există [Link]ţi dacă arborele citit este un arbore binar echilibrat. Un arbore este
echilibrat dacă diferenţa dintre înălţimea oricăror doi subarbori este 0 sau 1.
[Link] Rezultate
81 Arborele este echilibrat
24700000
35806000

1. #include<fstream>
2. #include<iostream>
3. #include<cmath>
4. using namespace std;
5. int i,n,St[101],R,Dr[101],ok=1;
7. void citire()
8. {
9. ifstream f("[Link]");
10. f>>n>>R;
11. for(i=1;i<=n;i++) f>>St[i];
12. for(i=1;i<=n;i++) f>>Dr[i];
13. [Link]();
14. }
16. int h(int p, int k)
17. {
18. int a,b;
19. if((St[p]==0)&&(Dr[p]==0)) return k;
20. Else
21. {
22. a=h(St[p],k+1);
23. b=h(Dr[p],k+1);
24. if(abs(a-b)>1) ok=0;
25. if(a>b) return a;
26. else return b;
27. }
28. }
30. int main()
31. {
32. citire();
33. h(R,0);
34. if(ok==1)
35. cout<<"Arborele este echilibrat";
36. Else
37. cout<<"Arborele nu este echilibrat";
38. }

69
Capitolul 5. Considerații metodice

5.1 Tipologia lecţiei de informatică

Fiecare lecţie ocupă un anumit loc într-un sistem de lecţii ce reprezintă un capitol, o
temă, şi are o anumită individualitate dată de tipurile posibile sub care se poate realiza şi
totodată conferită de către profesor în urma proiectării şi aplicării dorite. Tipul de lecţie
reprezintă un model de concepere (proiectare) şi realizare a lecţiei, o categorie a lecţiei care
reprezintă o “unitate structurată cu valoarea orientativă”.
Tipul de lecţie este un model didactic sub forma unui ansamblu de elemente caracteristice
(momente sau etape) pe baza căruia se proiectează structura unei anumite lecţii. Structura
lecţiei este tot un model didactic care stabileşte numărul de etape didactice şi le ordonează
într-un mod coerent, corespunzător unui anumit tip de lecţie. Între tipologia şi structura
lecţiilor se manifestă interdependenţa şi condiţionarea reciprocă. În acest contex avem fie
tipuri cu o etapă predominantă, care urmăresc realizarea în principal a unui act didactic, fie un
tip de lecţie cu o structură complexă şi multiplă, care urmăreşte să realizeze toate actele şi
etapele didactice, însă în ponderi diferite – lecţiile mixte.
Tipul de lecţie poate fi privit ca o structură procesuală, reprezentativă pentru întreaga
categorie de lecţii. Pedagogia actuală susţine o tipologie a lecţiei simplă, flexibilă şi diversă
cu o reconsiderare a poziţiei valorice a diferitelor tipuri de lecţii, ca şi a ponderii lor în
activitatea didactică. Dintre avantajele tipologizării lecţiilor, a grupării acestora pe anumite
categorii şi subcategorii, precum şi încadrarea situaţiilor de învăţare şi a structurilor prosibile
într-o anumită categorie se pot menţiona:
 Permite organizarea riguroasă, ordonată şi diferenţiată a lecţiilor;
 Ajută la identificarea variantelor de lecţii, la etichetarea lor;
 Permite selectarea cu mai multă uşurinţă a strategiilor adecvate de predare;
 Reprezintă un instrument de lucru real în activitatea profesorului;
 Permite raportarea la structuri similare şi la găsirea soluţiilor de organizare.

5.2. Avantajele tipologizării

Fiecare lecţie ocupă un anumit loc într-un sistem de lecţii ce reprezintă un capitol, o
temă, şi are o anumită individualitate dată de tipurile posibile sub care se poate realiza şi
totodată conferită de către profesor în urma proiectării şi aplicării dorite. Cu ajutorul
tipologiei profesorul poate lua în considerare întraga variaţie a posibilităţilor de structurare a
lecţiilor.

70
Dintre avantajele tipologizării lecţiilor, a grupării acestora pe anumite categorii şi
subcategorii, precum şi încadrarea situaţiilor de învăţare şi a structurilor posibile într-o
anumită tipologie, se pot menţiona:
 Este necesară pentru că aceasta reprezintă un instrument de lucru real în activitatea
profesorului;
 Permite organizarea riguroasă, ordonată şi diferenţiată a lecţiilor;
 Ajută la identificarea variantelor de lecţii, la etichetarea lor;
 Permite selectarea cu uşurinţă a strategiilor adecvate de predare;
 Filtrează similarităţile şi diferenţele dintre lecţii, îndemnând la construcţii care
valorifică experienţe atestate deja.

5.3 Tipuri de lecţii specifice obiectului „Informatică”

Criteriile de clasificare pot fi diverse, lucru rezultat din necesitatea perfecţionării continue a
tehnicilor de elaborare şi realizare a lecţie.
Nicola I. consideră că în cadrul fiecărei lecţii se realizează multiple sarcini, dar există
una dominantă sau care constituie obiectivul ei principal, orientând şi concentrând în acelaşi
sens activitatea profesorului şi a elevilor (numită şi sarcina didactică fundamentală). Sarcinile
didactice fundamentale pot fi:
 Comunicarea de cunoştinţe;
 Formarea de priceperi şi deprinderi;
 Sistematizarea;
 Verificarea;
Fiecare sarcină didactică fundamentală presupune stabilirea riguroasă a obiectivelor
operaţionale care pot fi diverse în funcţie de multitudinea factorilor ce trebuie luaţi în
considerare:
 Obiectul de învăţământ;
 Particularităţile colectivului de elevi, de grup şi individuale;
 Strategiile didactice propuse şi în acelaşi timp viabile;
 Stilul de predare;
 Creativitatea profesorului;
Realizarea obiectivelor prin modalităţi diferite conduce la o infinitate de variante determinate
de factorii variabili ce intrevin în fiecare lecţie.

71
Clasificarea tipurilor şi variantelor de lecţii realizată după modelul lui [Link]:
Lecţia de comunicare şi însuşire de noi cunoştinţe. Variante:
Lecţii bazate pe învăţarea prin receptare a naraţiunii;
Lecţii bazate pe învăţarea prin receptare a descrierii;
Lecţii bazate pe învăţarea prin receptare a expunerii;
Lecţii bazate pe învăţarea prin receptare a explicaţiei
Lecţii bazate pe învăţarea prin receptare a textului din manual;
Lecţia de elaborare a cunoştinţelor şi dezvoltare a strategiilor cognitive. Variante:
Lecţii bazate pe învăţarea prin cercetare şi descoperire;
Lecţii bazate pe învăţarea prin observarea directă şi independentă sau dirijată;
Lecţii bazate pe învăţarea prin observarea nemijlocită de material prelucrat;
Lecţii bazate pe învăţarea prin explorarea experimentală a realităţii;
Lecţii bazate pe învăţarea prin studiul de caz;
Lecţii bazate pe învăţarea prin studiul (analiza) textului;
Lecţii bazate pe învăţarea prin problematizare;
Lecţii bazate pe învăţarea prin dezbatere euristică;
Lecţia de formare a priceperilor şi deprinderilor. Variante:
Lecţii bazate pe învăţarea prin exerciţii executorii;
Lecţii bazate pe învăţarea prin exerciţii creative;
Lecţii bazate pe învăţarea prin imitarea de modele;
Lecţii bazate pe învăţarea prin activităţi practice;
Lecţii bazate pe învăţarea prin exersare simulată;
Lecţia de consolidare şi sistematizare. Variante:
Lecţii bazate pe rezolvarea de exerciţii şi probleme;
Exerciţii de vorbire şi scriere;
Discuţii de sistematizare şi clasificare;
Discuţie de revizie sumară;
Aplicaţii practice;
Recapitulare;
Joc didactic;
Discuţie finală;
Lecţia de aplicaţii practice, de dezvoltare a funcţiilor de acţiune sau de [Link]
Lecţii bazate pe generalizări (transferuri);
Studiu (analiza) de caz;
Rezolvări de exerciţii şi probleme;

72
 Lucrări practice;
Lucrări experimentale;
Aplicaţii tehnice;
Exersare de simulatoare;
Lecţii cu caracter de joc;
Lecţii de caracterizare a personajelor literare;
Lecţia de [Link]:
Lecţii de verificare şi apreciere;
Lecţii de lucrări practice;
Lecţii de lucrări scrise;
Lecţii de analiză şi corectare a lucrărilor;
Lecţii de evaluare a exerciţiilor;
Lecţia de atitudine (motivaţie);
Lecţia mixtă; Tipul lecţiei mixte
Caracteristici: urmăreşte realizarea aproximativ în aceeaşi măsură a mai multor sarcini
didactice (comunicare, sistematizare, fixare, verificare), fiecăreia fiindu-i rezervată o verigă a
instruirii, sarcinile profesorului şi elevilor se situează pe acelaşi plan, succesiunea
evenimentelor este variabilă, volumul cunoştinţelor predate este mai redus.
Structură:
- Organizarea clasei pentru lecţie şi captarea atenţiei elevilor;
- Actualizarea elementelor învăţate anterior;
- Pregătirea elevilor pentru asimilarea noilor cunoştinţe;
- Comunicarea şi asimilarea noilor cunoştinţe;
- Fixarea cunoştinţelor predate (sistematizare, exerciţii aplicative, reluarea într-un alt
contex a esenţialului);
- Conexiune inversă – pe tot parcursul lecţiei;

5.4. Tehnologie didactică şi strategii didactice

Prin tehnologie didactică se înţelege proiectarea (obiectivelor, competenţelor,

conţinutului, strategiilor, metodelor, mijloacelor, formelor), organizarea, realizarea,
evaluarea si reglarea - pe baza rezultatelor evaluării – a unui sistem de instruire, folosind
datele de care dispune ştiinţa si tehnica actuală. Rezultă de aici că tehnologia didactică
include într-un tot unitar toate elementele procesului de învăţământ înlăturând anumite graniţe
artificiale dintre ele, insistând asupra interdependenţei dintre conţinut şi celelalte elemente,
cum ar fi organizarea relaţiilor profesor – elevi, metodele, procedeele, mijloacele folosite, etc.

73
 Aplicarea de către profesor în activitatea de predare a principiilor moderne pe care le
sugerează psihologia contemporană, constituie un aspect al tehnologiei didactice în aceeaşi
măsură cu folosirea maşinilor de învăţământ, a computerului şi a altor mijloace tehnice.
În cadrul tehnologiei didactice, un loc aparte, central, îl ocupă strategiile didactice.
Strategia didactică implică un ansamblu (metode si procedee) prin care se realizează
colaborarea dintre profesori şi elevi în vederea predării şi însuşirii unui anumit volum de
cunoştiinţe, formării unor priceperi şi deprinderi de muncă practică şi a unor capacităţi
intelectuale. Alegerea şi folosirea unei strategii se face în funcţie de obiectivele stabilite, de
conţinutul acestora, de nivelul de dezvoltare intelectuală a elevilor, de condiţiile concrete în
care se desfăşoară activitatea didactică. Deci, orice strategie didactică presupune doi
parametri:
 Programarea externă: se referă la modul în care este prelucrată, ordonată si prezentată
informaţia didactică. Prin intermediul ei se realizează reglarea externă a procesului de
învăţare. Ea imprimă un caracter organizat învăţării, orientând şi direcţionând acest proces în
condiţiile asigurării independenţei şi inţiativei celui ce învaţă.
 Programarea operatională internă: se referă la registrul componentelor psihice antrenate în
procesul de învăţare a informaţiilor. Ea facilitează autoreglarea internă prin valorificarea
experientei acumulate şi a potenţialului psihologic, propriu fiecărui elev.
Întrucât între cei doi parametri unul vizând activitatea de predare, iar celălalt
activitatea de învăţare, nu se stabileşte o relaţie univocă, datorită imposibilităţii racordării
depline a celor două programări calitativ deosebite şi factorilor întâmplători ce se interpun, ca
adoptarea conceptului de strategie didactică oferă posibilitatea surprinderii specificului
relaţiilor dintre aceşti parametri.
Conform celor de mai sus, o strategie didactică, în primul rand, urmăreste apariţia şi
stabilizarea unor relaţii optime între activitatea de predare şi cea de învăţare prin care se
urmăreşte declanşarea mecanismelor psihologice ale învăţării potrivit particularităţilor de
vârstă şi individuale ale elevilor şi a condiţiilor concrete în care are loc această învăţare. Orice
strategie didactică este eficientă numai în măsura în care, transmiţând o cantitate de
informaţie, reuşeşte să-i antreneze pe elevi în asimilarea ei activă si creatoare. Procesul de
învăţământ, ca proces de cunoaştere, este determinat de structura logică a conţinutului,
precum şi de particularităţile psihologice ale învăţării. Misiunea strategiei didactice este aceea
de a asigura adaptarea conţinutului la aceste particularităţi şi de a determina, totodată,
mişcarea interioară a acestora pe o traiectorie ascendentă.
În al doilea rând, orice strategie didactică acţionează într-un câmp de factori şi
posibilităţi, în consecinţă, finalitatea ei include un oarecare grad de probabilitate. Orice

74
strategie didactică are astfel un caracter statistic sau probabilistic. Ponderea si rolul factorilor
întâmplători diferă de la o strategie la alta.
În al treilea rând, orice strategie didactica, impune îmbinarea între activitatea
profesorului şi cea a elevului. Din acest punct de vedere rolul profesorului se poate deplasa
din situaţia în care este doar o sursă de informaţii, în situaţia în care conduce şi controlează
activitatea independentă a elevilor, în timp ce activitatea acestora se poate deplasa de la cea de
simpla reproducere la cea creatoare. Folosirea diverselor strategii impune un sens ascendent
acestei mişcări apropiind astfel procesul concret al asimilării, de modelul său ideal, învăţarea
independentă şi creatoare. Conlucrarea dintre profesor şi elevi conferă strategiei o dimensiune
psihosocială prin multitudinea şi diversitatea relaţiilor interpersonale ce se stabilesc între ei.
Orice strategie este, în acelaşi timp, rezultatul interactiunii mai multor procedee, este o
succesiune de operaţii urmărind multiple obiective didactice. De aceea, alegerea unei strategii
se face în funcţie de anumite criterii: conţinutul informaţional, particularităţile de vârstă,
situaţia concretă, etc. În final, se poate spune că strategia didacticăa nu se reduce la o simplă
tehnică de lucru, ea este, totodată, o manifestare şi o expresie a personalităţii profesorului.
Strategia include deci, într-un tot unitar tehnica de lucru şi concepţia pe care o adoptă în
procesul aplicării ei, profesorul. Dacă tehnica de lucru este rezultatul unor descoperiri
psihopedagogice în limitele demersului ştiinţific, ea impunându-se în mod obiectiv în virtutea
relaţiilor evidenţiate între elementele sale, aplicarea ei îmbracă nuanţe diferite în funcţie de
personalitatea celui care o manipulează într-o situaţie dată. Ca atare, orice strategie este
concomitent tehnica şi arta educatională. Privită în acest fel, ea devine componentă a “stilului
de predare”, propriu fiecărui profesor.
Deducem că strategiile didactice ocupă un loc central în cadrul tehnologiei didactice,
alegerea şi folosirea lor diferenţiată depinzând în mod hotărâtor de pregatirea şi personalitatea
profesorului. Orientându-ne după cele de mai sus, putem spune că în predarea-învăţarea
informaticii se folosesc următoarele strategii didactice: strategii de tip expozitiv–euristic,
strategii de tip algoritmizat si strategii de tip evaluativ – stimulativ, care se obiectivizează în
diverse metode, procedee şi forme de activitate cu elevii.

5.5. Strategii didactice de tip expozitiv-euristic

Specific pentru aceste strategii este faptul că activitatea de predare şi cea de învăţare
se desfăşoară pe fondul unor relaţii neunivoce cu un oarecare grad de incertitudine. În cadrul
lor, nu există concordanţă deplină între programarea activităţii de predare şi programarea
activităţii de învăţare, componentele primeia neavând o corespondenţă totală şi directă în
componentele celeilalte. De aici rezultă un anumit joc al imprevizibilului ale cărui limite

75
diferă în funcţie de cunoaşterea factorilor ce intervin. Elaborarea şi asimilarea adevărului se
realizează nuanţat de către fiecare elev, proces în care logicul interferă cu elemente logice, de
natură psihologică, individuală cum ar fi: cele afective, temperamentale, imaginative, etc.,
toate acestea punându-şi amprenta asupra rezultatului final al învăţării.
Referitor la rolul si ponderea activităţilor profesorului şi a elevului în cadrul acestor
strategii se constată oscilaţii destul de mari. În unele forme predomină activitatea
profesorului, în altele activitatea elevilor; în unele, profesorul reprezintă sursa principală de
cunoştinţe pe când, în altele, rolul său constă în a asigura şi coordona procesul de învăţare,
rezultatele fiind şi ele diferite de la o formă la alta: asigurarea asimilării de cunoştinţe şi
informaţii prin simpla memorare sau prin preluarea prin formarea doar a priceperilor şi
deprinderilor, sau dezvoltarea capacităţilor psihice. Se consideră că unele forme ale acestor
strategii sunt concentrate asupra activităţii profesorului (cele expozitive), iar altele asupra
activităţii elevilor (cele euristice). Privită în mod abstract diferenţierea apare ca fiind arbitrară,
deoarece chiar dacă este vorba de activitatea elevilor îndreptată în vederea descoperirii şi
asimilării cunoştiinţelor, ea este dirijată şi coordonată de profesor, operaţii care solicită cel
puţin tot atâta efort ca şi în cazul în care profesorul ar expune cunoştiinţele. Totuşi, una este să
dirijezi activitatea intelectuală prin procedee euristice, prin analiza alternativelor şi a
ipotezelor, prin căutări succesive, şi alta să foloseşti procedee standardizate gata elaborate.
Sensul expozitiv al acestor strategii subliniază faptul că unele informaţii sunt relatate de către
profesor, iar sensul euristic exprimă necesitatea de a-i ajuta si dirija pe elevi în cunoaşterea
adevărurilor ştiinţifice. Acest “ajutor” se exprimă prin sugerarea şi crearea unor situaţii care
oferă mai multe posibilităţi, alegerea soluţiei fiind rezultatul unui proces de analiză, ce se
desfăşoară pe plan mental. “Euristica nu oferă reţete pentru parcurgerea drumului spre
descoperire, ci caută căi în labirintul creaţiei pentru înţelegerea lui” ([Link]). Euristica nu
este nouă şi totusi, ea prezintă noul – condiţie a perfecţionării, a ridicării pe o treaptă
superioară. De la Socrate, care îşi conducea interlocutorul, prin dialog, spre descoperirea
adevărului, esenţa euristicii a rămas până azi aproape aceeaşi: i se cere elevului ca, prin efort
personal de căutare, valorificând cunoştiinţele anterioare, experienţa şi capacităţile sale
intelectuale, să dobândească cunoştiinţe, descoperindu-le independent, sub îndrumarea
profesorului.
Sub aspect formativ, folosirea strategiilor euristice în învăţarea informaticii are o
importanţă deosebită, acestea stimulând capacităţile intelectuale ale elevilor, menţinând şi
dezvoltând interesul lor cognitiv formând astfel motivaţia pentru învăţare. Utilizând strategii
euristice, elevii – în prezenţa şi sub îndrumarea profesorului – caută, încearcă soluţii de
rezolvare proprii pentru diferite situaţii de învăţare, prin insusirea unor reguli care-i conduc

76
spre soluţiile respective, încercând să reelaboreze cunoştiinţele, să refacă, în linii mai mari,
drumul parcurs de ştiinţă pentru aflarea lor. Elevii îşi însuşesc modalităţi de studiere a
fenomenelor ştiinţifice ca procese şi nu ca produse, devin participanţi activi, creatori şi
responsabili pentru dezvoltarea ştiinţei în interesul societăţii şi al său, al progresului în
general, nu ca simpli beneficiari scutiţi de eforturi. Ambele sensuri (cel expozitiv şi cel
euristic) sunt necesare şi indispensabile însă, deoarece nu totul poate fi asimilat prin căutări
proprii şi de multe ori nu este nevoie de aşa ceva, după cum unele din obiectivele procesului
de învăţământ, îndeosebi cele de ordin formativ, nu pot fi realizate prin simpla memorare a
cunoştiinţelor gata prelucrate. Important este de a decide unde şi când să apelam la o variantă
sau alta. De fapt în activitatea practica ele se îmbină, profesorul fiind acela care poate decide
în funcţie de situaţia concretă, dacă sunt necesare căutările sau tatonările din partea elevilor
sau se poate expune sau demonstra, reducându-se riscurile la mimimum.
Toate aceste particularităţi au fost teoretizate prin delimitarea a două “stiluri”
fundamentale de predare, cel “dominat de profesor” şi cel “axat pe grupuri”. În cadrul
primului dintre acestea, stilul profesorului realizează activitatea de predare prin expunerea
cunoştiinţelor, preocuparea sa concentrându-se asupra prezentării lor într-o manieră cât mai
sistematică, recurgând în mai mică măsură la conexiunea inversă pentru a constata efectul
expunerii sale. Specific pentru stilul axat pe grup este accentul pe activitatea elevilor, pe
participarea lor la descoperirea cel putin a unei părţi din cunoştinţele ce urmează a fi învăţate.
Dialogul devine indispensabil, ca modalitate fundamentală, de lucru, nu numai între profesor
şi elev ci şi în interiorul grupului, între membrii săi. Opţiunea pentru unul sau altul dintre
aceste stiluri depinde de conţinutul cunoştiinţelor ce urmează a fi predate şi de pregătirea şi
personalitatea profesorului.

5.6. Metode si procedee explozitiv – euristice în predarea informaticii

Termenul de “metodă” derivă etimologic din două cuvinte grecesti (odos = cale;
metha = spre, catre). În didactică, metodă se referă la calea ce se urmează, drumul ce conduce
la atingerea obiectivelor educaţionale. Metodele de instruire se aseamănă cu cele ştiinţifice de
cercetare în sensul că ambele sunt căi ce conduc la conturarea unor fapte, legităţi, descrieri,
interpretări cât mai aproape de realitate. Deosebirea fundamentală este aceea că metodele
didactice – de regula – prezintă, vehiculează cunoaşterea sedimentată la un moment dat.
Metoda didactică este deci, o cale eficientă de organizare si desfăşurare a predării – învăţării
şi se corelează cu celelalte componente ale instruirii. Cel mai adesea metodele nu se
manifestă izolat şi – mai ales – în stare pură, ci sub forma unor variante şi circumstanţieri
diferite. Ele apar şi se concretizează în variante metodologice compozite, prin difuzarea

77
permanentă a unor trăsături şi articularea a două sau mai multe metode. Exista însă o serie de
metode “primare”, de “ideal – tipuri” metodologice din care derivă combinaţii inedite. Dintre
acestea sunt metodele prin care se obiectivizează strategiile euristice în predarea – învăţarea
informaticii.
1. Lucrările practice de laborator constituie o formă larg utilizaăa în practica
şcolară, în predarea informaticii. Acestea se realizează în variante şi cu scopuri didactice
diferite. Astfel, ele pot folosi fie ca un punct de plecare în însuşirea cunoştinţelor, fie ca mod
de verificare şi consolidare a acestora sau de aplicare a lor. În toate aceste situaţii ele rămân o
forma de muncă independentă a elevilor şi, în acelaşi timp, o cale de dezvoltare a interesului
pentru informatica ştiinţa şi pentru latura aplicativă a acesteia.
Din punctul de vedere al modului de realizare, formele metodice ale lucrărilor de
laborator s-ar putea grupa astfel :
lucrări de laborator demonstrative – efectuate de profesor, pe care elevii le urmăresc, fiind
antrenaţi să constate;
lucrări de laborator executate frontal, de întreaga clasă – care sunt mai eficiente antrenând
întregul colectiv de elevi. Prin lucrări experimentale frontale de laborator, elevii sunt puşi în
aceleaşi condiţii de muncă efectuând simultan aceleaşi lucrări; ei pot să compare astfel
rezultatele obţinute, să împrumute unii de la alţii cele mai bune procedee de lucru, să se
stimuleze reciproc. Ele permit profesorului să compare şi să evalueze mai bine activitatea
elevilor, ca şi rezultatele obţinute – folosind aceleaşi criterii.
Se disting în practica şcolară, forma lucrărilor experimentale pe grupe ce se pot desfăşura, la
rândul lor, în două feluri: toate grupele efectuând aceeaşi tema sau fiecărei grupe fiindu-i
repartizate sarcini diferite şi, individuale în care caz fiecare elev, folosind anumite materiale,
pe baza unui sistem de indicaţii concrete primite în scris prin fişe de lucru, o sarcina concretă,
diferită de a celorlalţi elevi.
Dacă se tine seama de finalitatea pedagogică, se pot delimita alte trei variante de lucrări
experimentale de laborator:
aplicative ce au ca scop punerea elevilor în situaţia de a verifica experimental posibilităţile de
aplicare în practică a cunoştinţelor teoretice Ele se efectuează sub îndrumarea profesorului
printr-un protocol întocmit de acesta şi se folosesc mai ales în cazul lecţiilor recapitulative;
lucrări experimentale destinate formării abilităţilor şi deprinderilor practice specifice;
lucrări experimentale cu caracter de cercetare. În acest caz elevii sunt puşi în situaţia de a
concepe pornind de la o ipoteză şi continuând cu culegerea datelor, prelucrarea lor şi
desprinderea concluziilor.

78
 2. Demonstraţia constă în prezentarea sistematică, schematică şi organizatorică a
unor obiecte, procese, fenomene, etc., sau producerea în faţa elevilor a unor experimente,
fenomene, etc., în scopul asimilării unor informaţii despre ele şi a familiarizării acestora cu
efectuarea corectă a activităţilor respective.
Folosirea metodei demonstraţiei în predarea – învăţarea informaticii impune respectarea unor
cerinte metodice ce s-ar putea grupa în trei categorii si anume:
pregătirea pentru demonstraţie;
participarea activă a elevilor pe parcursul demontraţiei;
prelucrarea datelor obţinute prin folosirea acestei metode.
În toate situaţiile de învăţare este necesar ca, înaintea demonstraţiei, elevii să fie
sensibilizaţi asupra a ceea ce urmează să cunoască sau să efectueze, pentru a le stimula
curiozitatea, interesul, tendinţa de cunoaştere. În acest sens este necesar să se reactualizeze o
serie de cunoştinţe supuse observării, se precizează cu claritate scopul urmărit; se indică o
serie de repere, care vor orienta percepţia elevilor, se formulează situaţii problemă privind
interpretarea rezultatelor obţinute prin experimentele efectuate. Este necesar ca elevii să
lucreze efectiv pentru formarea unor priceperi şi deprinderi practice (de exemplu în cazul
demonstrării acţiunilor pe care aceştia trebuie să şi le însuşească); prin acestea se realizează
stimularea participării active a elevilor în timpul demonstratiei, fapt ce presupune crearea de
condiţii pentru ca aceştia să perceapa cât mai complex demonstraţia.
3. Modelarea este metoda de studiere a realităţii cu ajutorul modelelor (materiale sau
ideale) ca analoage ale obiectelor, fenomenelor şi proceselor din realitate şi utilizarea lor
efectivă în activitatea de predare – învăţare, ca mijloace de instruire. Modelul reprezintă un
sistem material sau teoretic (logico – matematic) care reproduce şi explică la o altă scară şi
într-o altă formă originalul – cu care modelul prezintă o anumităa analogie – parţial sau în
esenţă, cu scopul de a-i fi descoperite noi proprietăţi. Modelarea, concepută ca proces de
cunoaştere, implică mai multe tipuri de modele, respectiv de modelare. Astfel, se folosesc
modelarea similară şi modelarea prin analogie.
Modelarea similară se realizează prin intermediul modelelor materiale care reproduc
sistemul original, pentru a-l face accesibil studiului. Din aceasta categorie fac parte, de
exemplu, machetele unor dispozitive, aparate, instalatii, etc. Acestea, la rândul lor, pot fi
statice sau dinamice. Din aceeaşi categorie a modelelor similare mai fac parte şi figurinele cu
ajutorul cărora pot fi modelate diferite structuri şi procese. O altă categorie de modele îl
reprezintă modelele figurative care reproduc obiectul, fenomenul sau procesul original cu
ajutorul imaginii.

79
 Modelarea prin analogie, se bazează pe asemănarea dintre model şi original. Dacă la
modelul similar “identitatea” cu originalul îi este caracteristică, modelului prin analogie îi este
caracteristică corespondenţa dintre elementele esenţiale. Dacă originalul are proprietăţile
A,B,C şi modelul construit are proprietăţile A1,B1,C1, iar din acestea descoperim
proprietăţile d si e, atunci şi originalul are proprietăţile d şi e. Modelarea prin analogie se
obiectivizează prin modele simbolice teoretice sau logico – matematice (abstracte),
caracterizate prin absenţa formei de concretizare substanţiala (fizică). Ele exteriorizează
esenţa fenomenelor, proceselor pe care le modelează sub formă de simboluri, formule, ecuaţii
matematice sau suite de raţionamente care exprimă raporturi structurale sau funcţionale între
componentele sistemului modelat. Modelele, indiferent de tipul lor, joacă rolul unor mijloace
de sprinjin în gândirea elevilor, sunt forme prin care fenomenele pot fi “vizualizate”.
Utilizarea metodei modelării în predarea – învăţarea informaticii implică înarmarea elevilor
cu ideea că procesele, fenomenele pot fi modelate şi studiate pentru a le descoperi noi
proprietăţi. Solicitarea elevilor de a reconstrui anumite proprietăţi ale originalului pe model –
proprietăţi cunoscute în ştiinţă, dar necunoscute lor; reconstruirea sau redescoperirea unor
modele care sunt cunoscute în ştiinţă determinăa activizarea elevilor, stimulează funcţiile
gândirii.
[Link]ţia, ca metodă didactică, este un dialog ce se desfăşoară între profesor şi
elevi, prin care se stimulează şi se dirijează activitatea de învăţare a elevilor. În acord cu
obiectivele instructiv – educative urmărite în învăţarea informaticii, conversaţia îndeplineşte
multiple funcţii:
conversatia euristica - de descoperire a noilor informaţii şi date (dobandire de cunoştinţe);
conversatia de consolidare si aprofundare - de consolidare si fixare;
conversatia de verificare, control si apreciere - de verificare si apreciere a performanţelor
învăţării;
Cea mai utilizată dintre formele menţionate este conversaţia euristică, care se bazează pe
o înlănţuire logică de întrebări formulate de profesor şi care îi determină pe elevi la căutări, la
stabilirea unor relaţii cauzale, la descoperirea elementelor caracteristice. Prin întrebări clar
formulate elevii sunt ajutaţi să facă analogii, să ajungă la formularea unor concluzii, să
propună soluţii variate pentru rezolvarea unor probleme cu conţinut teoretic şi practic privind
temele studiate.
O variantă a acestei metode este asaltul de idei (brainstorming). Caracteristica
principală a acestei metode constă în faptul ca ea realizează separarea etapei de elaborare a
soluţiei unei probleme (faza producţiei divergente) de etapa evaluării soluţiilor propuse (faza
de evaluare critică şi validare a soluţiilor considerate corecte şi originale). Rezolvarea unei

80
probleme prin brainstorming (căutarea şi găsirea celei mai adecvate soluţii) constă într-o
antrenare susţinută a subiecţilor participanţi la discuţia în grup, ca să enunţe cât mai multe
idei, fară a fi preocupaţi de evaluarera critică a acestora. Analiza, selecţia şi elucidarea
calităţii soluţiilor elaborate se realizează într-o altă etapă de către membrii colectivului care au
participat la emiterea lor, dirijaţi de către conducătorul grupului .
Sistematizarea selectivă, aprecierea critică a soluţiilor grupului, se face de profesor în
colaborare cu elevii, la intervale diferite de la câteva ore, la câteva zile, în funcţie de
complexitatea problemei abordate; de aici şi metoda “evaluării amânate“. În cele mai multe
situaţii, în practica şcolară, în cele două faze ale metodei asaltului de idei (emiterea ideilor şi
analiza critică a acestora) se succed în decursul aceleiaşi activităţi.
Folosirea acestei metode - “de inventariere“, discuţie şi argumentare a oportunităţii sau a
caracterului mai eficient al unor soluţii, înlesneşte confruntarea dintre elevi la nivelul clasei,
lasă câmp larg de manifestare activă a independenţei în gândire, realizează cadrul unei
învăţări creatoare, sporeşte randamentul în învăţare, facilitează o buna conexiune inversă .
5. Problematizarea sau învăţarea prin rezolvări de situaţii problemă. Esenţa
problematizării constă în crearea situaţiilor problemă şi dirijarea gândirii elevilor în activitatea
de rezolvare a acestora. Folosirea acestei metode antrenează şi oferă elevilor posibilitatea să
surprinda diferite relaţii între obiectele şi fenomenele naturii, între cunoştinţele anterioare şi
noile cunoştinţe pe care ei înşişi, sub îndrumarea profesorului, le elaborează. În orice situaţie
problema nu este altceva decât o “schemă anticipatoare“ sau un “plan de acţiune“ care
presupune anumite repere, mai mult sau mai puţin detaliate, privitoare la operaţiile şi
activitatea ce urmează a fi efectuată de elevi .
Se pot delimita, în cadrul acestei metode, trei momente succesive :
Un moment pregătitor sau declanşator - constă în crearea situaţiei problemă. Ţinând cont de
modul în care apare şi de modul în care se rezolvă putem distinge următoarele cazuri :
cazul în care profesorul crează în mod intenţionat o situaţie – problema, atragând atenţia
elevilor asupra ei, pentru ca în final, explicaţiile sale să conducă la indicarea soluţiei;
cazul în care profesorul creează situaţia problemă, rezolvarea având loc în mod independent
(de catre elevi);
cazul în care elevii înşişi îşi creează situaţia-problemă o rezolvă independent, profesorul fiind
acela care sugerează şi supraveghează acest proces.
Un moment tensional – se exprimă prin intensitatea contradicţiilor dintre ceea ce se dă spre
rezolvare (se solicită) şi cunoştinţele anterioare ale elevilor. Tensiunea este dependentă şi de
metoda solicitată în vederea rezolvării sarcinii;

81
Un moment rezolutiv – urmăreşte nu numai deprinderea soluşiei ci şi confirmarea ei prin
întărire pozitivă sau negativă de către profesor .
Din înlănţuirea celor trei momente rezultă un model pentru activitatea de învăţare, model care
se încheie cu obţinerea unui rezultat. Evident, nu toate cunoştinţele pot fi asimilate după acest
model, metoda problematizării diferind în funcţie de particularităţile de vârsta, de capacităţile
individuale ale elevilor, de structura colectivului de elevi .
6. Munca cu manualul este o metodă de tip euristic ce foloseşte o tehnică tradiţională
de învăţare după un text scris, dar într-un stil nou, adaptat actualei tehnologii didactice
moderne. Această metodă cuprinde un ansamblu de acţiuni prin care profesorul urmăreşte
formarea capacităţii elevului de a folosi conştient, corect şi în mod eficient, o sursă de
informare scrisă. Manualul şcolar, privit ca mijloc de învăţământ, este destinat elevului şi
constituie principalul său instrument de lucru. Pentru obiectul informatică manualul este de
fapt o carte de lucru care, prin conţinutul său – informaţii, întrebări, demonstraţii, exercitii,
probleme, jocuri didactice, sarcini de lucru pentru activitatile de laborator – îndeplineşte un
triplu rol: de instrument de învăţare a noilor cunoştinţe, de instrument de autocontrol, şi de
ghid sau îndrumator pentru experimente şi lucrări practice. Pentru profesor, manualul şcolar,
reprezintă un ghid asupra volumului de cunoştinţe şi asupra modului de organizare a activităţii
în clasă.
7. Instruirea asistată de calculator numită şi “inovaţia tehnologică cea mai importantă
a pedagogiei moderne”, instruirea asistată de calculator – este un rezultat al introducerii
treptate a informatizării în învăţământ. Calculatorul poate fi utilizat în procesul de predare –
învăţare de către profesor şi elev în scopul intermedierii activităţii de predare interumană ce
are loc între cei doi poli educaţionali: profesor şi elevi. Este o metodă de instruire, în care
elevul învaţă în ritm propriu, materialul educaţional este structurat în secvenţe mici de studiu,
urmate de chestionare, elevul şi profesorul putând să observe imediat evoluţia procesului de
instruire. Folosirea calculatorului în procesul de învăţământ se dovedeşte a fi o necesitate în
condiţiile dezvoltării în ritm accelerat a tehnologiei informaţiei. Pentru noile generaţii de elevi
şi studenţi, a devenit o cerinţă conceptul de asistare a procesului de predare – învăţare de către
calculator, în condiţiile avalanşei de informaţii multimedia.
Metoda instruirii asistate de calculator dezvoltă propriile sale principii, valabile la nivel
strategic în orice variantă de organizare a învătării:
Principiul paşilor mici – se referă la divizarea materiei în unităţi de conţinut, care asigură
elevului şansa reuşitei şi a continuităţii în activitatea de predare – învăţare – evaluare;
Principiul comportamentului activ – vizează dirijarea efortului elevului în direcţia
selecţionării, înţelegerii şi aplicării informaţiei necesare pentru elaborarea unui răspuns corect;

82
Principiul evaluării imediate a răspunsului – înseamnă întărirea pozitivă sau negativă a
comportamentului elevului în funcţie de reuşita sau nereuşita în îndeplinirea sarcinii de
învăţare corespunzătoare fiecărui “ pas”;
Această metodă depinde nu numai de calitatea calculatorului, ci şi de condiţia pedagogică
asumată la nivelul programelor elaborate special pentru :
Conştientizarea valorii interactive a informaţiei alese ;
Sistematizarea rapidă a unui volum mare de informaţii ;
Difuzarea eficientă a unor informaţii esenţiale solicitate de un număr ridicat de participanţi la
actul didactic ;
Individualizarea reală şi completă a actului învăţării, adaptabilă la ritmul fiecărui elev
prin ,,asistenţă pedagogică imediată, realizată/realizabilă de/prin calculator ;
Stimularea capacităţii profesorului de a deveni un adevărat educator, ghid şi animator,
evaluator şi îndeosebi formator preocupat de cultivarea “atitudinilor superioare” (Văideanu,
1988). Valoarea instruirii asistate de calculator constă în faptul că, prin organizarea procesului
de învăţare, principiile didactice (al însuşirii conştiente şi active, al sistematizării şi
continuităţii, al accesibilităţii şi însuşirii temeinice a cunoştinţelor) acţionează concomitent şi
în fiecare moment al activităţii elevului cu programa, stimulînd formarea şi dezvoltarea
capacităţilor intelectuale, precum şi deprinderi de muncă independentă. De asemenea, se
reduc în mod simţitor timpul necesar însuşirii cunoştinţelor şi redundanţa inerentă procesului
de transmisie a informaţiilor de la profesor sau de la manual la elev.
Integrarea noilor tehnologii – dependente de capacitatea de asistenţă pedagogică a
calculatorului – în structura de acţiune specifică metodei didactice, conferă activităţii elevului
un caracter reactiv şi proactiv, în raport cu informaţia vehiculată, cu timpul real de învăţare,
cu valoarea formativă a cunoştinţelor dobândite.

5.7. Obiectivele didactice ( generalităţi )

Obiectivele-cadru au un grad ridicat de generalitate şi complexitate şi se referă la
formarea unor capacităţi şi aptitudini specifice disciplinei şi sunt urmărite pe o întreagă
perioadă de şcolarizare. Obiectivele de referinţă specifică rezultatele aşteptate ale
învăţării şi urmăresc în special progresul realizat în acumularea de cunoştinţe şi în
formarea deprinderilor, de regulă pe perioada unui an de studiu.
Transformările care au loc in societate, dezvoltarea şi răspândirea informaticii, pătrunderea
rapidă în viaţa economică, socială şi în învăţământ a celor mai noi realizări in domeniul
hardware-ului şi software-ului impun o diversificare a pregătirii elevilor de liceu în acest
domeniu, învăţământul preuniversitar trebuie să asigure în primul rând dobândirea unor

83
cunoştinţe de informatică la nivel de cultură generală. Totuşi, cunoştinţele de tehnologia
informaţiei, utilizarea calculatoarelor în rezolvarea problemelor profesionale în diversele
domenii ale vieţii economice, reprezintă o cerinţă a integrării în diferitele domenii
profesionale ale momentului. Din acest motiv, este posibil să admitem şi
introducerea/predarea în liceu (la un nivel corespunzător) a noilor elemente de programare
mai complexă (C + + , WEB, reţele de calculatoare , Oracle etc.). Astfel, în funcţie de filieră
şi specializare, elevii trebuie să dobândească, până la un anumit nivel de aprofundare, un
sistem de cunoştinţe relativ la prelucrarea informaţiei cu ajutorul calculatoarelor personale.
Pentru realizarea acestui obiectiv pedagogic considerăm că este necesar ca elevul:
i) Să dobândească cunoştinţele necesare înţelegerii principalelor aspecte legate de
noţiunea de informaţie (culegere, prelucrare, stocare, transmitere).
ii) Să-şi formeze şi modeleze modul de gândire şi abordare a problemelor. Asemenea
tuturor ramurilor ştiinţei, informatica dezvoltă gândirea, având un rol esenţial în procesul de
învăţare, in formarea caracterului şi a personalităţii, în plus, informatica formează şi dezvoltă o
manieră sistemică de abordare, provoacă o analiză progresivă a detaliilor, o rezolvare în context
general a problemelor particulare. Aceasta este gândirea algoritmică, practică, diferită cumva
de gândirea teoretică şi abstractă. Această manieră de abordare a problemelor leagă
cunoştinţele de programare de contextul bazei de date pe care o prelucrează şi de cel al
soluţiilor pe care le va obţine. Formarea unei gândiri algoritmice, analitice şi sistematice şi a
unui mod de lucru ordonat are consecinţe deosebite în evoluţia viitoare a elevului şi este un
obiectiv esenţial al studiului informaticii în învăţământul preuniversitar.
iii) Să-şi formeze şi să-şi dezvolte deprinderi de a munci individual şi în echipă. Cu
riscul de a ne repeta, trebuie să subliniem că, chiar dacă munca în informatică este aparent
individuală, activitatea colectivă este esenţială în conceperea şi realizarea bazelor de date mari
şi a produselor software de dimensiuni medii sau mari. Se impune formarea la elevi a acelor
deprinderi elementare de lucru cu calculatorul care oferă şansa unei învăţări în ritmul propriu al
fiecăruia, dar şi posibilitatea asimilării lucrului în echipă. Se realizează astfel asumarea
responsabilităţii, cu privire la finalizarea propriei munci şi asigurarea condiţiilor de finalizare a
activităţii celorlalţi membri ai colectivului. Conducerea raţională a activităţii de proiectare şi
programare, dezvoltarea intuiţiei determină elevul să capete încredere în propriile-i forţe.
iv) Să capete deprinderi care-1 vor ajuta să devină un utilizator profesionist, adică să
dobândească cunoştinţele necesare exploatării resurselor hardware şi software puse la dispoziţie
de tehnologia informatică actuală. Pentru aceasta, elevul trebuie să-şi formeze o cultură
generală informatică, ce presupune identificarea şi înţelegerea principalelor componente ale
calculatorului, funcţionarea reţelelor de calculatoare, dobândirea deprinderilor necesare

84
utilizării noilor produse software. Punctăm din nou că pentru atingerea acestui ultim obiectiv-
cadru trebuie urmărite, în mod diferenţiat, măcar următoarele obiective de referinţă :
• Cunoaşterea până la un anumit nivel de detaliu a sistemelor de
operare/mediilor de programare cel mai des folosite (Windows, Unix, Linux etc.).
• Cunoaşterea structurii şi arhitecturii sistemelor de calcul şi a noţiunilor elemen-
tare de hard, care să le permită să-şi facă o impresie precisă despre caracteristicile tehnice ale
oricărui calculator.
• Cunoaşterea unui limbaj de programare de nivel înalt (Pascal, C, Prolog, Java
etc.) şi a noţiunilor elementare despre limbajele de asamblare (măcar în liceele de specialitate).
• Cunoaşterea tehnicilor de proiectare a produselor program cu caracter
ştiinţific, a metodelor de elaborare a algoritmilor, a algoritmilor fundamentali, a tehnicilor de
optimizare a algoritmilor (elevii ar trebui să aibă şi o bună capacitate de apreciere a
complexităţii algoritmilor).
• Cunoaşterea unor noţiuni privind analiza şi proiectarea aplicaţiilor de
gestiune economică şi cunoaşterea unui sistem de gestiune a bazelor de date, procesoare de
calcul tabular.
• Cunoaşterea celor mai uzitate programe utilitare, editoare de texte şi editoare
grafice, pachete de programe de compresie (arhivare), programe antivirus, noţiuni primare de
inginerie de sistem etc.
• Cunoaşterea principalelor modalităţi de exploatare ale facilităţilor oferite de
reţele (locale şi interconectate), servicii Internet, documente Html, facilităţi multimedia etc.
v) Formarea unei conduite şi a unei moralităţi profesionale constituie un obiectiv
esenţial, în informatică, respectarea strictă a eticii profesionale este o necesitate impusă de
respectarea legii copyright-ului. Elevii trebuie să conştientizeze impactul social al dezvoltării
informaticii, care poate chiar să modifice societatea, de aici rezultând necesitatea înţelegerii
rolului pe care ea îl are în schimbările din viaţa socială, economică, a aspectelor etice care
derivă din aceste schimbări, a avantajelor şi riscurilor impuse de utilizarea calculatoarelor. Elevii
trebuie să cunoască prevederile legale cu privire la dreptul de autor, confidenţialitatea
informaţiilor, protecţia bazelor de date, efectele dezvăluirii informaţiei sau distrugerii ei prin
spargeri de parole de protecţie, virusare, transfer neautorizat etc..Programa şcolară determină
conţinutul învăţării, dar acest conţinut este prelucrat după două categorii de obiective:
- informative (ce va şti elevul?);
- formative (ce va putea face elevul?).

85
 5.7.1. Precizarea obiectivelor
Succesul oricărei activităţi didactice este condiţionat de claritatea şi ordonarea obiectivelor
pe care aceasta le urmăreşte. Mai mult decât în oricare alt domeniu, procesului de învăţământ
informatic îi este caracteristică intenţionalitatea, orientarea către realizarea unor obiective, spre
producerea unor schimbări şi transformări care să poată fi controlate şi dirijate, în acest spirit,
cea mai importantă condiţie pentru reuşita predării informaticii este structurarea, conştientizarea
şi ierarhizarea unor obiective generale şi specifice, adaptate particularităţilor de vârstă ale
elevilor, conţinutului cunoştinţelor şi pregătirii lor ştiinţifice şi metodice. Un obiectiv didactic
este o descriere a unui ansamblu de comportamente şi performante de care elevul trebuie să se
arate capabil.
Obiectivele generale ale predării informaticii au anumite determinări care trebuie să
pună în evidentă:
- importanţa informaticii în lumea contemporană, în ştiinţă, în tehnică sau
economie ;
- necesitatea învăţământului de informatică şi rolul acestuia în formarea culturii
generale şi nu numai;
- necesitatea dezvoltării capacităţii intelectuale şi a gândirii algoritmice;
- necesitatea formării elevului pentru activităţile viitoare, ca utilizator de
calculator, la diferite niveluri.
Fixarea obiectivelor generale ale informaticii trebuie să răspundă cel puţin la următoarele două
întrebări:
- De ce se predă informatica în şcoală ?
- Ce se urmăreşte prin includerea ei în planul de învăţământ ?
Obiectivele predării ştiinţelor informatice în şcoală includ cu siguranţă:
- trezirea interesului pentru studiul acestora;
- formarea priceperilor şi deprinderilor de bază în utilizarea şi exploatarea
calculatoarelor;
- stimularea creativităţii;
- integrarea utilizării informaticii în modul de gândire şi de viaţă al elevului.
În afara obiectivelor sale generale, informatica participă - prin mijloace ce-i sunt proprii - la
modelarea personalităţii, nu numai sub aspect intelectual, ci şi sub aspect estetic şi moral
(estetic: programarea este o artă; moral: activitatea în domeniul informaticii nu se poate

George D. Birkhoff(1884-1944), matematician şi estetician amarican rămâne în istoria esteticii informaţionale
cu teoria sa asupra percepţiei estetice şi a receptării operei de artă, fundamrntată pe matematică şi psihologia
experimentală. Câteva din operele sale sunt: „Quelques éléments mathématiques de l’art“, 1929; „A
mathematical theory of aesthetics”, 1932; „Aesthetics Measure”, 1933. Mai târziu M. Bense, H. Frank, R.
Gunzenhäuser îi preiau şi dezvoltă ideile.

86
desfăşura în afara unei etici profesionale sănătoase, dacă ne gândim doar la pericolul hacker-
ilor şi la relaţia defectuoasă a acestora cu cyber-space-ul virtual de pe Internet). Dintre
obiectivele specifice, putem desprinde anumite obiective derivate care pot fi la rândul lor
structurate pe trei niveluri:
- Nivelul obiectivului (elev)
- Nivelul subiectului (profesor)
- Nivelul acţiunii comune.
La nivelul elevului, obiectivele derivate sunt:
- Integrarea şi asimilarea cunoştinţelor cuprinse în programă
- Memorarea activă a acestor cunoştinţe
- Dezvoltarea judecăţii deductive şi inductive
- Conştientizarea procedeelor ce stau la baza raţionamentelor
- Formarea capacităţii de analiză şi sinteză
- Formarea capacităţii de structurare şi planificare
- Formarea capacităţii de abordare a unei probleme complexe.
La nivelul profesorului, obiectivele derivate se referă la capacitatea de apreciere a
fenomenelor şi rezultatelor. Nivelul acţiunii are în vedere asimilarea de către elev a noţiunilor şi
aplicarea lor în practică. Pe baza acestor consideraţii, se pot elabora şi delimita obiectivele
operaţionale ale fiecărui capitol, lecţie ş.a.m.d., cu detalierea fiecărei componente. Formularea
obiectivelor operaţionale trebuie făcută în termeni comportamentali cât mai precişi, care să
excludă formulări vagi. Formularea obiectivelor operaţionale presupune :
- identificarea performanţei finale care trebuie realizată;
- descrierea în detaliu a condiţiei esenţiale în care se poate produce
comportamentul respectiv;
- precizarea nivelului de performanţă la care trebuie să se ajungă pentru a fi
acceptată ca atare.
În acelaşi timp, trebuie să se cunoască:
- Cine va dirija modelarea unui comportament dorit ?
- Ce comportament observabil va dovedi că obiectivul a fost atins?
- Care va fi produsul (performanţa) acestui comportament?
- În ce condiţii trebuie să aibă loc comportamentul?
5.7.2. Clasificarea obiectivelor
În realitate, există două mari categorii de obiective ce trebuie avute în vedere în momentul
proiectării unei lecţii:
- Obiective sub raport stadial

87
 - Obiective sub raport psiho-pedagogic.
Obiective stadiale:
Obiective fundamentale (finale) - definesc elementele şi sarcinile rezultate din delimitarea
scopului final al educaţiei, cum ar fi cele legate de formarea unei personalităţi puternice,
complexe, cu o mare dispoziţie spre iniţiativă şi creativitate. Avem în vedere :
- formarea capacităţii de asimilare a cunoştinţelor de către elevi;
- formarea capacităţii de transfer a cunoştinţelor şi a experienţei deja
dobândite la rezolvarea unor sarcini necunoscute, apărute pe parcursul derulării procesului
didactic;
- formarea limbajului ştiinţific de profil;
- formarea unei atitudini ştiinţifice; trebuie creat un respect al elevului pentru
ştiinţă şi importanta acesteia în evoluţia sa ulterioară; elevul trebuie să înţeleagă că procesul
de cunoaştere nu se încheie într-o perioadă determinată de timp, că, pentru a fi eficient,
procesul de cercetare trebuie să prelucreze orice informaţie în mod critic, abţinându-se de
la a face afirmaţii categorice/definitive.
Obiective intermediare - sunt formulate în planul-cadru al procesului de învăţământ (privit
ca un sistem complex şi într-o permanentă evoluţie). În primul rând, se urmăreşte
dobândirea unei culturi generale de bază (în învăţământul preuniversitar), a unei culturi de
specialitate (în învăţământul superior) sau chiar a unei meserii (şcoli de profil).
Obiective secvenţiale - reprezintă obiectivele specializate, orientate spre anumite laturi ale
procesului de educaţie: intelectuală, tehnologică, profesională, morală, estetică, fizică etc.
Obiective operaţionale - privesc îndeplinirea concretă a unor activităţi curente, cum ar fi
cele legate de predarea unei lecţii sau de exemplificarea unor teme de laborator.
Evaluarea este posibilă numai în cazul în care formularea obiectivelor a fost făcută în
termeni comportamentali precişi, care evidenţiază performanţa aşteptată de la elevi. Este de
altfel necesar să organizăm acţiuni care să ne permită să constatăm realizarea acestei
performanţe şi să nu scăpăm din vedere efortul depus pentru obţinerea lor. Evaluarea
trebuie făcută după criterii absolut obiective. Fixarea unui obiectiv şi a unui principiu (ce se
face şi ce se obţine) este decisivă pentru construirea unui plan de lecţie. Aceasta este baza
construcţiei planului de lecţie şi a prezentării (alegerea metodelor şi materialelor didactice
necesare).

Obiective psiho-pedagogice
Sunt obiectivele didactice necesare formării de capacităţi intelectuale (teoretice, practice)
şi/sau afective. Şi acestea pot fi clasificate pe mai multe categorii:

88
Obiective cognitive/de cunoaştere. Prin acestea se urmăreşte formarea/dezvoltarea
următoarelor capacităţi intelectuale:
- cunoaşterea: posibilitatea, în principal, a îndeplinirii sarcinilor legate de
memorarea, reproducerea şi recunoaşterea materiei de asimilat;
- înţelegerea: se referă la transpunere, interpretare şi extrapolare.
1. Transpunerea înseamnă reformularea unei definiţii/noţiuni sau a unui rezultat
cu propriile cuvinte; de exemplu, traducerea unui algoritm dintr-o reprezentare oarecare
într-un limbaj implementat.
2. Interpretarea înseamnă înţelegerea comportării/evoluţiei unui obiect/sistem
dat, întrun context/mediu clar precizat.
3. Obiectivele (legate) de extrapolare au drept consecinţă căpătarea
îndemânării de a evidenţia consecinţe noi, neidentificate încă în procesul anterior;
- analiza: demonstrează capacitatea elevului de a gândi discriminativ, profund,
deductiv, de a distinge faptele concrete (noi) de ipotezele (generale) de lucru;
- sinteza: vizează - în principal - activitatea intelectuală de corelare logică a
fenomenelor observate şi a cunoştinţelor asimilate, în vederea realizării unor lucrări cu
caracter personal;
- evaluarea: implică posibilitatea formulării de către elevi a unor judecăţi de
valoare, originale (de natură ştiinţifică, socială, culturală), raportate, desigur, la cantitatea
de informaţii acumulate până în acel moment.
Formularea obiectivelor este obligaţia profesorului şi constituie o parte
indispensabilă a oricărei planificări didactice generale. Operaţionalizarea acestora
presupune în plus faptul că un cadru didactic arc o orientare globală şi coerentă asupra
întregului proces de învăţământ, că el cunoaşte şi aplică în mod curent elementele de
melodică, că procesul în sine de coordonare a învăţării în clasă nu mai are secrete, în urma
oricărei lecţii, elevii trebuie să dobândească anumite cunoştinţe, să aibă abilitatea de a le
structura (analiza, sintetiza) in mod creator. Aceştia trebuie să aibă şi posibilitatea de a se
manifesta direct, intervenţia profesorului trebuind să fie mai degrabă discretă. Prin urmare,
Operaţionalizarea înseamnă transpunerea scopurilor urmărite de obiectivele formulate în
termenii unor operaţii, acţiuni sau manifestări observabile şi aflate în concordanţă cu
cerinţele generale. Obiectivele operaţionale „sunt imediate", putând însă avea în anumite
situaţii şi o finalitate pe un termen mai lung; aceasta în ideea că deprinderile şi
cunoştinţele dobândite anterior vor trebui să fie completate prin acţiuni viitoare care să
contribuie decisiv la includerea lor în sistemul individual de informaţii şi îndemânări.

89
Operaţionalizarea obiectivelor trebuie să implice, eventual gradat, etape diferite de
dificultate care să precizeze:
- obiectivele în termeni comportamentali observabili;
- sarcinile concrete de învăţare, precum şi contextul de realizare;
- informaţia (finală) cerută de obiectiv ;
- criteriul de succes şi modul de evaluare.
Clasificarea obiectelor de învăţare
Există o multitudine de clasificări ale obiectelor de învăţare. De obicei fiecare clasificare este
realizată după un criteriu dominant: universalitate, grad de interactivitate, scalabilitate etc. O
clasificare “bidimensională” a fost propusă de M Pedroni. Clasificarea este realizată în funcţie
de doi parametric: gradul de interactivitate şi suportul de conţinut (Sergiu Corlat. Invatarea
centrată pe student).
Modele structurale ale obiectelor de învăţare:
Modele pasive (bazate pe transferul explicit de content)
Modele cu structură secvenţială (prezentări, texte)
Modele cu structură ierarhică (tutoriale, excursii tematice (virtuale)
Modele cu structură de reţea ( hărţi conceptuale pentru suportul învăţării, hărţi
informaţionale)
Modele interactive (pentru învăţarea activă)
Modele pentru utilizatori unici (modele liniare, modele cu structură interactivă: Exersare şi
Practică)
Modele universale (pentru utilizatori unici şi grupuri)
Explorative (studii de caz, rezolvări de probleme)
Jocuri (jocuri educaţionale, simulatoare)
Modele colaborative (învăţare cu ajutorul generatoarelor, Web Quest, Jocuri cu rol, MUDs şi
spaţii virtuale).

5.8. Competenţele specifice dobândite prin studierea algoritmilor

Competenţele reprezintă ansambluri structurate de cunoştinţe şi deprinderi
dobândite prin învăţare care permit identificarea şi rezolvarea în contexte diverse a
unor probleme caracteristice unui anumit domeniu.
Competenţele generale se definesc pe obiect de studiu şi se formează pe durata
învăţământului liceal; acestea au un grad ridicat de generalitate şi complexitate.

90
 Competenţele specifice se definesc pentru fiecare obiect de studiu şi se formează pe
durata unui an şcolar, ele fiind deduse din competenţele generale şi constituie etape în
dobândirea acestora.
Modul de construire a competenţelor :
Psihologia învăţării şi-a pus dintotdeauna problema obiectivelor care trebuie atinse în procesul
instruirii. La început, obiectivele erau formulate la modul general, fără a se face o legătura
sistematică între calităţile intelectului care se doreau a fi formate şi conţinutul programelor
şcolare. În ordine istorică, comportamentismului îi revine meritul de a fi atras atenţia asupra
legăturii stricte care trebuie să existe între obiectivele înscrise în programă şi testarea
performanţelor atinse. Cu transformarea obiectivelor în ţinte riguroase ale procesului de
instruire se trece, de fapt, de la didactica clasică la tehnologiile didactice.
Proiectarea competenţelor :
Termenul de competenţă are numeroase accepţiuni : el a migrat uşor dinspre domeniul
profesional-tehnic către educaţie, primind valenţe complexe în acest domeniu. Proiectarea
curriculumului pe competenţe vine în întâmpinarea achiziţiilor cercetărilor din psihologia
cognitivă, conform cărora prin competenţă se realizează în mod exemplar transferul şi
mobilizarea cunoştinţelor şi a deprinderilor în situaţii / contexte noi şi dinamice. Modelul de
proiectare curriculară centrat pe competenţe simplifică structura curriculumului şi asigură o
mai mare eficienţă a proceselor de predare – învăţare – evaluare.
Competenţele specifice dobândite prin studierea algoritmilor sunt:
- Justificarea corectitudinii unui algoritm
- Compararea dintre implementarea recursivă şi cea iterativă a aceluiaşi algoritm.
- Elaborarea unui algoritm de rezolvare a unor probleme din aria curriculară a
specializării
- Alegerea celui mai eficient algoritm de rezolvare a unei problema
- Analiza problemei în scopul identificării metodei de programare adecvate pentru
rezolvarea problemei
- Aplicarea creativă a metodelor de programare pentru rezolvarea unor probleme
intradisciplinare sau interdisciplinare, sau a unor probleme cu aplicabilitate practică

5.9. Elaborarea strategiei didactice

Elaborarea strategiei presupune alegerea unui sistem de forme, metode, materiale şi
mijloace. De selectarea şi combinarea acestora depinde reuşita activităţii didactice. Selectarea
tehnicilor de învăţare se face în funcţie de materialele didactice, care depind de metodele
utilizate, iar metodele sunt determinate de obiective, conţinut şi colectivul de elevi. Astfel,

91
obiectivele operaţionale informative vor pretinde metode mai pasive (profesorul spune - elevul
ascultă), îmbinarea judicioasă a celor „3M" (Metode, Materiale, Mijloace) asigură succesul
lecţiei. Această corelare este gândită din momentul întocmirii scenariului didactic, prin care se
înţelege o descriere anticipată a desfăşurării pas cu paj a unei lecţii. Gradul de detaliu vizează
aspectele esenţiale ale condiţiei elevului ş schimbările pe care dorim să le realizăm.
Desigur că principalele momente ale unei lecţii pot fi sumarizate după cum urmează:
• Captarea atenţiei
• Enunţarea obiectivelor
• Reactualizarea cunoştinţelor învăţate anterior
• Prezentarea conţinutului noii lecţii
• Dirijarea învăţării
• Asigurarea feedbackului
• Intensificarea atenţiei
• Asigurarea transferului de cunoştinţe.
Succesiunea şi importanţa lor variază de la o lecţie Ia alta, de la un tip de lecţie la
altul. Lecţiile pot fi împărţite în trei mari categorii (vor exista şi lecţii mixte):
• de comunicare de noi cunoştinţe ;
• de fixare şi formare de priceperi şi deprinderi;
• de recapitulare şi sistematizare.
Totuşi nu trebuie omis faptul că lecţia este un act de creaţie care nu se poate încadra
în şabloane. Profesorul se bazează doar pe anumite sugestii pentru întocmirea de diverse
scenarii.

92
 5.10. Resurse didactice utile în predarea arborilor binari – Puncte cheie ale proiectării

 Operaţionalizarea obiectivelor
Reprezintă activitatea de specificare sau identificare a referinţelor sau incidenţelor concrete
sau practice ale unui concept sau enunţ general sau abstract. Metode de stabilire a obiectivelor
operaţionale sunt:
- derivarea competenţelor specifice, respectiv a obiectivelor de referinţă prin
detalierea acestora la nivelul claselor de comportament pentru domeniul cognitiv.
- analiza conţinuturilor materialului de învăţat. Reperele care trebuie urmărite în
procesul de operaţionalizare a obiectivelor sunt:
- gradul de complexitate a materialului
- caracterul său predominant – material cu conţinut descriptiv sau teoretic, aplicativ,
experimental.
În cazul algoritmilor pentru echilibrarea arborilor binari, conţinutul materialului de învăţat
este predominant aplicativ. De aceea, obiectivele operaţionale trebuie să vizeze diferite etape
ale comportamentului cognitiv: achiziţie, înţelegere, aplicare, analiză, sinteză şi evaluare.
Obiectivele operaţionale trebuie să specifice: comportamentul măsurabil care este urmărit,
condiţiile în care se va produce comportamentul, precum şi performanţa. Exemplu de obiectiv
operaţional bine formulat este următorul.
Pornind de la un arbore dat, elevul va trebui să scrie un program pentru parcurgerea
acestuia in adâncime şi în lăţime; programul va fi scris în limbaj C++.

 Alegerea conţinuturilor
Prima decizie pe care trebuie să o luăm este ce algoritmi vom prezenta pentru parcurgere. Mai
întâi este necesară evidenţierea celor două mari tipuri de probleme: implementarea static sau
dinamică. În aceasta alegere trebuie consideraţi mai mulţi factori: nivelul de cunoştinţe al
clasei, prezentarea gradată a conţinuturilor, resursele de care dispunem (ex: manuale). Cele
mai multe manuale prezintă algoritmii Kruskal si Prim. Prezentarea implementării arborilor în
memoria internă prin cele două metode trebuie să fie anterioară prezentării algoritmilor
pentru parcurgere.

93
  Modalităţi de captare a atenţiei
Cea mai eficientă modalitate de captare a atenţiei este prezentarea utilităţii algoritmilor prin
exemple de probleme:
[Link]ţii simple care să necesite implementarea operaţiilor elementare pe structuri
arborescente cum ar fi: parcurgerea unui arbore în scopul identificării tuturor nodurilor cu o
anumită proprietate, determinarea înălţimii unui arbore, copierea unui arbore, etc.
[Link] mai complexe, în care elevii să identifice eficienţa utilizării structurilor de date
arborescente, cum ar fi: realizarea eficientă a unui dicţionar, sortarea unei secvenţe de valori
cu ajutorul heap-urilor (heapsort), optimizarea algoritmului lui Kruskal prin organizarea
muchiilor ca heap.
Pentru toate aceste exemple se pot găsi modele vizuale foarte relevante.

 Resurse metodologice
În predarea structurilor arborescente vom utiliza următoarele metode didactice:
Învăţarea asistată – utilizarea unor tutoriale
Utilizarea resurselor web – cele mai utile resurse sunt animaţiile pentru diverşi algoritmi şi
structuri de date. Iată câteva adrese utile:
[Link]
[Link]
[Link]
Predarea asistată – folosirea pachetului Asistentului Educaţional pentru Licee, precum şi a
altor tutoriale.
Demonstraţia – profesorul va oferi pentru fiecare algoritm exemple de aplicare a acestora cu
evidenţierea grafică a fiecărui pas şi trasarea execuţiei algoritmului.
Algoritmizarea – este important ca elevii să înţeleagă mai întâi principiul de lucru al
algoritmului studiat şi, abia după aceea, să descrie algoritmul în paşi. În faza de implementare
a programului este necesară discutarea posibilităţilor de reprezentare a datelor.
Autodocumentarea – este o metodă esenţială de predare a informaticii. Elevii trebuie învăţaţi
în primul rând cum să înveţe. Deoarece informatica este un domeniu în plină dezvoltare, este
foarte posibil ca în foarte scurt timp mare parte din lucrurile studiate să fie perimate şi atunci
apare întrebarea „De ce am învăţat asta?”. Activitatea de autodocumentare nu poate fi lăsată la
voia întâmplării: „Căutaţi câte ceva despre arborii echilibraí.”. Elevii trebuie să primească
cerinţe clare, căutarea informaţiei să fie sub forma unei competiţii astfel încât să fie motivaţi
să caute resurse cât mai utile. Exemple de teme de autodocumentare:
Algoritmi pentru echilibrarea arborilor binari

94
Simulări animate pentru algoritmii studiaţi
Ce algoritmi foloseşte TCP-IP pentru rutarea pachetelor?
Autodocumentarea nu se opreşte în faza de găsire a resurselor. Acestea trebuie filtrate,
înţelese şi exersate. În final, se deschide o dezbatere pe tema aleasă cu toată clasa. Este o
metodă foarte utilă de pregătire a elevilor performanţi.
Evaluarea
O componentă importantă a procesului didactic, deseori neglijată, este evaluarea.
observarea sistematică a activităţii elevilor
Se vor întocmi fişe de observare a activităţii elevilor, după un model asemănător următorului:

algoritmului
partea

Aplicarea algoritmului pe

Participarea la discuţiile

diverse
matricei

(prezentarea

despre implementare

Analiza algoritmului
Nume şi prenume

în cuvinte proprii
la

exemple grafice

la
Implementarea
algoritmului)

algoritmului
Participarea

Prezentarea

Observaţii
Adaptarea
Utilizarea
costurilor

teoretică

enunţuri
Rubricile vor fi completate pe baza activităţii observate, în fiecare din oră pentru elevii care
au fost observaţi. Se va încerca completarea cel puţin a unei rubrici din tabel pentru fiecare
elev, cu calificative (slab, satisfăcător, bine, foarte bine), cu puncte pe scară 0-5, cu + sau -.
Bineînţeles, elevii vor fi anunţaţi la finalul orei despre calificativul primit, urmând ca în orele
următoare să-şi îmbunătăţească performanţa.
Rubrica Observaţii va fi completată cu fapte remarcabile ale elevului.
- evaluare orală
Este metoda de evaluare foarte des utilizată, mai ales în faza de reactualizare a cunoştinţelor şi
în faza de fixare a acestora. Un exemplu de evaluare orală apare în proiectul de activitate din
lucrarea de faţă, în momentul reactualizării cunoştinţelor
- evaluarea prin proiecte
Este metoda de evaluare care solicită cel mai mult elevul şi care pare foarte adecvată temei de
faţă. Este de preferat să fie asociată lucrului în echipă, astfel încât să fie cât mai cuprinzătoare.
Temele de proiect pot merge de la aplicarea unui algoritm pe o situaţie specificată (exemplu:
transport în comun, nodurile fiind staţiile, ponderile arcelor fiind durata transportului între
două staţii succesive) până realizarea de programe demonstrative sau tutoriale pentru
algoritmii studiaţi, folosind Action Script sau Java, în funcţie de cunoştinţele elevilor.

95
 - autoevaluarea
Este metoda care asigură conştientizarea de către elev a nivelului cunoştinţelor şi abilităţilor
sale. Dacă este posibil, se va folosi autoevaluarea cu ajutorul calculatorului sau inter-
evaluarea (colegii schimbă lucrările între ei şi îşi acordă punctaj, apoi confruntă cu punctajul
acordat de profesor). Pentru autoevaluare este cel mai bine să se folosească itemi tip grilă, cu
alegere multiplă sau duală, de completare, depistare a erorilor, evaluarea unei secvenţe de
program pentru intrări date, aceştia fiind mai uşor de corectat.

5.11. Modele de proiectare didactică

În această secţiune vor fi prezentate:
- planificare calendaristică pentru clasa a XI-a
- proiectul unităţii de învăţare „Structuri arborescente”
- proiect de activitate – de formare a capacităţilor şi dobîndire a cunoştinţelor ”.Arbori
[Link] arborilor binari”
- proiect de activitate - recapitulare şi sitematizarea cunoştinţelor “Arbori binari”
- proiect de activitate - evaluare a cunostinţelor “Arbori”

96
 Planificare calendaristică la informatică
Clasa a XI-a
Specializarea: matematică-informatică
Nr. Ore: 4 ore (1 teorie+3 laborator)/săptămână

Programa aprobată cu [Link]. 5099/09.09.2009

Filiera teoretică, profil real, specializarea: Matematică-informatică

Unitatea de Nr. de ore

Competenţe specifice Conţinuturi Săptămâna Observaţii
învăţare alocate
1.1 Particularităţi de memorare a şirurilor de caractere: 5 S1 – S5
Şiruri de 1.2 Subprograme predefinite de prelucrare a şirurilor de
caractere 1.3 caractere.
1.4 Evaluare sumativă
Rezolvarea unor probleme cu caracter practic: 3 S6 – S8
 declararea unei variabile de tip structură neomogenă
 exemplificarea cazurilor în care se utilizează structuri de
1.1 date neomogenă
Structuri de date
1.2  accesarea valorilor din câmpurile unei înregistrări
neomogene
1.3  prelucrarea unei înregistrări/structuri la nivel de câmp şi
(struct/record)
1.4 la nivel de structură
Evaluare sumativă

Structura şi a modul de definire al subprogramelor 5 S9-S13

Declararea şi apelul subprogramelor
Variabile locale şi globale
3.1
Transferul parametrilor la apel (prin valoare şi
Subprograme 3.2
referinţă)
3.3
Returnarea valorilor de către subprograme
Aplicaţii folosind subprograme
Evaluare sumativă
3.1 Definire. Exemplificare
3.2 Mecanisme de implementare
Recursivitate 3 S14 - S16
3.4 Aplicaţii cu subprograme recursive
3.5 Evaluare sumativă

97
 Unitatea de Nr. de ore
Competenţe specifice Conţinuturi Săptămâna Observaţii
învăţare alocate
Metoda de Prezentare generală
2.1
programare Aplicaţii 3
2.2 S17-S19
„Divide et Evaluare sumativă
2.3
Impera”
Prezentare generală
Implementarea iterativă sau recursivă a algoritmilor de 3 S20-S22
Metoda de 2.1
generarea produsului cartezian, permutărilor,
programare 2.2
combinărilor, aranjamentelor, submulţimilor unei
“Backtracking” 2.3
mulţimi
Evaluare sumativă
Reprezentarea grafică a structurilor de tip listă. Operaţii
1.1 specifice 3 S23-S25
Liste
1.2 Stiva şi coada
1.3 Aplicaţii cu implementare statică
Evaluare sumativă
Terminologie şi proprietăţi (graf orientat şi neorientat,
adiacenţă, incidenţă, grad; lanţ, lanţ elementar, drum,
drum elementar, ciclu,ciclu elementar, circuit, circuit
elementar; subgraf, graf parţial; conexitate, tare
conexitate, arbore, arbore parţial, etc) 4
S26 – S29
Reprezentarea în memorie a grafurilor (matrice de
adiacenţă, liste de adiacenţă, lista muchiilor/ arcelor)
Grafuri orientate Parcurgerea grafurilor. Aplicaţii.
1.5 Tipuri particulare de grafuri (graf eulerian, graf
si neorientate 
1.6 hamiltonian) 4
S30-S33
 Structuri arborescente
 Arbori binari-definitii, metode de parcurgere
 Implementarea arborilor in memoria interna S34-S36
3
 Arbori binari de cautare
 Arbori binari de sortare
Aplicatii.
Evaluare sumativă

98
COMPETENŢE SPECIFICE:

1.1. Analizarea unei probleme în scopul identificării datelor necesare şi alegerea modalităţilor adecvate de structurare a datelor care intervin într-
o problemă
1.2. Identificarea avantajelor utilizării diferitelor metode de structurare a datelor necesare pentru rezolvarea unei probleme
[Link] şirurilor de caractere şi a structurilor de date neomogene în modelarea unor situaţii problemă
1.4. Implementarea unor algoritmi de prelucrare a a şirurilor de caractere şi a structurilor neomogene
1.5. Transpunerea unei probleme din limbaj natural în limbaj de grafuri, folosind corect terminologia specifică
1.6. Descrierea unor algoritmi simpli de verificare a unor proprietăţi specifice grafurilor

2.1 Analiza problemei în scopul identificării metodei de programare adecvate pentru rezolvarea problemei
2.2 Construirea unor soluţii pentru probleme simple care se rezolvă cu ajutorul metodelor de programare
2.3 Aplicarea creativă a metodelor de programare pentru rezolvarea unor probleme intradisciplinare sau interdisciplinare, sau a unor probleme cu
aplicabilitate practică

3.1 Recunoaşterea situaţiilor în care este necesară utilizarea unor subprograme

3.2 Analiza problemei în scopul identificării subproblemelor acesteia
3.3 Utilizarea corectă a subprogramelor predefinite şi a celor definite de utilizator
3.4 Descrierea şi aplicarea mecanismului recursivităţii
3.5 Identificarea avantajelor şi a dezavantajelor aplicării tehnicii recursive în implementarea unor rezolvări

99
 PROIECTUL UNITĂŢII DE ÎNVĂŢARE
Unitatea de invatare: Structuri arborescente(arbori) Nr. ore alocate: 7 Clasa: a XI-a

Continut Competente specifice Activitati de invatare Resurse Evaluare Nr. ore Observatii
alocate
 Structuri 1.5. Transpunerea unei  Exercitii simple pentru  Activitatile se vor Evaluare frontala 2
arborescente probleme din limbaj natural desfasura in clasa si pe baza de
insusirea terminologiei
în limbaj de grafuri, in laboratorul de observatii directe
Arbori binari- specifice structurilor informatica
 folosind corect
definitii, metode de terminologia specifică arborescente: definitii,
parcurgere  Conversaţia
proprietati, metode de
1.6. Descrierea unor  Exerciţiul Evaluare
algoritmi simpli de parcurgere (RSD, SRD,
individuala pe baza
verificare a unor proprietăţi SDR), operatii specific.  Explicatie participarii la lectie
 Implementarea
specifice grafurilor (raspunsuri la
arborilor in memoria Implementarea unor Munca individuală intrebari,
interna algoritmi in care se rezolvarea de 2
utilizeaza reprezentarea Învăţarea prin exercitii)
 Arbori binari de in memorie a structurilor descoperire
cautare arborescente (static si
dinamic)
 Manual;
Rezolvarea unor probleme Caiet;
Aplicatii. cu caracter practic privind Mediul de compilare 3
arborii binari de căutare – (calculator) Evaluare scrisa (la
definiţie, proprietăţi, Fise de lucru sfarsitul unitatii)
operaţii specifice (inserare Soft educational
nod, ştergere nod, căutare
element)
Aplicaţii,

100
 PROIECT DIDACTIC
Data: 
Clasa: a XI-a 
Disciplina: Informatică 
Unitatea de învăţare: Structuri arborescente
Tema: Arbori [Link] arborilor binari
Tipul lecţiei: de formare a capacităţilor şi dobîndire a cunoştinţelor
Obiective operaționale:
O1: să definească noţiunea de nod, arbore binar şi arbore vid;
O2: să explice noţiunile rădăcină, subarborele stîng, subarborele drept, descendent, nivel, nod terminal, nod neterminal înălţimea
arborelui binar;
O3: să descrie modurile de creare a arborilor binari;
O4: Să parcurgă arborii binari prin cele trei metode.
Strategii didactice
•   Metode de învăţământ:  Conversaţia, expunerea;   problematizarea, exerciţiul;
•    Forme de organizare a activităţii instructive:  Individuală
•    Forme de dirijare a activităţii:    Independentă
•    Resurse materiale:   
 Informatica, manual pentru clasa a XI-a, Tudor Sorin, Editura L $ S Soft
 Prezentare  PowerPoint
•    Metodele de evaluare:  Întrebări adresate elevilor;  Fişă de lucru;

101
I. Scenariu didactic
Obiectiv Forma de
Etapa lecţiei Durata Conţinuturi Activităţi Evaluare
urmărit desfăşurare

2 Elevii se aşează la calculator grupe

conform repartizării,
1. Moment completează fişa calculatorului
organizatoric şi deschid mediul de
programare Code Bloks

ÎNTREBARE RĂSPUNS AŞTEPTAT

1) Ce înţelegem prin arbore - un arbore este

un graf neorientat, conex ș
i fără cicluri

2) Ce este un arbore cu -in cazul arborilor cu

radacina? rădăcină se pune în
evidenţă un vârf special al
său numit rădăcină.
Alegerea rădăcinii duce la
aşezarea arborelui pe
nivele.
2.
3) Ce intelegeti prin -vizitarea în mod
parcurgerea arborilor? sistematic a nodurilor
arborelui în scopul
prelucrării informaţiei
ataşate nodurilor sau a
liniarizării nodurilor.

4) Cum se face -prin matricea de

implementarea arborilor cu adiacenta, lista de
radacina? adiacenta, legatura de tip
tata, legatura de tip parinte
nod terminal

102
 Obiectiv Forma de
Etapa lecţiei Durata Conţinuturi Activităţi Evaluare
urmărit desfăşurare

O1 20 Subiectul lecţiei:”Arbori binari. Parcurgerea arborilor Se solicită elevilor sa furnizeze frontal

binari” exemple
O2
În informatică, un arbore binar este un arbore în care
O4 fiecare nod are cel mult doi succesori (fii). De obicei,
succesorii se numesc „nodul stânga” şi „nodul dreapta”. 
O5 Nod- o variabilă dinamică de tipul record care conţine un Elevii ascultă şi îşi fac notiţe.
cîmp destinat memorării informaţiei utile şi doi indicatori
de adresă. Elevii îşi notează în caiete
Arborele binar se defineşte recursiv după cum urmează: exemplele propuse
a) un nod este un arbore binar
b) un nod ce conţine legături către doi alţi arbori binari este
un arbore binar Observare
-- fronta sistematica
Arborele vid nu conţine nici un nod
Un arbore binar este o mulţime de noduri care îndeplinesc
următoarele condiţii:
► fiecare nod are 0, 1 sau 2 succesori;
3. Prezentarea ► fiecare nod are un singur predecesor, cu excepţia
noului conţinut rădăcinii care nu are niciunul;
► succesorii fiecărui nod sunt ordonaţi (fiul stâng,
fiul drept; dacă este unul singur trebuie menţionat care).

103
 Obiectiv Forma de
Etapa lecţiei Durata Conţinuturi Activităţi Evaluare
urmărit desfăşurare

Arborii binari pot fi construiţi în memoria calculatorului cu Se prezintă algoritmul pe Pe grupe

ajutorul algoritmilor iterativi sau algoritmilor recursivi.
exemplu grafic şi în varianta
animată Frontal orală
Algoritmul iterativ creează nodurile în ordinea apariţiei lor
pe niveluri:
Se reia algoritmul pe exemplu
 se creează nodul rădăcină; concret
 Nodul –rădăcină se introduce într-o coadă; Exersarea algoritmului pe
 Pentru fiecare nod extras din coadă se creează, tutorial
dacă există, descendentul stîng şi descendentul drept;
Se cere elevilor să încerce o
 Nodurile nou create se introduc în coadă;
formulare generală a
 Procesul de construire a arborelui se încheie cînd
algoritmului
coada devine vidă.
Nodurile arborelui din slide-ul anterior vor fi create în
următoarea ordine:

104
 Obiectiv Forma de
Etapa lecţiei Durata Conţinuturi Activităţi Evaluare
urmărit desfăşurare

B C

Pe grupe
D E F G

frontal
H I J

Nodurile arborelui vor fi create în următoarea

ordine: A, B,C,D,E,F,G,H,I,J

- Se argumentează
corectitudinea algoritmului
Algoritmul recursiv construieşte arborii binari urmînd
direct definiţia respectivă:

 Se creează nodul rădăcină; - Se analizează

 Se construieşte subarborele stîng complexitatea algoritmului
 Se construieşte subarborele drept.

B C

D E F G

H I J

Nodurile arborelui vor fi create în următoarea

ordine: A, B, D, E, H, C, F, G, I, J.

- Expunerea este susţinută cu ajutorul prezentării

anexate.

105
 Obiectiv Forma de
Etapa lecţiei Durata Conţinuturi Activităţi Evaluare
urmărit desfăşurare

4. Dirijarea O2 10 Însărcinare:
învăţării Se dă arborele binar. Determinaţi înălţimea arborelui,
O3 nodurile terminale şi cele neterminale.

Semnificaţia noţiunii de parcurgere a unui arbore binar;

► Prin parcurgerea unui arbore se înţelege
examinarea în mod sistematic a nodurilor sale astfel încît
fiecare nod să fie atins o singură dată. Implementarea algoritmului în Frontal formativă /
► Sinonim: “vizitarea” vîrfurilor unui arbore. limbaj C++
► Scopul parcurgerii: Pe grupe observare
 Prelucrarea informaţiilor asociate Testare pe diverse seturi de sistematica
vîrfurilor;
date
 Transformarea arborelui dintr-o
reprezentare plană într-o structură liniară.
Tipuri de parcurgeri:
Există mai multe modalităţi de parcurgere care diferă prin
ordinea de vizitare a nodurilor:
► Parcurgerea în preordine (RSD);
► Parcurgerea în inordine (SRD);
► Parcurgerea în postordine (SDR).
Obs. Putem considera că fiecare nod al arborelui
binar subordonează un subarbore stîng şi un subarbore
drept.
Parcurgerea în preordine (RSD)
► Se realizează în ordine următoarele operaţii:
1. Se vizitează rădăcina;
2. Se vizitează subarborele stîng;
3. Se vizitează subarborele drept.

106
 Obiectiv Forma de
Etapa lecţiei Durata Conţinuturi Activităţi Evaluare
urmărit desfăşurare

► Ca urmare a parcurgerii arborelui se obţine o

soluţie sub forma unui tablou unidimensional (vector).
Parcurgerea în inordine (SRD)
► Se realizează în ordine următoarele operaţii:
1. Se vizitează subarborele stîng;
2. Se vizitează rădăcina ;
3. Se vizitează subarborele drept.
► Ca urmare a parcurgerii arborelui se obţine o
soluţie sub forma unui tablou unidimensional (vector).
Parcurgerea în postordine (SDR)Se realizează în ordine
următoarele operaţii:
1. Se vizitează subarborele stâng;
2. Se vizitează subarborele drept ;
3. Se vizitează rădăcina.
Ca urmare a parcurgerii arborelui se obţine o soluţie sub
forma unui tablou unidimensional (vector).

5 Propun elevilor următoare însărcinare: Cum putem realiza acest frontal observarea
Se consideră un arbore binar cu 8 noduri. Dacă lucru? modului de
individual lucru
5. Obţinerea 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 Elevii notează tema, pun
performanţei
parcurgerea în postordine a aceluiaşi arbore? întrebări referitoare la cerinţe,
dau idei de rezolvare.

5 [Link] este un arbore binar, din ce este alcătuit? - Aplicare test autoevaluare individual autoevaluare
6. Realizarea
conexiunii [Link] parcurgem arborele binar? 
inverse
7. Tema 3 Tema pentru acasă este: Elevii notează tema, pun
pentru acasa Utilizînd programul P130 din manual, elaboraţi un program întrebări referitoare la cerinţe,
dau idei de rezolvare.
care construieşte arborele genealogic propriu pe parcursul a
trei sau patru generaţii. Nodul – rădăcinî conţine numele,
prenumele şi anul naşterii, iar nodurile descendente conţin

107
 Obiectiv Forma de
Etapa lecţiei Durata Conţinuturi Activităţi Evaluare
urmărit desfăşurare

datele respective despre părinţi.

108
PROIECT DIDACTIC

Data
DISCIPLINA: Informatică
CLASA: a XI-a
UNITATEA DE ÎNVĂŢARE: Structuri arborescente
TEMA: Arbori binari
TIPUL LECŢIEI: Lectie de recapitulare si sistematizare a cunoştinţelor
LOCUL DE DESFĂŞURARE: Laboratorul de informatică
OBIECTIVE DE REFERINŢĂ:

- să se realizeze programe în limbajul C++ pentru rezolvarea de probleme;

- să urmărească etapele de realizare a unei aplicaţii.

OBIECTIVE EDUCAŢIONALE

OBIECTIVE COGNITIVE:

- să definească corect noţiunile teoretice însuşite;

- să aplice corect noţiunile însuşite în aplicaţii concrete.

OBIECTIVE AFECTIVE:

- să argumenteze anumite situaţii create în etapele de rezolvare a unei aplicaţii;

- să manifeste interes faţă de problemele puse şi dorinţa de învăţare prin descoperirea
proprie a adevărului ştiinţific;
- să studieze individual şi în echipă, în colaborare şi în competiţie, cunoscând scopul
învăţării temei date;
- să aprecieze corect soluţiile oferite de ceilalţi colegi.

OBIECTIVE PSIHOMOTORII:

- să dezvolte gândirea algoritmică, logică, flexibilă, creatoare;

- să-şi dezvolte atenţia concentrată şi spiritul de observaţie;
- să utilizeze corect noţiunile teoretice însuşite;
- să conceapă programe pentru aplicaţiile propuse.

Nivelul iniţial al clasei:

Elevii şi-au însuşit toate noţiunile teoretice referitoare la arborii binari şi au dezvoltat
aplicaţii.

OBIECTIVE OPERAŢIONALE

 să reproducă şi să explice noţiunile de bază ale arborilor binari;

 să reprezinte arborii binari;
109
  să parcurgă arborii binari;
 să înţeleagă exemplele date şi să elaboreze programe corecte pentru aplicaţiile
propuse.

Strategii didactice

 Principii didactice
- principiul participării şi învăţării active;
- principiul asigurării progresului gradat al performanţei;
- principiul conexiunii inverse.

 Metode de Învăţământ
- metode de comunicare orală : -conversaţia, explicaţia;
- metode activ participative :-problematizarea, exerciţiul.

 Procedee de instruire
- conversaţia de recapitulare şi consolidare;
- problematizarea prin crearea situaţiilor problemă;
- exerciţii de consolidare şi sistematizare.

 Forme de organizare
- frontală şi individuală.

 Forme de dirijare a învăţării

- dirijată de profesor sau prin materiale didactice;
- independentă.

 Resurse materiale
- materiale bibliografice ( manualul );
- fişe de lucru;
- set de aplicaţii;
- teste de evaluare;
- computerul.

 Metode de evaluare
- iniţială (întrebări orale şi teste grilă);
- seturi de aplicaţii cu urmărirea atingerii performanţei minime.

110
 DESFĂŞURAREA ACTIVITĂŢII:

 Moment organizatoric : (2 min)

o pregătirea setului de întrebări şi aplicaţii
o verificarea prezenţei;
o verificarea cantitativă a temei, frontal şi verificarea calitativă, prin sondaj;
o verificarea existenţei resurselor materiale.
Captarea atenţiei clasei:
o anunţarea subiectului pentru tema respectivă;
o anunţarea obiectivelor pentru tema respectivă;
o anunţarea modului de desfăşurare a activităţii.

 Reactualizarea cunoştinţelor: (6 min)

I. Se realizează un set de întrebări pentru consolidarea cunoştiinţelor teoretice, ca mai
jos:

1. Ce este un arbore?
R. graf neorientat, conex şi fără cicluri

2. Din ce este format un arbore

R. Dintr-un nod rădăcină şi un număr finit de subarbori

3. Definiţi arborele binar.

R. Arborele binar este un arbore ordonat în care fiecare nod are cel mult doi
descentenţi. Ordinea subarborilor contează! Arborele conţine: o rădăcină, un
subarbore stâng şi un subarbore drept.

4. Care sunt proprietatile arborilor?

R.

1. Un arbore binar complet care are n noduri terminale, toate situate pe acelaşi nivel,
are în total 2n-1 noduri. În consecinţă, un arbore binar complet are un număr impar
de noduri.
2. Numărul maxim de noduri de pe nivelul i al unui arbore este 2i.
3. Numărul maxim de noduri dintr-un arbore binar cu înălţimea h este 2h+1-1.
4. Un arbore binar cu n noduri are înălţimea mai mare sau egală cu [log2n].

 Recapitularea şi sistematizarea cunoştinţelor (30 min)

II. Se realizează cu teorie si exerciţii pentru verificarea utilizării corecte a
noţiunilor învăţate:

Parcurgerile arborilor binari sunt cele mai frecvente operaţii utilizate pe arbori.
Parcurgerea unui arbore înseamnă vizitarea fiecărui nod al arborelui o singură dată,
cu scopul prelucrării informaţiei memorate în acel nod. Dintre cele mai utilizate
parcurgeri sunt parcurgerile în adâncime (algoritmul DFS) şi pe niveluri (algoritmul
BFS).

111
A. Parcurgeri în adâncime sunt parcurgerile în preordine, inordine şi postordine. În toate
cele trei tipuri de parcurgere în adâncime se vizitează prima dată subarborele stâng şi apoi
subarborele drept, iar diferenţa constă în momentul în care se vizitează rădăcina. Funcţiile de
parcurgere pot fi scrise recursiv sau iterativ, folosind o stivă.

n 1 2 3 4 5 6
S 2 4 6 0 0 0
D 3 5 0 0 0 0

Realizaţi parcurgerea in preordine(RSD), inordine(SRD) şi postordine(SDR) pentru

graful de mai sus.

R. Parcurgerea RSD: 1 2 4 5 3 6

Parcurgerea SRD: 4 2 5 1 6 3

Parcurgerea SDR: 4 5 2 6 3 1

B. Parcurgerea pe niveluri – se vizitează rădăcina, apoi toţi fii nodului rădăcină, de la stânga
spre dreapta şi se continuă în acest mod pe toate nivelurile.

Realizaţi parcurgerea pe nivel pentru arborele din figura de mai sus.

R. şirul parcurgerii pe niveluri este: 1 2 3 4 5 6.

Se prezintă elevilor următoarea problemă:

Se citeste o padure cu n varfuri prin vectorul de tati. Sa se determine din cati arbori este
formata padurea.

Exemplu: Pentru vectorul de tati 2 0 2 0 4 5 0 7, padurea este formata 3 arbori.

R. O posibilă rezolvare ar fi: Codul sursa este urmatorul:

#include ifstream f("[Link]");

ofstream g("[Link]");
int t[100],n;
void citire()
{ f>>n;
for(int i=1;i<=n;i++)
f>>t[i]; }
int main()
{ citire();
int k=0;
for(int i=1;i<=n;i++)
if(t[i]==0)
k++;
g<<k<<" "; }
112
Se dă următoarea problemă
Se citesc din fisierul [Link] de pe prima linie două numere n şi R reprezentând
numărul de noduri şi rădăcina unui arbore binar. De pe a doua şi a treia linie se vor citi
câte n elemente reprezentând rădăcinile subarborilor stâng şi respectiv drept al fiecărui
nod, sau 0 dacă nu există subarborele.
Afişaţi pe ecran şirurile parcurgerilor RSD, SRD şi SDR ale arborelui citit.
[Link] rezultate
81 RSD: 1 2 4 5 6 3 7 8
24700000 SRD: 4 2 5 6 1 7 3 8
35806000 SDR: 4 6 5 2 7 8 3 1

1. #include<fstream>
2. #include<iostream>
3. using namespace std;
4. int i,n,St[101],R,Dr[101];
5. void citire()
6. {
7. ifstream f("[Link]");
8. f>>n>>R;
9. for(i=1;i<=n;i++) f>>St[i];
10. for(i=1;i<=n;i++) f>>Dr[i];
11. [Link]();
12. }
13. void RSD(int p)
14. {
15. if(p>0)
16.
17. { cout<<p<<' ';
18. RSD(St[p]);
19. RSD(Dr[p]);
20. }
21. }
22. void SRD(int p)
23. {
24. if(p>0)
25. {
26. SRD(St[p]);
27. cout<<p<<' ';
28. SRD(Dr[p]);
29. }
30.
31. }
32. void SDR(int p)
33. {
34. if(p>0)
35. {SDR(St[p]);
36. SDR(Dr[p]);
37. cout<<p<<' ';}
38.
39. }
40. int main()
41. {
42. citire();
43. cout<<"RSD: ";
44. RSD(R);
45. cout<<endl;
46. cout<<"SRD: ";
47. SRD(R);
48. cout<<endl;
49. cout<<"SDR: ";
50. SDR(R);}

113
 Realizarea conexiunii inverse (10 min)
II. Se realizează cu exerciţii pentru verificarea utilizării corecte a noţiunilor învăţate:

Cerinţă:

1. Prin înălţimea unui arbore cu rădăcină înţelegem numărul de muchii ale celui mai lung lanţ
format din noduri distincte care are una dintre extremităţi în rădăcina arborelui. Scrieţi care
este înălţimea şi care sunt frunzele arborelui descris prin următorul vector ”de taţi”:
12345678
(6,6,5,0,6,4,4,7).

Răspuns aşteptat:                 
INALTIME: Nivelul 4
FRUNZE: 1,2,3,8

2. Se consideră un arbore cu rădăcină în care doar 13 dintre nodurile sale au exact 2 descendenţi
direcţi (fii), restul nodurilor având cel mult un descendent direct (fiu). Care este numărul
frunzelor arborelui?

Raspuns asteptat: 2*13

3. Pentru arborele cu rădăcină având următorul vector de “de taţi” tata=(2,0,2,3,2,3,4,4,3), care
este rădăcina arborelui şi care sunt descendenţii direcţi (fiii) ai nodului 3?

Raspuns asteptat:
Rădăcina: 2
Descedenţi direcţi ai nodului 3: 4,6,9

4. Care este vectorul "de taţi" pentru arborele cu rădăcină

din figura alăturată?
a. 0 0 5 7 6 5 1 b. 1 0 0 7 6 5 0
c. 7 4 5 0 4 5 4 d. 7 4 5 0 4 5 7

5. Răspuns aşteptat: c

6. Se consideră un arbore cu rădăcină, cu 100 noduri, numerotate de la 1 la 100. Dacă nodul 13

are exact 14 fraţi şi nodul 100 este tatăl nodului 13, care este numărul total de
descendenţi direcţi (fii) ai nodului 100?

114
 Răspuns aşteptat: 15 fii.
Daca nodul 13 este fiu al nodului 100 si are 14 fii, atunci numarul total de descendenti este
15. (14+1=15).

 Fişa după care se desfăşoară lecţia de consolidare şi sistematizare:

Funcţii exercitate de Activităţi ale lecţiei Metode

evenimentul
instrucţional

Reactualizarea Se face prin cerinţele de la Conversaţia euristică cu scop

cunoştinţelor punctul I de fixare

Recapitularea şi Se face prin cerinţele de la Conversaţia euristică cu scop

sistematizarea punctul II de consolidare
cunoştinţelor
Exerciţiul de consolidare

Realizarea conexiunii Se face printr-un set de aplicaţii Exerciţiul de consolidare

inverse de la punctul III
Problematizarea

 Tema pentru acasa (2 min)

1. Se citeste un arbore cu n varfuri dat prin vectorul TATA. Sa se afiseze frunzele

arborelui. Exemplu: Pentru vectorul de tati 2 0 2 1 3 se vor afisa frunzele 4 si 5.

2. Se citeste un arbore cu n varfuri dat prin vectorul muchiilor si apoi se citeste varful
radacina. Sa se calculeze si sa se afiseze numarul de niveluri ale arborelui. Exemplu:
Pentru un arbore cu 5 noduri si muchiile [1,2] [2,3] [1,4] [3,5] numarul de niveluri este
3.

3. Se citeste un arbore prin vectorul de tati. Sa se determine si sa se afiseze cel mai lung
lant din arbore. Exemplu: Pentru vectorul de tati 2 0 2 5 2 5 3 7 se afiseaza lantul 4 5 2
378

115
 PROIECT DIDACTIC

Data

Clasa: a XI-a

Disciplina: Informatică

Unitatea de învăţare: Structuri arborescente

Tema: Arbori binari

Tipul lecţiei: evaluarea cunoştiinţelor

Locul de desfăşurare: laboratorul de informatică

Obiective operaţionale:

 Să aleagă varianta corectă de răspuns pentru itemii obiectivi cuprinşi în testul de evaluare;
 Să formuleze răspunsuri la itemii semiobiectivi de tip intrebare structurată cuprinşi în testul
de evaluare;
 Să formuleze o rezolvare pentru itemii subiectivi de tip rezolvare de probleme cuprinşi în
testul de evaluare;
Strategii didactice

 Principii didactice:
 Principiul asigurării progresului gradat al performanţelor şi înlăturarea treptată a
punctelor de sprijin;
 Metode de învăţământ
 problematizarea, exerciţiul;
 Forme de organizare a activităţii instructive
 Individuală
 Forme de dirijare a activităţii
116
  Independentă
 Resurse materiale
 Tudor Sorin, Vlad Tudor , Informatica, clasa a XI a , Editura L & S Soft
 Mariana Milosescu, Informatica, clasa a XI a, Editura Didactica si Pedagogica, RA
 Resurse psihologice ale desfăşurării activităţii
Elevii şi-au însuşit noţiunile teoretice predate la capitolul „Arbori binari”, precum şi
modul de utilizare al acestora;

 Metodele de evaluare
Evaluare sumativă – test de evaluare

Desfăşurarea activităţii

 Moment organizatoric:
 Pregătirea lecţiei:
 întocmirea proiectului didactic
 realizarea testului de evaluare
 Organizarea şi pregătirea clasei
 verificarea frecvenţei elevilor
 verificarea existenţei resurselor materiale;
 Captarea atenţiei elevilor:
 anunţarea subiectelor pentru tema respectivă
 explicarea modului de desfăşurare a evaluării.

117
Numele şi prenumele: _______________________________________________
Clasa: _____________________________
Data: _____________________________

TEST DE EVALUARE

I. Alegeţi litera corespunzătoare răspunsului corect (20 puncte)

1. (4p) Pentru un arbore binar cu n niveluri, numărul maxim de noduri din arbore
este:
a) n
b) 2⋅ n
c) 2n −1
d) 2n−1
2. (4p) Câte modalităţi de parcurgere a unui arbore binar există ?
a) 3
b) 2
c) 1
← d) 4
3.(4p) Parcurgerea în postordine presupune:
a) parcurgerea subarborelui stâng, a vârfului, apoi a subarborelui drept
b) parcurgrea vârfului, a subarborelui stâng după care a celui drept
c) parcurgerea subarborelui stâng, a subarborelui drept după care a
vârfului
d) vizitarea rădăcinii, a nodurilor de pe nivelul 1, a nodurilor de pe nivelul
doi etc.
4.(4p) Pentru arborele din figura alăturată,
parcuregerea în inordine este:
a) 1 2 3 4 5 6 7
b) 4 2 1 5 7 3 6
c) 1 2 4 3 5 7 6
d) 4 2 7 5 6 3 1
5.(4p) Pentru arborele din figura de mai sus, parcuregerea în preordine este:
a) 1 2 3 4 5 6 7
b) 4 2 1 5 7 3 6
c) 1 2 4 3 5 7 6
118
 d) 4 2 7 5 6 3 1
II. Raspundeti la urmatoarele intrebari (30puncte)
1. (6p) Care sunt etichetele nodurilor de tip frunză ale arborelui cu rădăcină, având 7
noduri, numerotate de la 1 la 7, şi următorul vector “de taţi”: (5,1,5,1,0,7,5)?
2. (6p) Câţi fraţi are nodul 1 din arborele cu rădăcină cu 7 noduri, numerotate de la 1 la
7, având următorul vector ”de taţi”: (5,1,5,1,0,7,5)?
3. (6p) Un arbore binar este un arbore cu rădăcină în care fiecare nod are cel mult 2
descendenţi direcţi (fii). Înălţimea unui arbore este reprezentată de numărul maxim de
muchii ale unui lanţ elementar ce uneşte rădăcina cu un vârf terminal (frunză).
Pentru un arbore binar cu exact 8 noduri, care este înălţimea minimă posibilă şi care
este numărul de noduri terminale (frunze) în acest caz?
4. (6p) Care sunt nodurile care au exact 2 descendenţi pentru un arbore cu rădăcină, cu 7
noduri, numerotate de la 1 la 7, dat de vectorul de ”taţi”: (3,3,0,1,2,2,4)?

5. (6p) Fie T un arbore cu rădăcină. Arborele are 8 noduri numerotate de la 1 la 8 şi este

descris  prin următorul vector „de taţi”: (3,5,0,3,3,5,5,5). Care este nodul cu cei mai
mulţi descendenţi direcţi (fii)? (6p.)

III. Scrieţi cate un program C++ pentru următoarele problem (40 puncte)
1. (2p) Se dă un număr natural n. Construiţi un arbore binar complet cu vârfurile
1,2,....n astfel încât în urma parcurgerii pe nivele să fie afişate valorile 1,2,....n.
Se vor afişa vectorii S şi D.
Exemplu:
n = 8
S = 2 4 6 8 0 0 0 0 0
D = 3 5 7 9 0 0 0 0 0

2. (2p) Se citeşte un arbore cu n vârfuri dat prin vectorul TATĂ. Să se afişeze

frunzele arborelui.
119
 Exemplu: Pentru vectorul de taţi 2 0 2 1 3 se vor afişa frunzele 4 şi 5.

Barem de corectare

NR. RĂSPUNS CORECT PUCTAJ

I. 2punct
1. c 0, 4 puncte
2. d 0, 4 puncte
3. c 0, 4 puncte
4. b 0, 4 puncte
5. c 0, 4 puncte
II. 3 puncte
1. Nodurile de tip frunza ale arborelui sunt 2,3,4 si 6 deoarece 0, 6 puncte
aceste noduri nu se gasesc in vectorul tata, ele nemaiavand
descendeti.
2. Nodul 1 din arbore are 2 frati si anume nodul 3 si nodul 7, 0, 6 puncte
deoarece aceste noduri au acelasi tata ca si nodul 1,
respectiv nodul 5

3. Inaltimea minima este 3 ,iar numarul de frunze este 4 0, 6 puncte

4. 2,3         0, 6 puncte

5. 1  2  3  4  5  6  7  8   , arborele este:    0, 6 puncte

 3  5  0  3  3  5  5  5
   Nodul cu cei mai mult descendenti
este 5.

III. 4 puncte

1. Citire/afisare din fisier 0, 5 puncte

Declarare variabile 0, 5 puncte
Parcurgerea pe nivele 0, 5 puncte
Corectitudinea algoritmului 0, 5 puncte
2. Citire/afisare 0, 5 puncte
Declarare variabile 0, 5 puncte
Afisare frunze 0, 5 puncte
Corectitudinea algoritmului 0, 5 puncte
oficiu 1 punct

TOTAL 10 PUNCTE

120
5.12. Probleme rezolvate
1) Se citește un arbore cu n vârfuri de la tastatură, dat prin vectorul de tați. 
a) Să se afișeze muchiile arborelui;
b) Să se construiscă și să se afișeze matricea de adiacență a arborelui. 
Ex: Pentru vectorul de tați: 2 0 2 1 3 se vor afla muchiile [1,2] [2,3] [1,4] [3,5] și matricea de
adiacență 
0 1 0 1 0 
1 0 1 0 0 
0 1 0 0 1 
1 0 0 0 0 
0 0 1 0 0 

#include<iostream>
using namespace std;
int n, T[100], a[100][100];

void afis( )
{ int i, j;
for(i=1;i<=n;i++)
{ for(j=1;j<=n;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}
}
int main( )
{ int i;
cin>>n;
for(i=1;i<=n;i++) cin>>T[i];
for(i=1;i<=n;i++)
if(T[i]!=0)
{ cout<<"["<<T[i]<<","<<i<<"] ";
a[i][T[i]]=a[T[i]][i]=1;
}
cout<<endl;
afis( );
return 0;
}

121
2. Din fișierul “[Link]” se citește un arbore cu n vârfuri dat prin vectorul muchiilor și apoi se
citește vârful rădăcină. Să se construiscă și să se afișeze vectorul de tați asociat arborelui.
Ex: Pentru un arbore cu 5 noduri, cu muchiile [1,2] [2,3] [1,4] [3,5] și rădăcina 2 se obține
vectorul de tați 2 0 2 1 3.

#include<iostream>
#include<fstream>
using namespace std;
int n, r, T[100], a[100][100], p[100];

void citire( )
{ int i, x, y;
ifstream f(“date,in”);
f>>n;
for(i=1;i<=n-1;i++)
{ f>>x>>y;
a[x][y]=a[y][x]=1;;
}
f>>r;
[Link] ( );
}

void BF(int r)
{ int s, d, i, x[100];
d=s=1;
x[1]=r; p[r]=1;
while (s<=d)
{ for(i=1;i<=n;i++)
if(a[x[s]][i]==1 &&p[i]==0)
{ d++; x[d]=i;
p[i]=1; T[i]=x[s];
}
s++;
}
}

int main( )
{ int i;
citire( );
BF(r);
for(i=1;i<=n;i++) cout<<T[i]<<" ";
return 0;
}

115
3. Se citește un arbore cu n vârfuri dat prin vectorul muchiilor și apoi se citește vârful
rădăcină. Să se calculeze și să se afișeze numărul de niveluri ale arborelui. 
Ex: Pentru un arbore cu 5 noduri și muchiile [1,2] [2,3] [1,4] [3,5] numărul de niveluri
este 3.

#include<iostream>
using namespace std;
int n, max=0, r, T[100], a[100][100], p[100];

void citire( )
{ int i, x, y;
cin>>n;
for(i=1;i<=n-1;i++)
{ cin>>x>>y;
a[x][y]=a[y][x]=1;;
}
cin>>r;
}

void DF(int r, int niv)

{ int i;
p[r]=1;
if(niv>max) max=niv;
for( i=1;i<=n;i++)
if(a[r][i] &&!p[i])
DF(i,niv+1);
}

int main( )
{ int i;
citire( );
DF(r,1);
cout<<max;
}

123
4. Scrieți un program care citește un arbore cu n vârfuri dat prin vectorul de tați. Să se afișeze în
fișierul “[Link]”:
a) gradele vârfurilor.
b) pentru fiecare vârf nivelul pe care se află (numerotarea nivelelor începe de la 0-rădăcina).
Ex: Pentru vectorul de tați 2 0 2 1 3 se vor afișa următorii vectori:
Gradele: 2 2 2 1 1
Nivelele: 1 0 1 2 2
#include<iostream>
#include<fstream>
using namespace std;
int n, r, T[100], D[100], p[100], niv[100];

void afis()
{ ofstream g(“[Link]”);
for(int i=1;i<=n;i++) g<<D[i]<<" ";
g<<endl;
for(i=1;i<=n;i++) g<<niv[i]<<" ";
[Link] ( );
}

void df(int r)
{ int i;
for(i=1;i<=n;i++)
if(T[i]==r && !p[i])
{ p[i]=1;
niv[i]=niv[r]+1;
df(i);
}
}

int main( )
{ int i;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>T[i];
if(T[i]!=0) { D[i]++;
D[T[i]]++;
}
}
for(i=1;i<=n;i++)
if(T[i]==0) r=i;
niv[r]=0;
df(r);
afis( );
return 0;
}

124
5. Se citește de la tastatură un arbore cu n vârfuri dat prin vectorul de tați și apoi un vârf r. Să se
afișeze vectorul de tați obținut prin mutarea rădăcinii arborelui în varful r. 
Ex: Pentru vectorul de tați 2 0 2 1 3 și nodul r=5 se va afișa vectorul 2 3 5 1 0. 

#include<iostream>
using namespace std;
int n, t[100], r, i;

void citire()
{ cin>>n;
for( i=1;i<=n;i++) cin>>t[i];
cin>>r;
}
void f(int r)
{ if (t[r]!=0) f(t[r]);
t[t[r]]=r;
}

void afisare ( )
{ for( i=1;i<=n;i++) cout<<t[i]<<" ";
}

int main()
{
citire ( );
f(r);
t[r]=0;
afisare ( );
return 0;
}

125
6. Din fișierul “[Link]” se citește un număr natural n reprezentând numărul de vârfuri ale unui
arbore binar și apoi vectorii S și D, ce reprezintă subarborele stâng respectiv subarborele
drept al arborelui. Se va afișa în fișierul “[Link]” următoarele:
a) parcurgerea arborelui în preordine, inordine și postordine;
b) parcurgerea arborelui pe nivele;
c) înălțimea arborelui (adâncimea).

Exemplu: 
“[Link]”
7 
2400700
3560000

Se va afișa:
“[Link]”
Preordine (RSD): 1 2 4 5 7 3 6
Inordine (SRD): 4 2 7 5 1 3 6
Postordine (SDR): 4 7 5 2 6 3 1
Pe nivele: 1 2 3 4 5 6 7
Adâncimea: 3

#include<fstream>
ușing namespace std;
ifstream f("[Link]");
ofstream g("[Link]");
int S[100], D[100], P[100], r, n, i, maxx;

void RSD(int n)
{
g<<n<<" ";
if (S[n]!=0) RSD(S[n]);
if (D[n]!=0) RSD(D[n]);
}

void SRD(int n)
{
if (S[n]!=0) SRD(S[n]);
g<<n<<" ";
if (D[n]!=0) SRD(D[n]);
}
126
void SDR(int n)
{
if (S[n]!=0) SDR(S[n]);
if (D[n]!=0) SDR(D[n]);
g<<n<<" ";
}

void BF(int r)
{
int x[100], i, j;
i=1; j=i;
x[1]=r;
while(i<=j)
{
if (S[x[i]]!=0) x[++j]=S[i];
if (D[x[i]]!=0) x[++j]=D[i];
i++;
}
for(i=1;i<=n;i++) g<<x[i]<<" ";
}

void adancime (int n, int niv)

{
if (niv>maxx) maxx=niv;
if (S[n]!=0) adancime(S[n],niv+1);
if (D[n]!=0) adancime(D[n],niv+1);
}

int main()
{
f>>n;
for(i=1;i<=n;i++) P[i]=0;
for(i=1;i<=n;i++)
{
f>>S[i];
P[S[i]]=1;
}
for(i=1;i<=n;i++)
{
f>>D[i];
P[D[i]]=1;
}
for(i=1;i<=n;i++)
if(P[i]==0) r=i;
g<<"Preordine: ";
RSD(r);
g<<endl<<"Inordine: ";
SRD(r);
g<<endl<<"Postordine: ";
SDR(r);
g<<endl<<"Pe nivele: ";
127
 BF(r);
g<<endl;
adancime(r,0);
g<<"Adancimea: ";
g<<maxx;
[Link]();
[Link]();
return 0;
}

7. Se dă un arbore binar cu n noduri prin vectorul de tați T și vectorul P ce reprezintă pozitia

descendentului: -1 pentru stânga, 1 pentru dreapta
Afișați vectorii de descendenți stânga S și descendenți dreapta D. 
Exemplu: 
"[Link]"
12 
0 1 1 2 2 3 4 4 5 6 6 11 (T) 
0 -1 1 -1 1 1 -1 1 1 -1 1 1 (P) 
"[Link]"
2 4 0 7 0 10 0 0 0 0 0 0 (S) 
3 5 6 8 9 11 0 0 0 0 12 0 (D)

#include <fstream>
ușing namespace std;
ifstream f("[Link]");
ofstream g("[Link]");
int i, n, S[100], D[100], T[100], P[100];

int main ( )
{
f>>n;
for(i=1;i<=n;i++) f>>T[i];
for(i=1;i<=n;i++) f>>P[i];
for(i=1;i<=n;i++)
{
if (T[i])
{
if (P[i]==-1) S[T[i]]=i;
if (P[i]==1) D[T[i]]=i;
}

}
for(i=1;i<=n;i++) g<<S[i]<<" ";
g<<endl;
for(i=1;i<=n;i++) g<<D[i]<<" ";
[Link] ( );
[Link] ( );
return 0;
}

128
8. Într-o firmă sunt n angajați, numerotați de la 1 la n, fiecare angajat având un șingur șef direct,
cu excepția directorului, care nu are șef. Ierarhia firmei este data printr-un vector de tip tată.
Fiecare angajat al firmei are un salariu dat printr-un număr natural. Angajații și șeful sunt
recompensați astfel: câștigul fiecărui salariat este egal cu salariul său la care se adaugă media
aritmetică a câștigurilor subordonaților săi direcți. Media aritmetică se rotunjește prin adaos la
un număr întreg (de exemplu 5.33 se rotunjește la 6). Angajații care nu au subordonați direcți
căștigă doar salariul. Calculați care este câștigul directorului firmei.
Exemplu: 
"[Link]" "[Link]"
8 (numarul de angajati)  14
4 3 0 3 2 1 2 1 (vectorul tata) 
2 6 4 3 7 3 1 5 (Sălariul fiecarui angajat) 

#include <fstream>
#include <cmath>
ușing namespace std;

ifstream f("[Link]");
ofstream g("[Link]");

int r, n, t[101], x[101], s[101];

int fii (int r)

{
int k=0;
for(int i=1;i<=n;i++) if(t[i]==r) k++;
return k;
}

int calcul (int v)

{
s[v]=0;
for(int i=1;i<=n;i++)
if(t[i]==v)
s[v]=s[v]+calcul(i);
if(fii(v)>0) return x[v]+ceil((float)s[v]/fii(v));
else return x[v];
}
int main ( )
{
f>>n;
for(int i=1;i<=n;i++)
{
f>>t[i];
if(t[i]==0) r=i;
}
for(int i=1;i<=n;i++) f>>x[i];
g<<calcul(r);
[Link] ( );
[Link] ( );
return 0;
}
129
 Concluzii

Lucrarea de faţă constituie prezentarea arborilor ca structuri arborescente , dar şi

noţiuni despre cazurile de echilibrare ale acestora.
Scopul lucrării este in primul rand didactic, aceasta realizând o prezentare a teoriei
aferente noţiunilor tratate, urmată la fiecare capitol de mai multe exemple aplicative.
Lucrarea se doreşte a fi un material foarte util în pregătirea elevilor pentru admiterea
in ciclul superior, profesorilor care predau disciplinele informatice şi celor care sunt pasionaţi
de programare la un anumit nivel. Deşi aceste noţiuni privind echilibrarea arborilor binari sunt
descrise şi prezentate foarte puţin in câteva lucrări de specialitate din mediul academic,
puţine sunt publicaţiile care oferă spaţiu şi exemple aplicative asociate.
În redactarea documentaţiei şi a aplicaţiilor am efectuat traduceri din limba engleză
din mai multe publicaţii straine, am căutat informaţii diverse şi am încercat sa prezint cât mai
bine cazurile prin care un arbore binar poate fi echilibrat folosind chei.
Teza este consacrată descrierii şi analizei structurilor arborescente care stau la baza
căutării în memoria principală. În ultimii ani, datorită popularităţii crescânde a aplicaţiilor
care utilizează structurile arborescente (cum ar fi căutare Web, procesarea imaginilor,
robotică), domeniul analizei acestor structuri a luat o mare amploare.O problemă de cercetare
actuală este dezvoltarea de modele potrivite pentru generarea datelor necesare măsurării
performanţelor structurilor arborescente.
Lucrarea este structurată după cum urmează:
În primul capitol am prezentat o introducere şi am argumentat imprtanţa temei
abordate. De asemeni am precizat care este locul structurilor arborescente în programa
scolară.
În capitolul 2 am descris arborii, ca structuri de date referindu-mă la arborele liber,
arborele partial, arborele cu rădăcină şi arborii oarecare.
Capitolul 3 este dedicat arborilor binari, aici am prezentat şi modurile de reprezentare
în memoria internă, implementarea statică şi dinamică şi metodele de parcurgere.
În capitolul 4 se regăsesc cazurile de echilibrare a arborilor, caracteristicile acestora,
definiţii, generalităţi. La sfârşitul acestui capitol am prezentat probleme specifice acestor
structuri în limbajul de programare C++.

130
 În a doua parte a lucrării am prezentat tehnologiile şi strategiile didactice cît şi
resursele didactice utile în predarea arborilor [Link] aici se regăsesc şi modele de
proiectare didactică.
În această secţiune vor fi prezentate: planificare calendaristică pentru clasa a XI-a, proiectul
unităţii de învăţare „Structuri arborescente”, proiect de activitate –lectie de dobândire de noi
cunoştinţe cu tema Arbori [Link] arborilor binari, proiect de activitate – lectie
de recapitulare şi sitematizare a cunoştinţelor cu tema Arbori binari, proiect de activitate –
test de evaluare a cunostinţelor cu tema Arbori binari
Pe parcursul lucrării am analizat un număr mare de metode de reprezentare ale
structurilor de date arborescente şi am acordat atenţie maximă pentru structurile de date care
evidenţiau particularităţi avantajoase scopurilor urmărite. Concluziile finale declară ferm
superioritatea uneia dintre structurile de date analizate, şi anume echilibrarea arborilor. În
lucrarea de faţă am dorit să evidenţiez pe lângă diversele aplicaţii ale structurilor arborescente
şi modul în care se aleg cele mai performante structuri arborescente pentru unele aplicaţii în
domenii conexe. Marele avantaj al utilizării unor structuri de date arborescente este acela că
facilitează regăsirea rapidă a unor submulţimi ale datelor reprezentate şi astfel, operaţiile se
implementează cu algoritmi care au un timp de execuţie deosebit de performant. Datorită
avantajelor lor, unele structuri arborescente, într-o varietate foarte mare, sunt generatoare de
metode moderne şi foarte utilizate la reprezentarea şi arhivarea datelor. Pentru a le oferi
puncte de sprijin celor care doresc să utilizeze aceste structuri de date arborescente, după
prezentarea acestora am adăugat probleme rezolvate pe baza structurilor de date analizate.
Eficienţa soluţiilor problemelor prezentate la finalul fiecărui capitol este mărită prin alegerea
unei reprezentări corespunzătoare a datelor. O problemă de cercetare actuală este dezvoltarea
de modele potrivite pentru generarea datelor necesare măsurării performanţelor structurilor
arborescente. În final, menţionăm că lucrarea cuprinde numeroase figuri şi algoritmi descrişi
în pseudocod sau implementaţi în limbajulC++.

131
 Bibliografie

1. BERGE C- Graphs, 2. North-Holland, Auflage, 1985

2. BONDY J. A , U.S.R. MURTY- Graph Theory With Applications, North-Holland ,
Elsevier Science Ltd/ 1976
3. CIUREA C – Structuri de date - note de curs - Departamentul de informatică şi
Cibernetică Economică ASE Bucureşti
4. DUTĂ L. , PASCALE L. - Tehnici de programare si metode de alocare dinamica,
Matrix Rom , Bucuresti, 2010
5. GEORGESCU, H. - Tehnici de programare, Ed. Universităţii, Bucureşti, 2005
6. IGNAT I, IGNAT C.L - Structuri de date, Îndrumător de lucrări de laborator, Ed. UT.
Pres, Cluj Napoca, 2001
7. IVAȘC C, PRUNĂ M – Bazele informaticii (Grafuri și Elemente de combinatorică).
Manual de informatică pentu clasa a X-a, București, Editura Petrion, 1995
8. MASALAGIU C, ASIMINOAEI I - Didactica predării informaticii, Iaşi, Ed.
Polirom, 2004
9. MILOȘESCU M – Informatică intensiv: manual pentru clasa a XI-a, București,
Editura Didactică și Pedagogică, 2006
10. OPRESCU D, BEJAN IENULESCU L, PĂTRȘCU V - Informatică: manual pentru
clasa a XI-a, București , Editura Niculescu ABC SRL, 2002
11. PETRE C, POPA D, CRĂCIUNOIU Şt, ILIESCU C - Metodica predării informaticii
şi tehnologiei informaţiei, Craiova, Editura ARVES, 2002
12. POPESCU D. R - Combinatorică şi teoria grafurilor, Bucureşti, Editura Societatea de
stiinte matematice din Romania, 2005
13. STOILESCU D - Culegere de C++, Ed. Radial, Galati,1998
14. UNGUREANU M - Structuri de date si algoritmi, [Link] Rom,2012
15. TUDOR S - Informatică manual pentru clasa a XI-a, București, Editura L&S
INFOMAT, 2002
16. [Link]
17. [Link]
18. [Link]

132
19. [Link]
%20structuri%20date/[Link]
20. [Link]

21. [Link]

22. [Link]
data-structure/c-program-to-implement-avl-tree-its-operations/

23. [Link]

133