Ministerul Educatiei si Cercetarii

Colegiul Tehnic David Praporgescu

Municipiul Turnu Magurele

Judetul Teleorman

Arbori binari,parcurgerea arborilor binari

Profesor indrumator : prof. Paraschiv Niculina

An scolar 2004-2005

REFERAT

ABSOLVENT: .....................

TITLUL LUCRARII: .................

Calitatea exprimarii in termeni de specialitate:

pfoarte buna

pbuna

psatisfacatoare

pnesatisfacatoare

Contributia personala:

pfoarte bine

pbine

psatisfacator

pnesatisfacator

Observatii: ..................... ............................

Concluzii: ...................... ..........................

REFERENT, APRECIERE FINALA,

Data ___/___/_

Cuprins

1.Istoricul limbajului Turbo Pascal

2.Vocabularul limbajului Turbo Pascal

3.Operatii de intrare si iesire

4.Reprezentarea operatiilor de citire si scriere cu ajutorul fisierelor de intrare si iesire

5.Procedurile Read/Readln ;Write/Writeln

6.Structuri de control

7.Instructiunea compusa

8.Structuri repetitive

9.Arbori

10.Arbori binari

11.Reprezentarea arborilor binari

12.Listingul

13.Rezultatele obtinute dupa rularea programului

I. LIMBAJUL TURBO PASCAL

I.1.Notiuni introductive

Limbajul Turbo Pascal a aparut la inceputul anilor '70 si a fost elaborat de matematicianul N. Wirth.

Initial limbajul a fost conceput pentru predarea sistematica a disciplinei de programare a calculatoarelor(structuirile clasice din programarea structurala au fost transformate in instructiuni).

Cu timpul limbajul a inceput sa fie folosit si in activitatea practica de programare a calculatoarelor.Un rol fundamental pentru acestea l-a avut firma americana Borland,care pe langa instructiunile clasice ale limbajului contine si multe altele.

Un mare avantaj al acestui limbaj este acela ca utilizatorul are posibilitatea sa-si declare propriile tipuri de date.

Ultimele versiuni ale limbajului permit si realizarea programarii pe obiecte.

Observatii :

Orice cuvant poate fi scris cu litere mici sau mari deoarece limbajul Turbo Pascal nu face diferente ;

-In versiunea Turbo prima linie a programului poate lipsi(desi nu este recomandabil acest lucru,din ratiuni de ordine) ;

Plasarea cuvintelor pe linie si numarul de spatiu dintre ele sunt la alegerea programatorului(putem sa scriem intreg programul pe o singura linie insa este bine ca programul sa fie scris in asa fel incat sa fie usor de inteles).

Orice limbaj de programare se caracterizeaza prin sintaxa si semantica ,sintaxa limbajului este data de totalitatea regurilor de scriere corecta(in sensul acceptarii sale de programul traducator(compilator)care are rol de a converti programul in cod masina pentru a fi executat).

Prin semantica unui limbaj intelegem ce anume realizeaza fiecare instructiune a sa.Sintaxa formalizata perfect din punct de vedere matematic dar nu acelasi lucru se intampla cu semantica.Sintaxa poate fi deschisa cu ajutorul diagramelor de sintaxa,in esenta intr-o diagrama de sintaxa putem inlocui urmatoarele simboluri grafice .

Vocabularul limbajului Pascal

Elementele care constituie vocabularul acestor limbaje sunt:

Setul de caractere,identificatori,operatori,separatori,comentarii

Setul de caractere

Limbajul Pascal utilizeaza literele alfabetului englez mari si mici( A.Z,a.z) , cifrele arabe (0.9) si caractere speciale( ,  : ; . < = > = <>  _ + - * / ( )[ ] )

Limbajul Pascal nu face distinctia intre literele majuscule si cele

minuscule (de exemplu:Da,da,dA,DA reprezinta aceeasi informatie in limbajul Pascal).

Identificatori

Prin identificatori intelegem o succesiune de litere,cifre si caracterul_(underscore)

exemple

a aha vali t SORin

xYb    InDex auxil tlt2t3 sTeLiAN

x_1    numitor Andr eMil Ion_sOfIA

Exista o serie de identificatori speciali , numiti  cuvinte cheie care nu pot fi folositi decat in scopul in care au fost creati. Ex: begin, end,or,and,array, procedure, function, set, file etc.

Operatori,separatori,comentarii

Cu ajutorul simbolurilor speciale se definesc: operatori de atribuire, operatori de indici, comentariu.

Tipuri de date standard

Datele vehiculate in dialogul om-calculator,fie ca sunt constante,fieca sunt variabile, pot fi de urmatoarele cinci tipuri de baza:

-tipul intreg (numere intregi),

-tipul real(numere reale),

-tipul character, ,

-tipul boolean(logic),

-tipul pointer

- tipul enumerare.

-tipul subdomeniu.

Aceste categorii de date sunt numite tipuri simple , dar exista tipurile structurate ( tablou, sir de caractere,

Constante

Asa cum am afirmat,constantele sunt informatii care se autodefinesc, spatiul de memorie necesar pastrarii lor fiind rezervat si gestionat de mediul de programare.

Constante numerice de tip intreg sunt numere intergi in sensul matematic cunoscut.

Exemple

-0

3 +3 -3

Limbajul Pascal standard accepta numere intregi din intervalul

Definirea constantelor

Cind o anume valoare apare in mod repetat este recomandabil a o 'boteza',mai ales in cazul in care ea are o scriere'lunga'.De pilda , in loc sa folosim in mod repetat constanta 312.054973 o definim sub un nume iar la fiecare aparitie a acestei valori vom scrie numele ce i

l-am dat.Definirea constantelor se face conform sintaxei :

const nume_variabila=valoare ;

5.1.Constante numerice de tip real

Numerele reale se scriu apelind la exponenti ai bazei(asa numita scriere stintifica a numerelor reale).De pilda, putem reprezenta constanta reala 19.55 in nenumarate moduri:

0.1955E2    0.01955E3 1955E-2

De aici ideea de scriere in virgula mobila a numerelor reale.Din infinitatea manierelor de scriere;cea evidentiata se numeste forma normala,unica pentru orice constanta.Ea este caracterizata de faptul ca se reprezinta printr-un numar sub unitar(0.1955)cu cifra zecilor (prima dupa marca zecimala) diferita de zero.Reprezentarea in calculator a constantelor reale se face pornind de la formula normala:

mantisa E exponent

iar la tiparire, in lipsa informatiilor pentru formatare este utilizata forma normala.

5.2.Constante logice(booleene)

Acestea sunt, de fapt, constante simbolice,fiind desemnate prin cuvintele false - corespunzatoare valorii logice fals(desemnata prin F in capitolul doi) si true - corespunzatoare valorii logice adevar (marcata cu A in acelasi capitol).

Reperezentarea in memoria calculatorului se face prin completarea cu valoarea 1 a zonei de memorie rezervate in cazul valorii logice adevar si,

respectiv , cu 0 in cazul valorii logice fals (de aici relatia flse <true).

5.3.Constante de tip alfanumeric

Aceasta categorie de constante reprezinta succesiuni de caractere ale limbajului (elemente din setul de caractere)avind sintaxa : 'succesiune de caractere'

Pentru a introduce caracterul apostrof (intr-o constanta alfanumerica Pascal),

se procedeaza ca in exemplul de mai jos:

'Emilia este ' serioasa' '

echivalent cu sirul

Emilia este 'serioasa'

6.Variabile

Ca si constantele,variabilele pot fi de tipurile amintite in paragraful anterior.Ele sunt desemnate prin identificatori alesi de programator,fiind recomandabil a fi sugestivi.In programe,orice variabila are un domeniu in care ia valori si pentru o utilizare corecta trebuie sa primeasca valori din domeniul respectiv.

Definirea variabilelor: Variabilele se declara utilizind sintaxa :

Var nume_variabila : tip_variabila ;

6.1.Variabilele numerice

Definitia acestora se face apelind in simbolurile integer,byte,shortint,word,longint pentru tipul intreg si real,single,double,extended pe tipul real,prin care sunt evidentiate domeniile de valori standard posibile pentru variabile.Tipurile single ,double , extende necesita coprocesor matematic.

6.2.Variabilele alfanumerice

Variabilele alfanumerice pot fi de tip caracter (evidentiate prin terminalul char si reprezentate pe un octet)sau de tip sir de caractere (marcate prin terminalul string in Pascal fiind reprezentate prin numarul de caractere necesare stocari sirului la care se adauga un caracter de control. In pascal acest caracter se adauga in fata si reprezinta numarul de caractere.

Exemplu :

Daca avem segventele

P :string ;

P:='Emi';

Atunci rezulta

P[1]='E' p[2]='m' p[3]='i'

P[0]=3

6.3.Variabile logice

Aceasta categorie de variabile este pusa in evidenta prin simbolul boolean.

Exemplu

Var B: boolean.

7. Tipuri ordinale definite de utilizator

Tipurile studiate anterior sunt numite tipuri standard.Lor le vom adauga,in cele ce urmeaza,alte categorii de tipuri pe care si le poate defini utilizatorul.Avem in vedere tipurile enumerat si interval(subdomeniu).

Definitiile lor trebuie plasate in zona de declaratii,inaintea sectiunii dedicate variabilelor.

Tipul enumerat

Definitia sintactica a acestui tip este urmatoarea:

type nume_tip=(val1,val2,,vn);

Exemple

type

zi_libera=(sambata,duminica);

logic=(fals,adevarat) ;

medalie=(aur,argint,bronz) ;

In legatura cu modul de lucru cu acest tip de date(tipul enumerat)sunt necesare unele precizari :

- tipul de variabila si cel al valorii ce i se atribuie acesteia trebuie sa fie acelasi ;

- in cazul declararii mai multor variabile de tip enumerat multimile de valori trebuie sa fie disjuncte.De exemplu,daca am declara tipurile :

type

fruct=(copt,verde) ;

culoare=(alb,verde,galben) ;

nu ar fi corect deoarecevaloarea verde este element comun al celor doua multimi de valori enumerate in definirea tipurilor fruct si culoare ;

-valorile enumerate sunt considerate a avea rangurile(numerele de ordine)0,1,2.. ;

- asupra tipurilor definite de utilizator nu se pot aplica operatii aritmetice.In schimb,valorile precizate sunt considerate a fi in relatie strict crescatoare:

ca atare , pentru exemplul culoare de la punctul (c) se considera ca:

alb < verde< galben

ceea ce este in concordanta cu rangurile lor (0<1<2) ;

- exista trei functii standard Pascal aplicabile tipurilor ordinale definite de utilizator : pred (care da predecesorul unui element), succ (care da succesorul unui element), ord (returneaza rangul unui element).

- datorita ordonarii la care sunt supuse valorile,este posibila utilizarea operatorilor rationali in lucrul cu tipurile scalare definite de utilizator. Pentru exemplificare, fie tipul litera definit astfel :

type litera=(A,B,C,D,E,F) ;

var p,q :litera ;

In acest caz este corect sa scriem, de exemplu :

p:=B ;

q:=A ;

si apoi de a le utiliza in comparatii.

7.2Tipul interval

Acest tip de date apare destul de des in aplicatii. Putem sa ne referim de exemplu, la numere naturale sau intregi dintr-un anume interval, apeland la cele doua margini :inferioara si superioara.Definitia sintactica pentru aceasta categorie de informatii este :

Exemple :

1) type nota=1..10 ;

intreg_pozitiv=0..MaxInt ;

var x,y:nota;

z,t:intreg_pozitiv ;

2) var x,y :1..10 ;

z,t :0..MaxInt ;

Cele doua exemple reprezinta practic acelasi lucru,amandoua definind patru variabile de tip interval.

Expresii

Expresiile sunt constructii algoritmice destinate calculelor algoritmice,logice respectiv operarii pe siruri de caractere.

Elementele constitutive ale oricarei expresii sunt constantele, variabilele si functiile, cu posibilitatea utilizarii parantezelor rotunde.

Operatorii utilizati in construirea de expresii sunt de sapte tipuri :

aritmetici, logici, relationali, de tip sir, operatii la nivel de bit, de tip multime si de tip adresa.

O clasificare uzuala a operatorilor este facuta tinand cont de prioritatile acestora in evaluarea expresiilor.

In tabel este data lista acestora in ordine descrescatoare a prioritatilor.

Facem precizarea ca atunci cand sunt folosite parantezele,

acestea sunt luate in considerare la inceput, de la cea mai interioara spre cea mai exterioara, cu respectarea prioritatilor (prin operatori unari intelegem pe cei cu un singur operand). Cand doi operatori consecutivi au aceeasi prioritate ei se efectueaza de la stanga la dreapta.

De exemplu :

a/b*c

se evalueaza facand a / b si apoi rezultatul inmultit cu c . Pentru inlaturarea oricaror dubii, putem scrie (a/b)*c.

In evaluarea expresiilor este foarte important sa stim cum se procedeaza in stabilirea tipului rezultatului obtinut ca efect al evaluarii.

Sa observam ca operatorul and este "si"logic,respectiv, "si" pe biti, in functie de  "contextul" in care este utilizat.

Exemple de expresii si evaluarile rezultate :

41 div 8 5

12mod52 12and224

2shl6128

128shr48

123xor12

Instructiunea repeat/until, implementeaza in limbajul Pascal,permite executia unei multimi de instructiuni pana la indeplinirea unei conditii.

Instructiunea do/while,specifica limbajului C, permite executia unei instructiuni simple sau a unei instructiuni compuse atata timp cat o anumita conditie este indeplinita.

Instructiunea For

In cazul instructiunilor while cu numarul de reluari predeterminabil se poate apela la o variabila de tip intreg numita,variabila de control a ciclului,cu evolutia de la o valoare initiala vi la una finala vf.Evolutia poate fi crescatoare (vi,vi+1,vi+2,,vf ; ramura cu to in diagrama sintactica ) sau descrescatoare (vi,vi-1,vi-2,,vf ; ramura cudownto a diagramei). In acest mod s-a ajuns la o noua structura repetitiva ,numita for, a carei descriere este :

for variabila :=valoare_initiala_mica to valoare_finala_mare do instructiune;

sau

for variabila := valoare_initiala_mare downto val_finala_mica do instructiune;

Se numeste graf neorientat o pereche ordonata de multimi(X , U),X fiind o multime finita si nevida de elemente numite noduri sau varfuri,iar U o multime de perechi neordonate(submultimi cu doua elemente) din X,numite muchii.

Vom nota cu G=(X,U) un graf neorientat.Multimea X se numeste multimea nodurilor sau varfurilor grafului G iar U se numeste multimea muchiilor.o muchie uIU este o submultime de varfuri distincte din X si se noteaza u=[x,y].Varfurile x si y sunt adiacente in G iar despre u si x ca sunt incidente la fel ca si u si y.Se mai spune ca x si y sunt extremitatile muchiei u.

Un graf partial al grafului G=(X,U) este un graf G₁ =(X,V) astefel incat V U,adica G₁ are aceeasi multime de varfuri ca G iar multimea de muchii V este chiar U sau submultime a acesteia.Cu alte cuvinte un graf partial al unui graf se obtine pastrand aceeasi multime de varfuri si eliminand o parte din muchii.

Un subgraf al unui graf G=(X,U) este un graf H=(Y,V) astfel incat Y X iar V contine toate muchiile din U care au ambele extremitati in Y.Spunem ca subgraful H este inclus sau generat de multimea de varfuri Y.

Se numeste lant in g succesiunea de varfuri L=[x_i1 ,x_i2,,x_ik] cu proprietatea ca orice doua varfuri consecutive din L sunt adiacente,adica [x_i1,x_i2],[ x_i2,x _i3],,[ x_ik-1, x_ik]IU.Varfurile x_i1 si x_i2 se numesc extremitatile lantului iar numarul de muchii ce apar in L se numeste lungimea lantului L.Daca varfurile x_i1 ,x_i2,,x_ik sunt diferite doua cate doua atunci lantul L se numeste elementar.In caz contrar lantul este neelementar.

Se numeste ciclu in G un lant L pentru care x_i1= x_i2 si toate muchiile [x_i1 ,x_i2],[ x_i2, x _i3],.,[ x_ik-1, x_ik] sunt diferite doua cate doua.

Se numeste ciclu elementar un ciclu care are proprietatea ca oricare doua varfuri ale sale,cu exceptia primului si a ultimului sunt diferite doua cate doua.Doua cicluri C si C' sunt egale daca muchiile lor induc acelasi graf partial al subgrafului generat de varfurile ce apartin lui C,respectiv C'.Un ciclu se numeste par daca lungimea sa este para si impar in caz contrar.

Un graf G se numeste conex daca pentru oricare doua varfuri x si y diferite ale sale exista un lant care le leaga.Se numeste componenta conexa a grafului C=(X₁,U₁),conex,al lui G care are proprietatea ca nu exista nici un lant care sa lege un varf din X₁ cu un varf din X-X₁.

Arbori

In clasa grafurilor conexe,arborii reprezinta grafurile cele mai simple(ca structura)si, de asemenea,cele mai frecvent utilizate in practica.De studiul lor s-au ocupat matematicienii si fizicieni de seama :Cayley a studiat arborii pentru aplicatiile lor in chimia organica,iar Kirchhoff a studiat aceasta categorie de grafuri pornind de la studiul retelelor electrice.Termenul de arbore a fost introdus de Cayley in 1857 plecand de la o analogie botanica.

Se numeste arbore un graf conex si fara cicluri.

In figura de mai jos este desenat un arbore.Se observa ca oricum am elimina o muchie graful isi pierde proprietatea de conexitate,si oriunde am adauga o muchie apare un ciclu iar acest lucru este valabil in orice arbore.

Teorema :Fie un graf G=(X,U).Urmatoarele afirmatii sunt echivalente :

G este arbore ;

G este un graf conex,minimal cu proprietatea ca eliminand o muchie oarecare se obtine un graf neconex ;

G este un graf fara cicluri,maximal cu proprietatea ca daca se adauga o muchie se obtine un graf care are macar un ciclu.

Ca sa demonstram teorema enuntata mai sus este suficient sa parcurgem urmatoarele implicatii :1)T T T3) si 3) T1).Dupa ce vom demonstra ce ne-am propus,vom putea scrie :2) 3), si prin tranzitivitatea relayiei de echivalenta obtinem si 2)

1) T G este conex si fara cicluri

G este conex minimal cu aceasta proprietate

Se observa ca proprietatea de conexitate este comuna ipotezei si concluziei.Presupunem prin reducere la absurd ca in U exista o muchie u=[x,y]prin a carei eliminare sa se obtina un graf G₁ care este totusi conex.

Rezulta din conexitatea lui G₁ ca in acest graf exista un lant intre oricare doua varfuri,deci si intre x si y,fie acesta L_x,y.Din acesta putem obtine un lant elementar L'_x,y.Daca adaugam muchia eliminata na situam din nou in G si in plus se obtine un ciclu,ceea ce este absurd.Urmeaza ca in G este intr-adevar minimal proprietatea de conexitate.

2) T G este conex si minimal cu aceasta proprietate

G este conex si fara cicluri

Din nou proprietatea de conexitate este comuna ipotezei si concluziei. Mai ramane sa demonstram ca G este fara cicluri.Presupunem prin reducere la absurd ca in G exista un ciclu C=[ x₁ ,x₂,,x_k, x₁].Eliminam muchia[x₁ ,x₂]si argumentam ca se obtine un graf G₁ tot conex.Intr-adevar pentru ca in G este conex intre orice doua varfuri exista un lant.In lanturile care folosesc muchia[x₁ ,x₂]doar acestea sunt afectate de eliminarea muchiei)vom inlocui aceasta muchie cu lantul[x₂,x₃,,x_k,x₁].Urmeaza deci ca G₁ este intr-adevar conex,ceea ce vine in contradictie cu ipoteza.Rezulta ca presupunerea facuta a fost falsa si deci este fara cicluri.

1)T G este conex si fara cicluri

G este fara cicluri si maximal cu aceasta proprietate

Proprietatea lui G de a fi fara cicluri este comuna ipotezei si concluziei.Deoarece G este conex,rezulta ca intre oricare doua varfuri distincte si neadiacente x si y exista un lant,din el construim un lant elementar care sa lege x si y.Daca am adauga muchia[x,y]atunci ar apare un ciclu,deci G este fara cicluri,maximal.

3)T G este fara cicluri si maximal cu aceasta proprietate

G este conex si fara cicluri

Din nou ipoteza si concluzia au o parte comuna.Mai ramane sa demonstram conexitatea lui G.Fie x si y doua varfuri neadiacente in G.Daca am adauga muchia[x,y] am obtine conform ipotezei un graf care contine un ciclu C (in care apar,evident varfurile x si y),C=[x,y,t,,x].Eliminand muchia[x,y]]ne plasam din nou in G si,in plus,din ciclul C putem evitdentia un lant L=[y,t,,x]cre leaga cele doua varfuri x si y.In concluzie,graful G este conex,demonstratia teoremei este acum terminata.

Definitie :

Fie G un graf.Un graf partial H al sau care in plus este si arbore se numeste arbore partial.

Corolar :

Un graf G=(X,U) contine un arbore partial daca si numai daca G este conex.

Demonstratie :

I.Presupunem ca G contine un arbore partial H=(X,V),atunci,cum H este conex(fiind arbore),pentru G el este graf partial.Rezulta ca prin adaugarea la H a muchiilor din UV pentru a reconstrui pe G din H,proprietatea de conexitate se pastreaza.Deci G este conex.

II.Daca G este conex atunci exista doua cazuri :

G este arbore,caz in care H=G.

2.G nu este arbore.Rezulta ca el contine cicluri,deci exista in G macar un ciclu C.Fie o muchie u=[x,y] a acestui ciclu.Prin eliminarea muchiei u, proprietatea de conexitate se pastreaza.Se obtine astfel un graf G₁.Daca G₁ este arbore,atunci H=G₁ ,daca nu,procedam similar cu G₁ .Dupa un numar finit de pasi(la fiecare pas se elimina o muchie),obtinem arborele partial cautat H.

Propozitia 1.Orice arbore H=(X,V) cu n 2 varfuri contine cel putin doua varfuri terminale.

Demonstratie :Presupunem prin absurd ca exista un arbore H cu n 2 varfuri si care contine cel mult un varf terminal,adica un varf al carui grad este 1.Alegem in H un lant elementar de lungime maxima(care contine numarul maxim de muchii posibil) ;fie acesta L=[ x₁,x₂,,x_k].Rezulta ca cel mult o extremitate este de gradul 1,deci cel putin una din extremitati are gradul cel putin 2 ;fie aceasta x₁.Mai exista in H macar un varf in afara de x₂ cu care x₁ este adiacent ;fie z unul din ele.Daca z nu ar apartine lantului L,am deduce ca L ar mai putea fi prelungit cu macar o muchie,contradictie.

Urmeaza deci ca z este lantul L,L=[ x₁,x₂,..,z,,x_k].Din acest lant am putea construi un ciclu C=[ x₁,x₂,..,z, x₁],ceea ce este absurd.Contradictia privine din presupunerea existentei a cel mai mult unui varf terminal.Acum demonstratia este terminata.

Propozitia 2.Orice arbore cu n varfuri are n-1 muchii.

Demonstratie:Facem demonstratia prin inductie dupa n.Pentru n=1,exista un singur arbore si el nu are muchii,deci numarul sau de muchii este 1-1=0.Presupunem proprietatea din enunt adevarata pentru orice arbore cu n varfuri si s-o demonstram pentru arborii cu n+1 varfuri.

Fie H un arbore cu n+1 varfuri.Conform propozitiei anterioare,rezulta ca exista in H un varf terminal ;fie acesta x.Eliminand din H varful x impreuna cu muchia incidenta cu el,obtinem un arbore H₁ cu n varfuri(intr-adevar H₁ este conex si fara cicluri).Pentru el aplicam ipoteza inductiva(el avand n varfuri)si deducem ca H₁ are (n-1)-1=n=(n+1)-1 muchii,ceea ce voiam sa demonstram.

Din cele doua etape ale inductiei,rezulta ca afirmatia din enunt este demonstrata.Ne propunem sa vedem cum rezolvam algoritmic unele probleme legate de arbori.O prima problema este aceea a verificarii daca un graf este arbore.Verificam mai intai daca el este conex,folosind,de exemplu una din metodele de parcurgere.Daca el este conex,pentru a fi arbore ar fi suficient si necesar ca graful sa aiba n-1 muchii,lucru usor de verificat chiar inainte de verificarea conexitatii.O alta problema interesanta aici este aceea a verificarii daca un graf este fara cicluri.

Definitie:Un graf G=(X,U)care nu contine cicluri se numeste acilic.

Algoritmul pe care il propunem se bazeaza pe faptul ca reconstruim multimea X de varfuri,plecand initial de la extremitatile primei muchii.Se adauga la X noi varfuri adiacente cu varfuri deja adaugate anterior la X.Daca in tentativa de a cauta asemenea varfuri,gasim unul in X care este adiacent cu un varf care este de asemenea in X,deducem usor ca am depistat existenta unui ciclu si ne oprim.

Daca nu gasim nici o muchie care sa aiba o extremitate in X si o extremitate in afara lui X,se adauga la X extremitatile unei muchii oarecare,neutilizate inca.Cautarea varfurilor,pentru a le adauga in X,o facem deci printre extremitatile muchiilor grafului.Se porneste initial cu multimea V a indicilor muchiilor grafului,exceptand prima muchie pe care o folosim pentru initializarea multimii X.Pe masura ce prelucram anumite muchii(adaugand la X o extremitate sau chiar pe amandoua),scoatem din V indicii lor.Dam in continuare acest algoritm scris in pseudocod si presupunem ca muchiile grafului sunt date in vectorul u.

Pass 1. aciclic :=true ;(daca vom descoperi ca G=(x,u) contine cicluri,vom schimba valoarea variabilei aciclic in false)

X=;(punem in X extremitatile primei muchii)

V= ;(initializam V cu multimea vida)

Pass 2. pentru i:=2,m executa V:=V (punem in V indicii tuturor muchiilor exceptand 1)

Pass 3. atata timp cat(aciclic=true)and(V ) executa

g:=false;(se foloseste pentru a testa daca am gasit o muvhie cu o extremitate in X)

pentru j:=2,m executa(determina prima muchie care are cel putin o extremitate in X)

daca jIV atunci x1:=u[j].x;y1:=u[j].y;

daca(x1IX)or(y1IX)atunci g:=true

break;

daca g=false atunci determina prima muchie j din V

X:=X

V:=V

astfel,daca (x1IX) and(y1IX) atunci aciclic:=false;(G are cicluri)

astfel determina extremitatea t a muchiei j care nu este in X

X:=X ;(adaugam t la X)

V:=V(scoatem muchia j din V)

Pass 4.daca aciclic=true atunci scrie 'graf aciclic' astfel scrie 'graful contine cicluri'.

Arbori binari

Definitie,Reprezentare,Parcurgere

Structurile arborescente reprezinta structuri neliniare de date cu multe aplicatii in programareqa si utilizarea calculatoarelor.Intr-un limbaj simplist,structurile arborescente exprima relatii de ramnificare intre noduri,asemanatoare configuratiei arborilor din natura cu deosebirea ca,in informatica in mod traditional,arborii cresc in jos.

Se numeste arborescenta un arbore care are un varf special numit radacina iar celelalte noduri pot fi repartizate in m multimi disjuncte x₁,x₂,..,x_m,m 0,astfel incat fiecare din aceste multimi exista un nod adiacent cu radacina iar subgrafurile generate de acestea sunt la randul lor arborescente.In particular,o arborescenta cu un singur nod este formata doar din nodul radacina.

Daca ordinea relativa a arborescentelor generate de multimile x₁,x₂,..,x_m din definitie are importanta,arborescenta se numeste arbore ordonat.In reprezentatea grafica a unei arborescente nodurile se deseneaza pe nivele,astfel :-radacina se afla pe primul nivel

-varfurile adiacente cu radacina pe urmatorul nivel,si asa mai departe.

Exemple de arbori ordonati :

nnni

Nodurile adiacente cu radacina-care se deseneaza pe nivelul urmator se numesc descendentii radacinii.In mod analog,in fiecare arbore ordonat a carui radacina este un nod aflat pe un nivel urmator,se numesc descendentii sai.Descendentii aceluiasi nod se mai numesc si frati.In desenul 1 nodurile b si c sunt frati si tot frati sunt si nodurile d,e si f.Daca un nod x este descendentul altui nod y,il numim pe acesta din urma parintele nodului x.

Folosim termenii descendent si parinte pentru a exprima relatii intre noduri aflate pe nivele consecutive in reprezentarea vizuala a arborilor.Terminologia utilizata in structurile arborescente include chiar cuvinte ca fiu,tata,frati,unchi,veri,strabunic,cu inteles similar celui din vorbirea curenta pentru noduri aflate pe diversele nivele.Prezentam ca exemplu de utilizare a acestei structuri de date modalitatea de organizare arborescenta a software-ului unui calculator utilizata de sisteme de operare ca ms-dod,unix si altele.

De asemenea observam ca orice tablou poate fi privit ca un caz special de structura arborescenta.In figura 3 avem un asemenea exemplu :

Un arbore binar este o multime finita de noduri care este fie vida,fie reprezinta un arbore ordonat in care fieacre nod are cel mult doi descendenti.Din definitie rezulta ca un arbore binar contine cel mult doi sub-arbori binari,pe care ii numim sub-arbore stang,respectiv sub-arbore drept.Ei se obtin deci prin suprimarea radacinii si a muchiilor incidente cu aceasta.Oricare din ei poate sa fie vid.Daca arborele binar este format dintr-un singur nod,atunci ambii subsrbori sunt vizi.

Sa observam ca un arbore nu reprezinta un caz particular de arbore,de exemplu,arborii binari din figurile 3 si 4 sunt distincti(in primul caz radacina are subarborele drept vid,iar in al doilea caz radacina are subarborele drept nevid),desi ca arbori ei sunt identici.

Un nod fara descendenti se numeste nod terminal sau frunza.Vom numerota incepand cu 0,nivelele nodurilor intr-un arbore binar.Astfel in figura 5 nodul 1 se gaseste pe nivelul 0,nodurile 2 si 3 se gasesc pe nivelul 1 si asa mai departe.

Un arbore binar in care fiecare nod care nu este terminal are exact doi descendenti se numeste arbore binar complet.Arborele binar din figura 5 este complet.

Propozitie.Un arbore binar complet care are n noduri terminale,toate situate pe acelasi nivel,are in total 2n-1 noduri.

Demonstratie.Vom arata mai intai ca n=2^r,unde r este ultimul nivel si anume cel terminal.Demonstram prin inductie dupa numarul nivelului ca in arborele binar din ipoteza,pe nivelul k se gaseste 2^k noduri,unde k este mai mic sau egal decat numarul de ordine al ultimului nivel de arbore.Intr-adevar pe nivelul 0 se gaseste doar radacina,deci 2⁰=1.Presupunem acum ca pe nivelul k se gasesc 2^k noduri si sa demonstram ca pe nivelul k+1 se gasesc 2^k+1 noduri.Intr-adevar,daca nivelul k+1 apartine arborelui,atunci nodurile de pe acest nivel sunt doua cate doua descendente ale unor noduri de pe nivelul k,nivel pe care sunt conform ipotezei inductive,2^k noduri.

Prin urmare,numarul total al nodurilor de pe nivelul k+1 este de 2*2^k=2^k+i.Rezulta ca pe nivelul r (ultim) sunt 2^r noduri.Calculam acum numarul total de noduri din arbore:

2⁰+2¹++2^r=2^r+1-1=2*2^r-1=2n-1.

Corolar.Un arbore complet are un numar impar de noduri.

Reprezentarea Arborilor Binari

Pentru reprezentarea arborilor binari exista mai multe moduri de reprezentare :

a)Reprezentarea standard :se specifica radacina rad si,pentru fiecare varf se precizeaza descendentul stang si descendentul drept,in fiecare caz ca acesta exista.Modul concret in care se precizeaza descendentii unui varf poate sa varieze :putem utiliza vectori,asa cum vom detalia imediat,sau putem folosi avantajele alocarii dinamice care ne permite sa legam un nod de parintele sau utilizand adresele reale de memorie.

In prima varianta se folosesc doi vectori S si D,pentru fieacre varf i,S[i] fiind descendentul stang,D[i] este descendentul drept iar INF[i] reprezentand informatia asociata nodului.Lipsa unui descendent se indica prin valoarea zero in S sau D.Pentru arborele binar din figura 6 avem,RAD=1 si S=(2,0,5,0,6,0,0) iar D=(3,0,4,0,7,0,0).Sa observam ca in general nu este esential sa precizam radacina,ea putand fi dedusa din vectorii S si D,dat fiind faptul ca radacina este singurul varf care nu este descendentul vreunui alt varf.

b) Se dau vectorii TATA,care precizeaza pentru fiecare varf i,nodul TATA[i]care reprezinta parintele sau si DESC,care indica prin valoarea -1 sau 1,daca varful i este descendentul stang sau drept al parintelui sau TATA[i].Pentru nodul radacina,care nu are un nod parinte asociat , componenta corespunzatoare din vectorul TATA va fi o.Pentru arborele din figura 6 vom avea :

TATA=(0,1,1,3,3,5,5) si

DESC=(0,-1,1,1,-1,-1,1).

Reprezentarea arborilor binari

In acest paragraf utilizam prima forma de reprezentare a arborilor binari.Exista multi algoritmi de prelucrare a structurilor arborescente,dar una dintre problemele care apar in mod frecvent in acesti algoritmi este necesitatea de a parcurge sau de a traversa arborele.

Prin parcurgerea unui arbore se intelege examinarea in mod sistematic a nodurilor sale astfel incat fiecare nod sa fie atins o singura data. Aceasta actiune este numita si "vizitare" a varfurilor arborelui,scopul ei fiind,in afara unuia pur didactic,acela al stationarii in fiecare varf pentru a efectua o prelucrare a informatiei asociata varfului respectiv.Arborele este o structura neliniara de organizare a datelor,iar rolul traversarii sale este tocmai conceperea unei aranjari lineare a nodurilor in vederea trecerii da la unul la altul,fructificand avantajul acestei organizari.

Exista trei modalitati principale de parcurgere a arborilor binari:nodurile pot fi vizitate in preordine,inordine si postordine.Aceste trei metode sunt definite recursiv :daca arborele este vid atunci el este traversat fara a se face nimic ;astfel,traversarea se face in trei etape.

a)Traversarea in preordine

I.Se viziteaza radacina ;

II.Se traverseaza subarborele stang ;

III.Se traverseaza subarborele drept.

b)Traversarea in inordine

I.Se traverseaza subarborele stang ;

II. Se viziteaza radacina ;

III.Se traverseaza subarborele drept.

c)Traversarea in postordine

I.Se traverseaza subarborele stang ;

II.Se traverseaza subarborele drept ;

III. Se viziteaza radacina .

Pentru arborele din figura 6,parcurgerea in preordine furnizeaza varfurile in ordinea :1,2,3,5,6,7,4 ;parcurgerea in inordine furnizeaza varfurile in ordinea:2,1,6,5,7,3,4;iar parcurgerea in postordine furnizeaza varfurile in ordinea:2,6,7,5,4,3,1.

LISTING

Program Parcurgere_Arbore;   

Var st,dr:array[1..10] of byte;

rad,n,i:byte;

c:char;

Procedure Antet;

Begin   

Writeln (' Proiect pentru atestat ');

Writeln ;   

Writeln (' Parcurgerea arborilor binari ');

Writeln ;

Writeln (' Nume elev:COJOC PAULICA ');

Writeln ;

Writeln (' Clasa:XII A ');

Writeln ;   

Writeln (' Prof.indrumator:Paraschiv Niculina ');

Writeln ;   

Writeln (' Sesiunea Mai-2005 ');

End;   

Procedure Inordine(k:byte);   

Begin   

If st[k]<>0 then inordine(st[k]);

Write(k,'');

If dr[k]<>0 then inordine(dr[k]);

End;   

Procedure Preordine(k:byte);

Begin   

Write(k,'');

If st[k]<>0 then preordine(st[k]);   

If dr[k]<>0 then preordine(dr[k]);

End;   

Procedure Postordine(k:byte);   

Begin   

If st[k]<>0 then postordine(st[k]);   

If dr[k]<>0 then postordine(dr[k]);   

Write(k,'');

End;   

Procedure control;   

Begin   

Writeln;   

Writeln('    A-daca doriti o parcurgere in inordine ');

Writeln;   

Writeln('    B-daca doriti o parcurgere in preordine ');

Writeln;   

Writeln('    C-daca doriti o parcurgere in postordine ');

Writeln;

Writeln('    T-pentru terminare ');

Writeln;   

End;   

Begin   

Antet;   

Control;   

Repeat   

Write('apasati o tasta:');Read(c);   

Case C of   

'A','a':Begin   

Write('numarul de noduri:');Read(n);

Write('radacina:');Read(rad);

For i:=1 to n do Begin

Write('st,dr(',i,')=');

Readln(st[i],dr[i]);

End;

Write('Arborele binar dat in parcurgere de tip inordine');

Writeln;

Inordine(rad);

Control;

End;

'B','b':Begin

Write('numarul de noduri:');Read(n);

Write('radacina:');Read(rad);

For i:=1 to n do Begin

Write('st,dr(',i,')=');

Readln(st[i],dr[i]);

End;

Write('Arborele binar dat in parcurgerea de tip preordine');

Writeln;

Preordine(rad);

Control;

End;

'C','c':Begin

Write('numarul de noduri:');Read(n);

Write('radacina:');Read(rad);

For i:=1 to n do Begin

Write('st,dr(',i,')=');

Readln(st[i],dr[i]);

End;

Write('Arborele binar dat in parcurgerea de tip postordine');

Writeln;

Postordine(rad);

Control;

End;

End;

Until(c='T') or(c='t');

End.

REZULTATE OBTINUTE DUPA RULAREA PROGRAMULUI

S-a tastat Alt+R

Borland Pascal Version 7.0 Copyright (c) 1983,92 Borland International

Proiect pentru atestat

Arbori Binari

Parcurgerea arborilor binari

Nume elev:COJOC PAULICA

Clasa:XII A

Prof.indrumator: Prof.Paraschiv Niculina

Sesiunea Mai 2005

A-daca doriti o parcurgere in inordine

B-daca doriti o parcurgere in preordine

C-daca doriti o parcurgere in postordine

T-pentru terminare

Apasati o tasta:

Se apasa tasta A :

A

Se constrieste arborele binar , utilizand metoda Divide et impera

astfel: -se citeste informatia utila pentru nod

-se aloca spatiu in memorie pentru acesta

- se completeaza informatia utila

-se construieste subarborele stang

- se construieste subarborele drept

Dati succesiunea de nodurilor arborelui binar :

N=1

N=2

N=0

N=0

N=3

N=0

N=0

INORDINE

Se parcurg mai intai subarborele stang, apoi radacina si subarborele drept.

A-daca doriti o parcurgere in inordine

B-daca doriti o parcurgere in preordine

C-daca doriti o parcurgere in postordine

T-pentru terminare

Apasati o tasta:

Se apasa tasta B :

B

Se constrieste arborele binar , utilizand metoda Divide et impera

astfel: -se citeste informatia utila pentru nod

-se aloca spatiu in memorie pentru acesta

- se completeaza informatia utila

-se construieste subarborele stang

- se construieste subarborele drept

Dati succesiunea de nodurilor arborelui binar :

N=1

N=2

N=0

N=0

N=3

N=0

N=0

PREORDINE

Se parcurg mai intai radacina ,subarborele stang si apoi subarborele drept.

A-daca doriti o parcurgere in inordine

B-daca doriti o parcurgere in preordine

C-daca doriti o parcurgere in postordine

T-pentru terminare

Apasati o tasta:

Se apasa tasta C :

C

Se constrieste arborele binar , utilizand metoda Divide et impera

astfel: -se citeste informatia utila pentru nod

-se aloca spatiu in memorie pentru acesta

- se completeaza informatia utila

-se construieste subarborele stang

- se construieste subarborele drept

Dati succesiunea de nodurilor arborelui binar :

N=1

N=2

N=0

N=0

N=3

N=0

N=0

POSTORDINE

Se parcurg mai intai subarborele stang , subarborele drept si apoi radacina.

Se apasa tasta T :

T

Se revine la programul principal.

BIBLIOGRAFIE

1.Daniela Oprescu-Informatica,Manual pentru clasa a XI-a,Editura Niculescu 2002

2.Cristea V. Si Athanasiu I.-Turbo Pascal 6.0,Editura Teora,Bucuresti 1992

3.Iorga V. si Fatu I.-Programrea in limbajul Turbo Pascal,Litografia I.P.B. 1997

4.Balanescu Tudor-Programarea in limbajele Pascal si Turbo Pascal,Editura Tehnica,Bucuresti

5.Tudor Sorin-Tehnici de programare,Editura L&S Infomat 1997

6.Tudor Sorin-Turbo Pascal,Algoritmi si limbaje de programare,Editura L&S Infomat 1997