Referat, comentariu, eseu, proiect, lucrare bacalaureat, liceu si facultate
Top referateAdmitereTesteUtileContact
      
    


 


Ultimele referate adaugate

Adauga referat - poti sa ne ajuti cu un referat?

Politica de confidentialitate





Ultimele referate descarcare de pe site
  CREDITUL IPOTECAR PENTRU INVESTITII IMOBILIARE (economie)
  Comertul cu amanuntul (economie)
  IDENTIFICAREA CRIMINALISTICA (drept)
  Mecanismul motor, Biela, organe mobile proiect (diverse)
  O scrisoare pierduta (romana)
  O scrisoare pierduta (romana)
  Ion DRUTA (romana)
  COMPORTAMENT PROSOCIAL-COMPORTAMENT ANTISOCIAL (psihologie)
  COMPORTAMENT PROSOCIAL-COMPORTAMENT ANTISOCIAL (psihologie)
  Starea civila (geografie)
 




Ultimele referate cautate in site
   domnisoara hus
   legume
    istoria unui galban
   metanol
   recapitulare
   profitul
   caract
   comentariu liric
   radiolocatia
   praslea cel voinic si merele da aur
 
despre:
 
Stucturi proiect
Colt dreapta
Vizite: ? Nota: ? Ce reprezinta? Intrebari si raspunsuri
 
Laborator numarul 1

Tema: u1t13tm
Arbori binari ordonati.
Analiza:
Prin arbore binar ordonat (sau arbore de cautare ) se intelege un arbore binar care care are proprietatea ca, parcurgand nodurile in inordine , secventa cheilor este monoton crescatoare .Un arbore ordonat se bucura de urmatoarea proprietate:daca N este un nod oarecare al arborelui , avand cheia c, atunci toate nodurile din subarborele stang al lui N au cheile mai mici decat cheia c, si toate nodurile din subarborele drept al lui N au cheile mai mari sau egale cu cheia c.
De aici rezulta un procedeu foarte simplu de cautare : incepand cu radacina, se trece la fiul stang sau la fiul drept, dupa cum cheia cautata este mai mica sau mai mare decat cea a nodului curent.
Vom folosi urmatoarea stuctura de arbore binar ordonat:

typedef struct nod
A int cheie; struct nod *st,*dr;
STnod; typedef Tnod *ref; ref radacina;

Pentru vizualizarea naturala a unui arbore avem nevoie de modul grafic. In C pentru a realiza un program ce utilizeaza modul grafic trebuie respectate urmatoarele etape :
? Initializare mod grafic;
? Stabilirea culorii hartiei de scris (fundalului );
? Stabilirea culorii scrisului;
? Reprezentarea in mod grafic a ceea ce dorim sa relizam;
? Iesirea din modul grafic.
Vom folosi urmatoarea functie C pentru a initializa modul grafic :

void initializare_mod_grafic(void)
A int gdriver=DETECT, gmode, err; initgraph(&gdriver, &gmode, CALE); err=graphresult(); if(err!=grOk)
A printf("Eroare la initializarea modului grafic: %s\n", grapherrormsg(err)); printf("Apasati o tasta pentru a termina ...\n"); getch(); exit(1);
S
S/*initializare mod grafic*/

Lucru in mod grafic (explicarea functiilor pentru gestiunea ecranului in mod grafic ).




Gestiunea ecranului in mod grafic
Pentru gestiunea ecranului in mod grafic se pot utiliza peste 60 de functii standard aflate in biblioteca sistemului. Aceste functii au prototipul in fisierul graphics.h .

Setarea modului grafic
Modul grafic se seteaza cu ajutorul functiei initgraph.Aceasta functie poate fi folosita singura sau impreuna cu o alta functie numita detectgraph care determina parametrii adaptorului graphic.Prototipul ei este:

void far detectgraph(int far *gd, int far *gm);

unde: valorile spre care pointeaza gd definesc niste functii standard corespunzatoare adaptorului grafic. Aceste functii se numesc drivere .Ele se afla in subdirectorul BGI.
Apelul functiei detectgraph trebuie urmat de apelul functiei initgraph. Aceasta are prototipul: void far initgraph(int far *gd , int far *gm, int far *cale); unde: gd si gm -sunt pointeri care au aceeasi semnificatie ca in cazul functiei detectgraph. cale -este pointer spre sirul de caractere care defineste calea subdirectorului
BGI care contine driverele. De exemplu, daca BGI este subdirector al
Directorului BORLANDC, atunci vom folosi sirul de caractere :
“c:\\BORLANDC\\BGI”
Constanta simbolica DETECT este definita in fisierul graphics.h alaturi de celelalte constante simbolice care definesc driverul. Aceasta are valoarea zero.

Gestiunea culorilor
In mod grafic, ecranul se considera format din puncte luminoase numite pixeli. Pozitia pe ecran a unui pixel se defineste printr-un sistem binar: (x,y) unde: x -defineste coloana in care este afisat pixelul . y -defineste linia in care este afisat pixelul .
In cazul adaptoarelor color, unui pixel ii corespunde o culoare. Culoarea pixelilor se pastreaza pe biti in memoria video. Multimea culorilor care pot fi afisate simultan pe ecran se numeste paleta. Culorile din componenta unei palete pot fi modificate de utilizator prin intermediu functiilor standard. La initializarea modului grafic se seteaza o paleta implicita.
Culoarea de fond poate fi modificata cu ajutorul functiei setbkcolor. Aceasta are prototipul: void far setbkcolor(int culoare); unde: culoare -este index in tabloul care defineste paleta.
De exemplu, daca se utilizeaza apelul: setbkcolor(BLUE); atunci culoarea de fond devine albastra.
Pentru a cunoaste culoarea de fond curenta se poate apela functia getbkcolor de prototip: int far getbkcolor(void); -ea returneaza indexul in tablou care defineste paleta pentru culoarea de fond.
Culoarea pentru desenare poate fi modificata folosind functia setcolor de prototip: void far setcolor(int culoare); unde : culoare -este indexul in tablou care defineste paleta.
De exemplu, daca se utilizeaza apelul: setcolor(YELLOW); atunci culoarea pentru desenare este galbena.
Culoarea pentru desenare se poate determina apeland functia getcolor de prototip: int far getcolor(void); ea returneaza indexul in tablou care defineste paleta relativa la culoare pentru desenare.
Paleta curenta poate fi modificata folosind functiile settpalette si setallpalette.
Numarul culorilor dintr-o paleta poate fi obtinut apeland functia getmaxcolor de prototip: int far getmaxcolor(void); -ea returneaza numarul maxim de culori diminuat cu 1.

Starea ecranului
In mod grafic, ecranul se compune din n*m puncte luminoase(pixeli). Aceasta inseamna ca pe ecran se pot afisa m linii a n pixeli fiecare.
Coloanele se numeroteaza de la stanga spre dreapta, iar liniile de sus in jos.
Biblioteca grafica a sistemului contine 4 functii care permit utilizatorului sa obtina urmatoarele informatii relative la ecran:
-coordonata maxima pe orizontala (abscisa maxima): int far getmaxx(void);
-coordonata maxima pe verticala (ordonata maxima): int far getmaxy(void);
-pozitia curenta pe orizontala (abscisa) a pixelului: int far getx(void);
- pozitia curenta pe verticala (ordonata) a pixelului: int far gety(void);

Gestiunea textelor
Afisarea textelor presupune definirea unor parametri care pot fi gestionati prin functiile descrise mai jos.
Acesti parametri se seteaza cu ajutorul a doua functii settextstyle si settextjustify. Prima are prototipul: void far settextstyle(int font, int direction, int charsize); unde: font -defineste setul de caractere direction -defineste directia de scriere a textului charsize -defineste dimensiunea caracterului in pixeli
Cea dea doua functie defineste cadrajul textului. Ea are prototipul: void far settextjustify(int oriz, int vert); unde : oriz -defineste cadrajul pe orizontala vert -defineste cadrajul pe verticala
Valorile acestor parametri pot fi determinate cu ajutorul functiei gettextsettings de prototip: void far gettextsettings(struct textsettingstype far *textinfo);
Dupa setarea parametrilor de mai sus se pot afisa texte folosind functiile outtext si outtextxy. Prima afiseaza textul incepand cu pozitia curenta de pe ecran. Cea de a doua functie permite afisarea textului incepand cu un punct al carui coordonate sunt definite prin primi doi parametri efectivi ai functiei. Functiile afiseaza caractere colorate folosind culoarea de desenare curenta. Functia outtext are prototipul: void far outtext(char far *sir); unde: sir -este pointer spre o zona de memorie in care se pastreaza caracterele de afisat.
Se afiseaza caracterele respective pana la intalnirea caracterului NULL.
Functia outtextxy are prototipul : void far outtextxy(int x, int y, char far *sir); unde : (x,y) -defineste pozitia punctului de pe ecran incepand cu care se afiseaza textul sir -are aceeasi semnificatie ca in cazul functiei outtext.
Dimensiunile in pixeli a unui sir de caractere se pot determina folosind functiile textheight si textwidth. Acestea au prototipurile: int far textheight(char far *sir); -returneaza inaltimea in pixeli a sirului pastrat
in zona spre care pointeza sir; int far textwidth(char far *sir); -returneaza latimea in pixeli a sirului aflat in zona spre care pointeaza sir.
Gestiunea imaginilor

Utilizatorul poate afisa pe ecran un pixel cu ajutorul functiei putpixel. Aceasta are prototipul: void far putpixel(int x, int y, int culoare); unde : (x,y) -defineste pozitia punctului. culoare -defineste culoarea punctului. Este un intreg din intervalul a0,15i si reprezinta indicele culorii in tabela care defineste paleta curenta.
Functia getpixel permite stabilirea culorii unui pixel afisat pe ecran. Ea are prototipul: unsigned far getpixel(int x, int y); unde :(x,y) -defineste pozitia punctului
O fereastra se defineste cu ajutorul functiei setviewwport de prototip: void far setviewport(int st, int sus, int dr, int jos, int d ); unde: (st,sus) -sunt coordonatele coltului stanga sus al ferestrei.
(dr,jos) -sunt coordonatele coltului dreapta jos al ferestrei d -indicatorul cu privire la decuparea desenului
O ferastra activa se poate sterge cu ajutorul functiei clearviewport. Ea are prototipul : void far clearviewport(void);
Dupa apelul functiei clearviewport, toti pixelii ferestrei active au aceeasi culoare si anume culoarea de fond curenta.
O alta functie utilizata pentru a sterge tot ecranul este functia cleardevice. Ea are prototipul : void far cleardevice(void);
Dupa apelul functiei cleardevice se sterge tot ecranul si pixelul current devine cel din coltul stanga sus al ecranului.

Tratarea erorilor
Erorile survenite in gestiunea in mod grafic a ecranului pot fi puse in evidenta cu ajutorul functiei graphresult. Ea are prototipul : int far graphresult(void);
Functia returneaza codul ultimei erori care a aparut inaintea apelului functiei graphresult sau valoarea constantei simbolice grOk daca nu au fost erori. Constanta grOk este definita in fisierul graphics.h .
Mesajul de eroare poate fi decodificat cu ajutorul functiei grapherrormsg. Ea are prototipul : char far *far grapherrormsg(int coderoare); unde: coderoare -este valoarea returnata de functia graphresult.
Functia grapherrormsg returneaza un pointer spre textul de eroare.
Constanta grOk are valoarea zero.Codurile de eroare au valori negative.

Desenare si colorare
Amintim ca un punct colorat(pixel) se afiseaza cu ajutorul functiei putpixel de prototip: void far putpixel(int x, int culoare);
Pentru trasarea liniilor se pot folosi trei functii: line, lineto si linerel.
Functia line are prototipul: void far line(int xstart, int ystart, int xfin, int yfin);
Functia traseaza un segment de dreapta ale carui capete sunt punctele de coordonate: (xstart,ystart) si (xfin,yfin);
Functia lineto are prototipul : void far lineto(int x, int y); Ea traseaza un segment de dreapta care are ca origine pozitia curenta, iar ca si punct final cel de coordonate(x,y).
Punctul final devine pozitia curenta. Amintim ca functia moveto permite definirea pozitiei curente.
Cea de a treia functie utilizata la trasarea dreptelor are prototipul: void far linerel(int x, int y);
Functia care traseaza un cerc, are prototipul: void far circle(int xcentru, int ycentru, int raza);
Functia care deseneaza o elipsa colorata, are prototipul: void far fillellipse(int xcentru, int ycentru, int semiaxamare, int semiaxamica);
Modul de colorare al unei figure si culoarea se defineste cu ajutorul functiei setfillstyle. Ea are prototipul: void far setfillstyle(int hasura, int culoare); unde : hasura -defineste modul de colorare culoare -defineste culoarea pentru colorarea figurilor

Programul C:

Scrieti programul C care permite crearea si vizualizare unui arbore binar ordonat cu vizualizare naturala.

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <conio.h>
#include <graphics.h>
#include <dos.h>

#define CALE "E:\\BC\\BGI"
#define raza 10
#define timp 500
#define spatiu 40

typedef struct nod
A int cheie; struct nod *st, *dr;
STnod; typedef Tnod *ref; ref radacina;

void creare(void); void inarbore(int, ref *); void initializare_mod_grafic(void); void tip(ref, int, int, int, int, int, char *); void inordine(ref, int, int, int, int, int); void preordine(ref, int, int, int, int, int); void postordine(ref, int, int, int, int, int); void tipt(ref anod, int nivel);

void main(void)
A char op; do
A clrscr(); printf("Sa se creeze un arbore binar ordonat si sa se afiseze grafic\n"); printf(" C. Creare\n"); printf(" I. Afisare in mod grafic in inordine\n"); printf(" P. Afisare in mod grafic in preordine\n"); printf(" O. Afisare in mod grafic in postordine\n"); printf(" E. Iesire\n"); printf("Introduceti optiunea: "); fflush(stdin); op=toupper(getc(stdin)); switch (op)
A case 'C': creare(); break;

case 'I': if(radacina==NULL) printf("Arborele este vid\n"); else
A initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Parcurgere in INORDINE" ); setviewport(0,30,getmaxx(), getmaxy(), 1); inordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(BLUE); outtextxy(getmaxx()/2, getmaxy()-40, "Apasati o tasta pt. a termina"); fflush(stdin);while(!getch()); closegraph();
S break; case 'P': if(radacina==NULL) printf("Arborele este vid\n"); else
A initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Parcurgere in PREORDINE" ); setviewport(0,30,getmaxx(), getmaxy(), 1); preordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(BLUE); outtextxy(getmaxx()/2, getmaxy()-40, "Apasati o tasta pt. a termina."); fflush(stdin);while(!getch()); closegraph();
S break;

case 'O': if(radacina==NULL) printf("Arborele este vid\n"); else
A initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Parcurgere in POSTORDINE" ); setviewport(0,30,getmaxx(), getmaxy(), 1); postordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(BLUE); outtextxy(getmaxx()/2, getmaxy()-40, "Apasati o tasta pt. a termina."); fflush(stdin);while(!getch()); closegraph();
S break;

case 'E': break;

default: printf("\nOptiune invalida !\n"); break;
S
S
while(op!='E');
S

void creare(void)
A int x; radacina=NULL; printf("Introduceti noul nod (0-pt a termina): ");
while(scanf("%d", &x)!=1)
A printf("Introduceti un numar!\n"); fflush(stdin);
S
while(x!=0)
A inarbore(x, &radacina); printf("Introduceti noul nod (0-pt a termina): ");
while(scanf("%d", &x)!=1)
A printf("Introduceti un numar!\n"); fflush(stdin);
S
S
S/*creare*/

void inarbore(int x, ref *t)
A if((*t)==NULL)
A
*t = (Tnod*)malloc(sizeof(Tnod));
(*t)->st = NULL;
(*t)->dr = NULL;
(*t)->cheie = x;
S else
A if(x < (*t)->cheie) inarbore(x, &(*t)->st); else inarbore(x, &(*t)->dr);
S
S/*inarbore*/

void initializare_mod_grafic(void)
A int gdriver=DETECT, gmode, err;

initgraph(&gdriver, &gmode, CALE); err=graphresult(); if(err!=grOk)
A printf("Eroare la initializarea modului grafic: %s\n", grapherrormsg(err)); printf("Apasati o tasta pentru a termina ...\n"); getch(); exit(1);
S
S/*initializare mod grafic*/

void inordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
A static char sa10i; if(rad!=NULL)
A inordine(rad->st, nivel+1, x1, (x1+x2)/2, (x1+x2)/2, nivel*spatiu+raza); tip(rad, nivel, x1, x2, c1, c2, s); inordine(rad->dr, nivel+1, (x1+x2)/2, x2, (x1+x2)/2, nivel*spatiu+raza);
S
S/*inordine*/

void preordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
A static char sa10i; if(rad!=NULL)
A tip(rad, nivel, x1, x2, c1, c2, s); preordine(rad->st, nivel+1, (x1+x2)/2, x2, (x1+x2)/2, nivel*spatiu+raza); preordine(rad->dr, nivel+1, x1, (x1+x2)/2, (x1+x2)/2, nivel*spatiu+raza);
S
S/*preordine*/

void postordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
A static char sa10i; if(rad!=NULL)
A postordine(rad->dr, nivel+1, x1, (x1+x2)/2, (x1+x2)/2, nivel*spatiu+raza); postordine(rad->st, nivel+1, (x1+x2)/2, x2, (x1+x2)/2, nivel*spatiu+raza); tip(rad, nivel, x1, x2, c1, c2, s);
S
S/*postordine*/

void tip(ref anod, int nivel, int x1, int x2, int c1, int c2, char *s)
A setcolor(15); line((x1+x2)/2, nivel*spatiu+raza, c1,c2+textheight("1")/2); fillellipse((x1+x2)/2, nivel*spatiu+raza, raza, raza); setcolor(1);/*albastru*/ sprintf(s, "%d", anod->cheie); outtextxy((x1+x2)/2, nivel*spatiu+raza, s); delay(timp);
S/*tiparire grafica*/

Laborator numarul 2

Tema:
Suprimarea unui nod dintr-un arbore binar ordonat.
Analiza :

Vom folosi urmatoarea stuctura de arbore binar ordonat: typedef struct nod
A int cheie; struct nod *st,*dr;
STnod; typedef Tnod *ref; ref radacina;

Procesul de creare a unui astfel de arbore consta in insertia unui nod intr-un arbore binar ordonat , care initial este vid.



Se traverseaza arborele incepand cu radacina si se selecteaza fiul stang sau drept , dupa cum cheia de inserat este mai mica sau mai mare decat cea a nodului parcurs. Aceasta se repeta pana cand se ajunge la un pointer NULL. Se modifica acest pointer astfel incat sa indice noul nod.
Pentru a suprima un nod cu cheia x, se cauta in prealabil daca exista un nod cu o astfel de cheie. Daca nu exista, suprimarea s-a incheiat si se va emite un mesaj de eroare. In caz contrar se executa suprimarea propriu-zisa, in asa fel incat arborele sa ramana ordonat si dupa terminarea ei.
Cautarea se realizeaza cu ajutorul functiei Loc(x,t), unde t este un pointer care indica radacina arborelui, iar x este un intreg, executa cautarea nodului de cheie x in acest arbore. Aceasta functie ia valoarea NULL daca nu gaseste nici un nod cu cheia x, altfel valoarea ei este egala cu adresa nodului de cheie x.
Daca elementul care se sterge este un nod terminal sau un nod cu un singur descendent, stergerea este directa. Daca nodul are insa doi descendenti, deoarece nu putem pointa in doua directii cu un singur pointer , elementul care se sterge este inlocuit fie cu cel mai din dreapta element al subarborelui sau stang, fie cu cel mai din stanga element al subarborelui sau drept, ambele avand maxim un descendent. a)Daca nodul care trebuie suprimat are cel mult un fiu, se procedeaza astfel :daca p este referinta care indica nodul x, valoarea lui p se modifica astfel aceasta sa indice unicul fiu al lui x, daca acesta exista, sau in caz contrar, p devine NULL. b)Daca nodul cu cheia x are doi fii se procedeaza astfel:
Se cauta predecesorul (respectiv succesorul) nodului in inordine. Fie acesta y.
Se modifica nodul x, asignand campurile sale, cu exceptia campurilor st si dr cu campurile corespunzatoare ale nodului y; se suprima apoi nodul y initial ca si la cazul a).

Observatii:
Procedeul de cautare intr-un arbore binar ordonat are eficienta maxima cand arborele este de inaltime minima. In caz contrar, eficienta este mult redusa, in cazul cel mai defavorabil arborele degenerand intr-o structura de lista liniara .
Toate nodurile terminale vor indica fanionul, adica toate referintele nule ale nodurilor arborelui initial se vor inlocui cu adresa fanionului.
Daca vom folosi pe y succesorul lui in inordine, atunci acesta va fi cel mai din stanga nod al subarborelui stang al nodului x.

Programul C :

Scrieti programul C care permite crearea si vizualizarea unui arbore binar ordonat cu vizualizare naturala. Programul va permite si suprimarea unui nod de cheie data.

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <conio.h>
#include <graphics.h>
#include <dos.h>

#define CALE "c:\\BorlandC\\BGI"

#define raza 10
#define timp 500
#define spatiu 40

typedef struct nod
A int cheie; struct nod *st, *dr;
S Tnod; typedef Tnod *ref;

void creare(void); void inarbore(int, ref *); void initializare_mod_grafic(void); void tip(ref, int, int, int, int, int, char *); void inordine(ref, int, int, int, int, int); void preordine(ref, int, int, int, int, int); void postordine(ref, int, int, int, int, int); void tipt(ref anod, int nivel); void suprimare(int, ref *); void suprimafd(ref *); ref Loc(int, ref);/*cauta un nod in arbore*/

ref radacina, r, q; int x, culoare_fundal=15,/*culoarea de fundal a nodurilor arborelui*/ culoare_scris=1, /*culoarea cu care sunt scrise nodurile arborelui*/ afisare=0;/*pt. cautare*/

void main(void)
A char op;

radacina = NULL; do
A clrscr(); printf("Sa se creeze un arbore binar ordonat si sa se afiseze grafic\n"); printf(" C. Creare\n"); printf(" S. Suprimarea unui nod din arbore\n"); printf(" F. Cauta un nod in arbore\n"); printf(" I. Afisare in mod grafic in inordine\n"); printf(" P. Afisare in mod grafic in preordine\n"); printf(" O. Afisare in mod grafic in postordine\n"); printf(" E. Iesire\n"); printf("Introduceti optiunea: "); fflush(stdin); op=toupper(getc(stdin)); switch (op)
A case 'C': creare(); initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Parcurgere in INORDINE" ); setviewport(0,30,getmaxx(), getmaxy(), 1); inordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(WHITE); outtextxy(getmaxx()/2, getmaxy()-40, "Apasati o tasta pt. a termina"); fflush(stdin);getch(); closegraph(); break;

case 'S': printf("Introduceti nodul de suprimat: ");
while(scanf("%d", &x)==0)
A printf("Introduceti un intreg!\n"); fflush(stdin); printf("Introduceti cheia nodului de cautat: ");
S suprimare(x, &radacina); initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Parcurgere in INORDINE" ); setviewport(0,30,getmaxx(), getmaxy(), 1); inordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(WHITE); outtextxy(getmaxx()/2, getmaxy()-40,
"Apasati o tasta pt. a termina"); fflush(stdin);getch(); closegraph(); break;

case 'F': afisare = 0; printf("Introduceti cheia nodului de cautat: ");
while(scanf("%d", &x)==0)
A printf("Introduceti un intreg!\n"); fflush(stdin); printf("Introduceti cheia nodului de cautat: ");
S r = Loc(x, radacina); if(r == NULL)
A printf("Nodul nu exista in arbore!\n"); printf("Apasati o tasta pentru a continua!\n");getch();
S else
A afisare = 1; initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Parcurgere in INORDINE" ); setviewport(0,30,getmaxx(), getmaxy(), 1); inordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(WHITE); outtextxy(getmaxx()/2, getmaxy()-40,
"Nodul a fost gasit in arbore"); fflush(stdin);getch(); closegraph();
S break;

case 'I': if(radacina==NULL)
A printf("Arborele este vid\n"); printf("Apasati o tasta pt. a continua\n");getch();
S else
A initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Parcurgere in INORDINE" ); setviewport(0,30,getmaxx(), getmaxy(), 1); inordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(WHITE); outtextxy(getmaxx()/2, getmaxy()-40, "Apasati o tasta pt. a termina"); fflush(stdin);getch(); closegraph();
S break;

case 'P': if(radacina==NULL)
A printf("Arborele este vid\n"); printf("Apasati o tasta pt. a continua\n");getch();
S else
A initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Parcurgere in PREORDINE" ); setviewport(0,30,getmaxx(), getmaxy(), 1); preordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(WHITE); outtextxy(getmaxx()/2, getmaxy()-40, "Apasati o tasta pt. a termina."); fflush(stdin);getch(); closegraph();
S break;

case 'O': if(radacina==NULL)
A printf("Arborele este vid\n"); printf("Apasati o tasta pt. a continua\n");getch();
S else
A initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Parcurgere in POSTORDINE" ); setviewport(0,30,getmaxx(), getmaxy(), 1); postordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(WHITE); outtextxy(getmaxx()/2, getmaxy()-40, "Apasati o tasta pt. a termina."); fflush(stdin);getch(); closegraph();
S break;

case 'E': break;

default: printf("\nOptiune invalida !\n"); break;
S
S
while(op!='E');
S/*main*/

void creare(void)
A int x;

radacina=NULL; printf("Introduceti noul nod (0-pt a termina): ");
while(scanf("%d", &x)!=1)
A printf("Introduceti un numar!\n"); fflush(stdin);
S
while(x!=0)
A inarbore(x, &radacina); printf("Introduceti noul nod (0-pt a termina): ");
while(scanf("%d", &x)!=1)
A printf("Introduceti un numar!\n"); fflush(stdin);
S
S
S/*creare*/

void inarbore(int x, ref *t)
A if((*t)==NULL)
A
*t = (Tnod*)malloc(sizeof(Tnod));
(*t)->st = NULL;
(*t)->dr = NULL;
(*t)->cheie = x;
S else
A if(x < (*t)->cheie) inarbore(x, &(*t)->st); else inarbore(x, &(*t)->dr);
S
S/*inarbore*/

void initializare_mod_grafic(void)
A int gdriver=DETECT, gmode, err;

initgraph(&gdriver, &gmode, CALE); err=graphresult(); if(err!=grOk)
A printf("Eroare la initializarea modului grafic: %s\n", grapherrormsg(err)); printf("Apasati o tasta pentru a termina ...\n"); getch(); exit(1);
S
S/*initializare mod grafic*/

void inordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
A static char sa10i; if(rad!=NULL)
A inordine(rad->st, nivel+1, x1, (x1+x2)/2, (x1+x2)/2, nivel*spatiu+raza); tip(rad, nivel, x1, x2, c1, c2, s); inordine(rad->dr, nivel+1, (x1+x2)/2, x2, (x1+x2)/2, nivel*spatiu+raza);
S
S/*inordine*/

void preordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
A static char sa10i; if(rad!=NULL)
A tip(rad, nivel, x1, x2, c1, c2, s); preordine(rad->st, nivel+1, x1, (x1+x2)/2, (x1+x2)/2, nivel*spatiu+raza); preordine(rad->dr, nivel+1, (x1+x2)/2, x2, (x1+x2)/2, nivel*spatiu+raza);

S
S/*preordine*/

void postordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
A static char sa10i; if(rad!=NULL)
A postordine(rad->st, nivel+1, x1, (x1+x2)/2, (x1+x2)/2, nivel*spatiu+raza); postordine(rad->dr, nivel+1, (x1+x2)/2, x2, (x1+x2)/2, nivel*spatiu+raza); tip(rad, nivel, x1, x2, c1, c2, s);
S
S/*postordine*/

void tip(ref anod, int nivel, int x1, int x2, int c1, int c2, char *s)
A if(afisare==1 && anod==r)
A culoare_scris=BLUE; culoare_fundal=RED; r = NULL;
S else
A culoare_scris=1;/*albastru*/ culoare_fundal=15;/*alb*/
S setcolor(15); line((x1+x2)/2, nivel*spatiu+raza, c1,c2+textheight("1")/2); setfillstyle(SOLID_FILL, culoare_fundal); fillellipse((x1+x2)/2, nivel*spatiu+raza, raza, raza); setcolor(culoare_scris);/*albastru*/ sprintf(s, "%d", anod->cheie); outtextxy((x1+x2)/2, nivel*spatiu+raza, s); delay(timp);
S/*tiparire grafica*/

void suprimafd(ref *r)
A if((*r)->dr!=NULL) suprimafd(&((*r)->dr)); else
A q->cheie = (*r)->cheie; q = *r;
*r = q->st;
S
S/*suprimafd*/

void suprimare(int x, ref *p)
A if((*p)==NULL) printf("Nodul nu exista, nu am ce sterge!\n"); else if(x < (*p)->cheie) suprimare(x, &((*p)->st)); else if(x > (*p)->cheie) suprimare(x, &((*p)->dr)); else /*sterge *p*/
A q=*p; if(q->dr==NULL)
*p = q->st; else if(q->st==NULL)
*p=q->dr; else suprimafd(&(q->st)); free(q);
S
S/*suprima*/

ref Loc(int x, ref t)
A int gasit = 0;
while((gasit==0)&&(t!=NULL)) if(t->cheie == x) gasit=1; else if(x < t->cheie) t = t->st; else t= t->dr; return t;
S/*Loc*/

Laborator numarul 3

Tema:
Arbori AVL. Inserarea unui nod in arbore AVL.
Analiza:
Un arbore binar se va numi echilibrat dupa inaltime (sau AVL) daca diferenta de inaltime dintre cei doi subarbori ai fiecarui nod este cel mult 1.
Fie un arbore binar cu radacina R si S ,D pe post de subarbore stang respectiv drept. Notam cu hs, inaltimea lui S si cu hd inaltimea lui D. Fara a restrange generalitatea, presupunem ca noul nod se insereaza in S, determinand cresterea cu 1 a inaltimii acestuia. Pot rezulta trei situatii:
1.hs<hd -; in urma insertiei , S,D devin de inaltimi egale, echilibrul fiind clar imbunatatit.
2.hs=hd -; in urma insertiei ,S si D devin de inaltimi inegale, fara a strica insa criteriul echilibrului
3.hs>hd -; criteriul echilibrului este stricat si arborele trebuie reechilibrat.
Vom considera urmatoare structura: typedef struct nod
A int cheie; struct nod *st,*dr;
S Tnod; typedef Tnod *ref; ref radacina;
Se intalnesc urmatoarele cazuri de reechilibrare :
• hs>hd

Cazul I stanga (SS)
Fie urmatorul arbore AVL:



-1

0 0
0
0 0
Pentru a cuprinde toate cazurile de inserare si caracteristicile acestora vom presupune ca nodurile se vor insera, pe rand,in arborele initial.

Cazul I a(SS)
• Inserarea nodului de cheie 1 dupa inserare : reechilibrarea : p

? p1



Cazul I b(SS)
Inserarea nodului de cheie 3
Dupa inserare : reechilibrarea: p

? p1


Dupa inserarea nodului de cheie 3 arborele de radacina 8 se dezechilibreaza fiindca inaltimea subarborelui stang este 2, iar inaltimea subarborelui drept este 0 si deci se impune reechilibrarea.
Fie p variabila pointer care contine adresa nodului radacina a arborelui ce se dezechilibreaza, iar p1 radacina subarborelui sau stang. La reechilibrare vom face nodul *p1 radacina a arborelui, iar fostul nod * p il vom cobora in subarborele sau drept. Pentru ca la traversarea in inordine secventa cheilor sa ramana monoton crescatoare subarborele drept al nodului p1 il vom trece ca subarbore stang a nodului care a fost *p. Intrucat in acest moment se cunostea doar adresa nodului radacina in care s-a facut inserarea, succesiunea operatiilor va fi urmatoarea: p1=p->st; p->st=p1->dr; p1->dr=p; p=p1;
Comparand cazul I a cu cazul I b vom constata ca vom face aceleasi operatii si de aceea cazul I a si cazul I b il vom retine ca si cazul I SS(stanga). p1=p->st; p->st=p1->dr; p1->dr=p; p=p1;

Cazul II a

Inserarea nodului de cheie 5
Dupa inserare reechilibrarea

p

? p1


Fie p variabila pointer care contine adresa nodului radacina a arborelui ce se dezechilibreaza, p1 radacina subarborelui sau stang, iar p2 referinta dreapta a nodului *p1 .
Pentru a realiza reechilibrarea urcam nodul p2 pointer inter nodul *p1 si *p .
Pentru ca la traversarea in inordine dupa reechilibrare secventa sa ramana monoton crescatoare subarborele drept al nodului p1 va deveni ceea ce a fost subarbore stang a nodului p2, iar referinta stanga a nodului p va devenii referinta nula, lucru care este echivalent cu a spune ca subarborele stang al nodului p va deveni ceea ce a fost subarborele drept a lui p2. Succesiunea operatiilor va fi urmatoarea: p1->dr=p2->st ; p->st=p2->dr ; p2->st=p1 ; p2->dr=p ; p=p2 ;

Cazul II a(SD)

Inserarea nodului de cheie 7

Dupa inserare reechilibrare p

? p1

Dupa inserarea nodului de cheie 7, arborele de cheie 8 se dezechilibreaza rezulta reechilibrarea.


Pentru a realiza reechilibrarea urcam nodul p2 pointer intre nodul *p1 si *p .
Pentru ca la traversarea in inordine dupa reechilibrare secventa sa ramana monoton crescatoare subarborele drept al nodului p1 va deveni ceea ce a fost subarbore stang a nodului p2, iar referinta stanga a nodului p va devenii referinta nula, lucru care este echivalent cu a spune ca subarborele stang al nodului p va deveni ceea ce a fost subarborele drept a lui p2. Succesiunea operatiilor va fi urmatoarea: p1->dr=p2->st ; p->st=p2->dr ; p2->st=p1 ; p2->dr=p ; p=p2 ;
Comparand operatiile care se efectueaza in cazul II a(SD) si cazul II b(SD) se constata ca vom face aceleasi operatii si de aceea cazul II a si cazul II b cazul II SD(stanga). p1->dr=p2->st ; p->st=p2->dr ; p2->st=p1 ; p2->dr=p ; p=p2 ;
Deci caracteristicile cazului S(stanga) sunt : p1=p->st; p2=p1->dr; p1->dr=p2->st ; p->st=p2->dr ; p2->st=p1 ; p2->dr=p ; p=p2 ;
Daca se doreste inserarea noului nod in subarborele drept al nodului radacina, atunci vom avea aceleasi situatii: hd <hs hd=hs hd>hs

Toate aceste 3 situatii se vor rezolva prin simetrie inlocuind st<->dr, incat vom constata ca in situatia in care se impune reechilibrarea vom avea cazul I DD(dreapta) si cazul II DS(dreapta)
Printr-o analiza atenta a operatiilor de inserare a unui nod intr-un arbore AVL cele patru situatii de echilibrare(cazul I S , cazul II S,cazul I D, cazul II D)pot fi reduse tratand doar doua situatii dintre acestea, celelalte doua situatii putand fi rezolvate prin analogie si simetrie inlocuind st<->dr si dr<->st.
Pentru a stabili in cadrul algoritmului de inserare cand se impune reechilibrarea si ce caz de reechilibrare este, vom introduce notiunea de factor de echilibru al unui nod, care reprezinta diferenta dintre inaltimea subarborelui sau drept si a celui stang. Astfel ca strctura arborelui va deveni: typedef struct nod
A int cheie; int contor; int ech; struct nod *st,*dr;
STnod; typedef Tnod *ref; ref radacina;

Algoritmul se va desfasura in trei faze :
? Se parcurge arborele pentru a verifica daca cheia exista in arbore.
? Daca nodul exista atunci eventual se incrementeaza contotul asociat nodului si algiritmul se opreste; in caz contrar nodul nu exista in arbore atunci se insereaza noul nod (daca nu exista in arbore) la locul determinat la pasul 1 si se stabileste corespunzator factorul de echilibru.
? Se revine pe drumul de cautare , in sens invers, si se restabileste factorul de echilibru pentru fiecare nod de pe acest drum.

Consideram ca inserarea se face in S:
Inainte de inserare : Dupa inserare:
1.hs<hd ?p->ech=1; ? 1.hs=hd?p->ech=0;
2.hs=hd?p->ech=0; ? 2.hs>hd?p->ech=-1;
3.hs>hd<>p->ech=-1; ?3.reechilibrarea
Dupa reechilibrare factorii de echilibru nu au fost modificati inca, de aceea mergem inapoi pe drumul de cautare pentru a modifica factorii de echilibru a nodurilor *p, *p1,*p2. De aceea cazul I Stanga (SS) devine: p1=p->st ; p->ech=-1 ; caracteristicile cazului I Stanga p1->ech=-1 ;

p->st=p1->dr ; reechilibrare p1->dr=p ;

p->ech=0 ; p=p1 ; /* p1->ech=0 */ p->ech=0 ;

Cazul II stanga(SD) devine:
P1=p->st ;
P2=p1->dr; p->ech=-1; p1->ech=1; carcteristicile caz II Stanga p1->dr=p2->st; p->st=p2->dr; reechilibrarea p2->st=p1; p2->dr=p; if(p2->ech= =-1) p->ech=1; else p->ech=0; if(p2->ech= =1) p1->ech=-1; else p1->ech=0; p=p2; p->ech=0;
Observatie :
Nu intotdeauna nodul *p(radacina subarborelui care se dezechilibreaza )este chiar radacina arborelui. La parcurgerea in sens invers a drumului de cautare in scopul restabiliri factorilor de echilibru ,primul nod al carui factor de echilibru ar deveni mai mic decat -;1 sau mai mare decat 1 va deveni nodul *p.

Programul C:

Scrieti programul C care permite crearea si vizualizarea unui arbore AVL.

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <conio.h>
#include <graphics.h>
#include <dos.h>

#define CALE "c:\\Borlandc\\BGI"

#define raza 10
#define timp 500
#define spatiu 40

typedef struct nod
A int cheie; int contor; int ech; struct nod *st, *dr;
S Tnod; typedef Tnod *ref;

void creare(void); void inarbore(int, ref *); void initializare_mod_grafic(void); void tip(ref, int, int, int, int, int, char *); void inordine(ref, int, int, int, int, int); void preordine(ref, int, int, int, int, int); void postordine(ref, int, int, int, int, int); void tipt(ref anod, int nivel); void inordinest(ref rad, int nivel); void insertechil(int , ref *, int *); ref Loc(int, ref);/*cauta un nod in arbore*/

ref radacina, r, q; int x, h, culoare_fundal=15,/*culoarea de fundal a nodurilor arborelui*/ culoare_scris=1, /*culoarea cu care sunt scrise nodurile arborelui*/ afisare=0;/*pt. cautare*/

void main(void)
A char op;

radacina = NULL; do
A clrscr(); printf("Sa se creeze un arbore AVL si sa se afiseze grafic\n"); printf(" C. Creare\n"); printf(" N. Insereaza un nod in arbore!\n"); printf(" F. Cauta un nod in arbore\n"); printf(" I. Afisare in mod grafic in inordine\n"); printf(" P. Afisare in mod grafic in preordine\n"); printf(" O. Afisare in mod grafic in postordine\n"); printf(" E. Iesire\n"); printf("Introduceti optiunea: "); fflush(stdin); op=toupper(getc(stdin)); switch (op)
A case 'C': creare(); initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Parcurgere in INORDINE" ); setviewport(0,30,getmaxx(), getmaxy(), 1); inordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(WHITE); outtextxy(getmaxx()/2, getmaxy()-40, "Apasati o tasta pt. a termina"); fflush(stdin);getch(); closegraph(); break;

case 'N': printf("Introduceti nodul de inserat: ");
while(scanf("%d", &x)!=1)
A printf("Introduceti un numar!\n"); fflush(stdin); printf("Introduceti nodul de inserat: ");
S h = 0; insertechil(x, &radacina, &h); initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Inserarea unui nod in arbore"); setviewport(0,30,getmaxx(), getmaxy(), 1); inordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(WHITE); outtextxy(getmaxx()/2, getmaxy()-40, "Apasati o tasta pt. a termina"); fflush(stdin);getch(); closegraph(); break;

case 'F': if(radacina==NULL)
A printf("Arbore vid!\n"); printf("Apasati o tasta pt. a continua!\n"); getch(); break;
S afisare = 0; printf("Introduceti cheia nodului de cautat: ");
while(scanf("%d", &x)==0)
A printf("Introduceti un intreg!\n"); fflush(stdin); printf("Introduceti cheia nodului de cautat: ");
S r = Loc(x, radacina); if(r == NULL)
A printf("Nodul nu exista in arbore!\n"); printf("Apasati o tasta pentru a termina!\n");getch();
S else
A afisare = 1; initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Cautarea unui nod in arbore"); setviewport(0,30,getmaxx(), getmaxy(), 1); inordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(WHITE); outtextxy(getmaxx()/2, getmaxy()-40, "Nodul a fost gasit in arbore"); fflush(stdin);getch(); closegraph();
S break;

case 'I': if(radacina==NULL)
A printf("Arborele este vid\n"); printf("Apasati o tasta pt. a continua\n");getch();
S else
A initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Parcurgere in INORDINE" ); setviewport(0,30,getmaxx(), getmaxy(), 1); inordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(WHITE); outtextxy(getmaxx()/2, getmaxy()-40, "Apasati o tasta pt. a termina"); fflush(stdin);getch(); closegraph();
S break;

case 'P': if(radacina==NULL)
A printf("Arborele este vid\n"); printf("Apasati o tasta pt. a continua\n");getch();
S else
A initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Parcurgere in PREORDINE" ); setviewport(0,30,getmaxx(), getmaxy(), 1); preordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(WHITE); outtextxy(getmaxx()/2, getmaxy()-40, "Apasati o tasta pt. a termina."); fflush(stdin);getch(); closegraph();
S break;

case 'O': if(radacina==NULL)
A printf("Arborele este vid\n"); printf("Apasati o tasta pt. a continua\n");getch();
S else
A initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Parcurgere in POSTORDINE" ); setviewport(0,30,getmaxx(), getmaxy(), 1); postordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(WHITE); outtextxy(getmaxx()/2, getmaxy()-40, "Apasati o tasta pt. a termina."); fflush(stdin);getch(); closegraph();
S break;

case 'E': break; default: printf("\nOptiune invalida !\nApasati o tasta!\n"); getch(); break;
S
S
while(op!='E');
S/*main*/

void creare(void)
A radacina = NULL; printf("Introduceti nodurile(0 pt. a termina): ");
while(scanf("%d", &x)!=1)
A printf("Introduceti un numar!"); fflush(stdin);
S
while(x!=0)
A h = 0; insertechil(x, &radacina, &h); printf("Introduceti nodurile(0 pt. a termina): ");
while(scanf("%d", &x)!=1)
A printf("Introduceti un numar!\n"); fflush(stdin); printf("Introduceti nodurile(0 pt. a termina): ");
S
S
S/*creare*/

void insertechil(int x, ref *p, int *h)
A ref p1,p2; if((*p)==NULL)
A
/* h=0 */
/* nodul nu exista,se insereaza */
(*p)=malloc(sizeof(Tnod));
(*p)->cheie=x;
(*p)->contor=1;
(*h)=1;
(*p)->ech=0; /* este nod frunza */
(*p)->st=NULL;
(*p)->dr=NULL;
S else if(x<(*p)->cheie)
A
/* continuam pe ramura stanga */ insertechil(x,&((*p)->st),h); if(*h==1) switch((*p)->ech)
A case 1: (*p)->ech=0;
*h=0; break; case 0: (*p)->ech=-1; break; case -1: /* reechilibrarea */ p1=(*p)->st; if(p1->ech==-1)
A
/* cazul 1 stanga */
(*p)->st=p1->dr; p1->dr=(*p);
(*p)->ech=0;
(*p)=p1;
S else
A
/* cazul 2 stanga,p1->ech=1 */ p2=p1->dr; p1->dr=p2->st;
(*p)->st=p2->dr; p2->st=p1; p2->dr=(*p); if(p2->ech==-1)
(*p)->ech=1; else (*p)->ech=0; if(p2->ech==1) p1->ech=-1; else p1->ech=0;
*p=p2;
S/* cazul 2*/
(*p)->ech=0;
*h=0; break; /* reechilibrarea */
S/*switch */
S/* ramura stanga */ else if(x>(*p)->cheie)
A
/* se cauta pe ramura dr */ insertechil(x,&((*p)->dr),h); if(*h==1) switch((*p)->ech)
A case -1: (*p)->ech=0;
*h=0; break; case 0: (*p)->ech=1; break; case 1: /* reechilibrarea */ p1=(*p)->dr; if(p1->ech==1)
A
/* cazul 1 stanga */
(*p)->dr=p1->st; p1->st=(*p);
(*p)->ech=0;
(*p)=p1;
S else
A
/* cazul 2 dreapta,p1->ech=-1 */ p2=p1->st; p1->st=p2->dr;
(*p)->dr=p2->st; p2->dr=p1; p2->st=(*p); if(p2->ech==1)
(*p)->ech=-1; else (*p)->ech=0; if(p2->ech==-1) p1->ech=1; else p1->ech=0;
*p=p2;
S/* cazul 2*/
(*p)->ech=0;
*h=0; break; /* reechilibrarea */
S/*switch */
S/* ramura dreapta */ else
A
/* nodul exista in arbore,increm contorul */
(*p)->contor++;
*h=0;
S
S /* insertechil */ void initializare_mod_grafic(void)
A int gdriver=DETECT, gmode, err;

initgraph(&gdriver, &gmode, CALE); err=graphresult(); if(err!=grOk)
A printf("Eroare la initializarea modului grafic: %s\n", grapherrormsg(err)); printf("Apasati o tasta pentru a termina ...\n"); getch(); exit(1);
S
S/*initializare mod grafic*/

void inordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
A static char sa10i; if(rad!=NULL)
A inordine(rad->st, nivel+1, x1, (x1+x2)/2, (x1+x2)/2, nivel*spatiu+raza); tip(rad, nivel, x1, x2, c1, c2, s); inordine(rad->dr, nivel+1, (x1+x2)/2, x2, (x1+x2)/2, nivel*spatiu+raza);
S
S/*inordine*/

void preordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
A static char sa10i; if(rad!=NULL)
A preordine(rad->st, nivel+1, x1, (x1+x2)/2, (x1+x2)/2, nivel*spatiu+raza); preordine(rad->dr, nivel+1, (x1+x2)/2, x2, (x1+x2)/2, nivel*spatiu+raza); tip(rad, nivel, x1, x2, c1, c2, s);
S
S/*preordine*/

void postordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
A static char sa10i; if(rad!=NULL)
A postordine(rad->dr, nivel+1, (x1+x2)/2, x2, (x1+x2)/2, nivel*spatiu+raza); tip(rad, nivel, x1, x2, c1, c2, s); postordine(rad->st, nivel+1, x1, (x1+x2)/2, (x1+x2)/2, nivel*spatiu+raza);
S
S/*postordine*/

void tip(ref anod, int nivel, int x1, int x2, int c1, int c2, char *s)
A if(afisare==1 && anod==r)
A culoare_scris=BLUE; culoare_fundal=RED; r = NULL;
S else
A culoare_scris=1;/*albastru*/ culoare_fundal=15;/*alb*/
S setcolor(15); line((x1+x2)/2, nivel*spatiu+raza, c1,c2+textheight("1")/2); setfillstyle(SOLID_FILL, culoare_fundal); fillellipse((x1+x2)/2, nivel*spatiu+raza, raza, raza); setcolor(culoare_scris);/*albastru*/ sprintf(s, "%d", anod->cheie); outtextxy((x1+x2)/2, nivel*spatiu+raza, s); delay(timp);
S/*tiparire grafica*/

ref Loc(int x, ref t)
A int gasit = 0;
while((gasit==0)&&(t!=NULL)) if(t->cheie == x) gasit=1; else if(x < t->cheie) t = t->st; else t= t->dr; return t;
S/*Loc*/

Laborator numarul 4

Tema:
Suprimarea unui nod dintr-un arbore AVL.
Analiza :
Tehnica care sta la baza suprimarii este cea prezenta in cazul arborilor perfect echilibrati. Cazul evident este cel in care nodul care se suprima este un nod terminal sau are un singur fiu. Daca nodul are insa doi fii, el va fi inlocuit cu cel mai din dreapta nod al subarborelui sau stang.
Modul de lucru va fi prezentat pe urmatorul arbore, din care se suprima succesiv nodurile 7,11,9,8,4,3 si 10.

Vom folosi urmatoarea stuctura de arbore AVL : typedef struct nod
A int cheie; int contor; int ech; struct nod *st,*dr;
STnod; typedef Tnod *ref; ref radacina;

Suprimarea nodului 7

Suprimarea unui nod intr-un arbore AVL se face dupa acelasi principiu ca si intr-un arbore ordonat. In cazul in care are cel mult un fiu suprimarea este directa, in caz contrar (daca are doi fii) se va inlocui cu predecesorul acestuia in inordine.

Fie p variabila pointer care contine adresa radacinii arborelui din care se face suprimarea.

0

-1

Nodul 7 este un nod frunza. Inainte de a-l sterge, subarborele de radacina 6 este echilibrat , cu p- >ech=-1.



Prin stergerea nodului 7, subarborele de radacina 6 se dezechilibreaza, dar factorii de echilibru ai nodurilor sunt inca nemodificati : p->ech=-1; p1->ech=-1;

- unde p contine adresa nodului 6 iar p1 adresa nodului 4;

0

-1

-1

Pentru reechilibrare , sa constatam ca ne aflam in cazul I stanga, deci : p1=p->st ; p1->ech=-1;
Modificarea factorilor de echilibru se propaga si mai sus :factorul de echilibru al nodului 8 devine 1.Situatia dupa echilibrare va fi : p->ech =0 ; p1->ech =0 ; p=p1 ;


1

0

0

Acelasi caz de reechilibrare am avea daca nodul *p1 (4) ar avea fiu drept pe 5 si am dori suprimarea acestuia din urma.
In consecinta, daca p->ech= -1 , p1->ech<=0 si se realizeaza stergerea unui nod in subarborele drept al acestuia, rezulta Cazul I stanga, reechilibrarea se face identic cu celalalt caz.

Suprimarea nodului 11

Inaintea suprimarii

1


0 0

0 0 -1 0

0 0

Nodul 11 are doi fii; se va inlocui cu predecesorul acestuia in inordine, cu cheia nodului10, care apoi va fi sters(nodul 11). Rezulta ca in cazul in care se realizeaza stergerea unui nod din subarborele stang al nodului *p, cu *p->ech=0, dupa suprimare p->ech=1. Factorul de echilibru pentru nodul 8 nu se modifica. Vom obtine arborele:

Dupa suprimare p->ech=1;
1

1

0 0

0 0

Suprimarea nodului 9


Inaintea suprimarii p->ech=1;
1
?p

1

0
0

0 0

Nodul 9 este nod frunza , iar P^.ech=1, unde p contine adresa noduli 10, iar p1 contine adresa nodului 13.
Dupa stergerea nodului 9, subarborele de radacina 10(P^) se dezechilibreaza si rezulta Cazul dreapta de reechilibrare(P^.ech=1,P1^.ech=0sauP1^.ech=1).


Dupa suprimare
1
?reechilibrare
?p
Cazul I dreapta
1 p1=p->dr; p1->ech=0;
0 ?p1
0

0 0

Reechilibrarea cu restabilirea factorilor de echilibrare va face ca in cazul I stanga, prin simetrie st<>dr,1<->-1:

Dupa reechilibrare: 1

-1

?p

1 0



Suprimarea nodului 8
Inainte:

1
-1


1 0

0
Nodul 8 are doi fii, se va inlocui cu cel mai din dreapta nod al subarborelui sau stang (nodul 6), dupa care cel din urma se va sterge.
Se sterge un nod in subarborele drept al nodului 4 (*p), cu p->ech=0. Dupa stergerea nodului 6 , p->ech := -1. Arborele cu fosta radacina 8, acum 6, ramane echilibrat dupa stergerea nodului 6. Nici factorul de echilibru al acestui nod nu se modifica

Dupa p->ech= -1; reechilibrare: h=0;
1
P

-1 -1

1 0

0

Suprimarea nodului 4

Inainte: p->ech= -1;

1
P

-1 -1

0 1 0

0

Nodul 4 are un singur fiu (nodul 3). Stergerea lui se realizeaza modificand referinta stanga a nodului 6 astfel incat sa indice nodul 3 :
Dupa suprimare: p

1 p1

0 -1

P2
1 0

0

Stergerea se face in subarborele stang al nodului 6(*p), cu p->ech=1, care prin stergere se dezechilibreaza. Cum p1->ech= -1, deci rezulta Cazul II dreapta de reechilibrare:
Dupa reechilibrare:

0 p? ?p1 p2=p1->st; p1->st=p2->dr;
1 0 p2->dr=p1; p->dr=p2->st; p2->st=p;

Pentru restabilirea factorilor de echilibru, sa observam ca *p2 are cel putin un fiu deci p2->ech ?A-1,0,1S. Valoarea factorilor de echilibru pentru nodurile *p,*p1, dupa reechilibrare va depinde de p2->ech:
Daca p2->ech= =1 atunci p->ech =1 ;p1->ech =0 astfel daca p2->ech= =0 atunci p->ech=0; p1->ech=0 astfel P->ech=0; p1->ech=1;

Suprimarea nodului 3

Nodul 3 este un nod frunza. Referinta stanga a nodului 6 va fi pusa pe NULL dupa stergerea nodului 3:

1

0

Arborele nu se dezechilibreaza.

Suprimarea nodului 10

Nodul 10 se va inlocui cu predecesorul sau in inordine, nodul 6, iar nodul 10 va fi sters.

P

1
P1

0

Scade in ramura stanga a nodului 10 (acum nodul 6), factorul sau de echilibru fiind 1, dupa stergere se impune reechilibrarea. Este cazul I dreapta de reechilibrare :

P

-1

1

Se observa ca reechilibrarea unui subarbore se executa numai atunci cand se reduce inaltimea acestuia. In acest sens, in functia de suprimare vom utiliza variabila h a carui valoare semnifica reducerea inaltimii subarborelui. Functia echilibru1 se aplica cand subarborele stang s-a redus in inaltime

Programul C :

Scrieti programul C care permite crearea si suprimarea unui nod dintr-un arbore AVL, a.i. si dupa suprimare arborele sa ramana tot AVL.

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <conio.h>
#include <graphics.h>
#include <dos.h>
#define CALE "c:\\Borlandc\\BGI"
#define raza 10
#define timp 500
#define spatiu 40 typedef struct nod
A int cheie; int contor; int ech; struct nod *st, *dr;
S Tnod; typedef Tnod *ref; void creare(void); void inarbore(int, ref *); void initializare_mod_grafic(void); void tip(ref, int, int, int, int, int, char *); void inordine(ref, int, int, int, int, int); void preordine(ref, int, int, int, int, int); void postordine(ref, int, int, int, int, int); void tipt(ref anod, int nivel); void inordinest(ref rad, int nivel); void insertechil(int , ref *, int *); void echilibru1(ref *, int *); void echilibru2(ref *, int *); void suprimaechil(int, ref *, int *); ref Loc(int, ref);/*cauta un nod in arbore*/ ref radacina, r, q; int x, h, culoare_fundal=15,/*culoarea de fundal a nodurilor arborelui*/ culoare_scris=1, /*culoarea cu care sunt scrise nodurile arborelui*/ afisare=0;/*pt. cautare*/

void main(void)
A char op;

radacina = NULL; do
A clrscr(); printf("Sa se creeze un arbore AVL si sa se afiseze grafic\n"); printf(" C. Creare\n"); printf(" I. Insereaza un nod in arbore!\n"); printf(" S. Sterge un nod din arbore!\n"); printf(" F. Cauta un nod in arbore\n"); printf(" A. Afisare in mod grafic in inordine\n"); printf(" E. Iesire\n"); printf("Introduceti optiunea: "); fflush(stdin); op=toupper(getc(stdin)); switch (op)
A case 'C': creare(); initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Parcurgere in INORDINE" ); setviewport(0,30,getmaxx(), getmaxy(), 1); inordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(WHITE); outtextxy(getmaxx()/2, getmaxy()-40, "Apasati o tasta pt. a termina"); fflush(stdin);getch(); closegraph(); break; case 'I': printf("Introduceti nodul de inserat: ");
while(scanf("%d", &x)!=1)
A printf("Introduceti un numar!\n"); fflush(stdin); printf("Introduceti nodul de inserat: ");
S h = 0; insertechil(x, &radacina, &h); initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Inserarea unui nod in arbore"); setviewport(0,30,getmaxx(), getmaxy(), 1); inordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(WHITE); outtextxy(getmaxx()/2, getmaxy()-40, "Apasati o tasta pt. a termina"); fflush(stdin);getch(); closegraph(); break; case 'S': if(radacina==NULL)
A printf("Arbore vid! Nu avem ce suprima!\n"); printf("Apasati o tasta pentru a continua!\n");getch(); break;
S printf("Introduceti cheia nodului de suprimat: ");
while(scanf("%d", &x)!=1)
A printf("Introduceti un numar!\n"); fflush(stdin); printf("Introduceti cheia nodului de suprimat: ");
S h = 0; suprimaechil(x, &radacina, &h); printf("Nodul cu cheia %d a fost sters din arbore!\n",x); printf("Apasati o tasta pentru a continua!\n"); getch(); break; case 'F': if(radacina==NULL)
A printf("Arbore vid!\n"); printf("Apasati o tasta pt. a continua!\n"); getch(); break;
S afisare = 0; printf("Introduceti cheia nodului de cautat: ");
while(scanf("%d", &x)==0)
A printf("Introduceti un intreg!\n"); fflush(stdin); printf("Introduceti cheia nodului de cautat: ");
S r = Loc(x, radacina); if(r == NULL)
A printf("Nodul nu exista in arbore!\n"); printf("Apasati o tasta pentru a continua!\n");getch();
S else
A afisare = 1; initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Cautarea unui nod in arbore"); setviewport(0,30,getmaxx(), getmaxy(), 1); inordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(WHITE); outtextxy(getmaxx()/2, getmaxy()-40,
"Nodul a fost gasit in arbore"); fflush(stdin);getch(); closegraph();
S break;

case 'A': if(radacina==NULL)
A printf("Arborele este vid\n"); printf("Apasati o tasta pt. a continua\n");getch();
S else
A initializare_mod_grafic(); delay(2000); settextjustify(1,1); outtextxy(getmaxx()/2, 10, "Parcurgere in INORDINE" ); setviewport(0,30,getmaxx(), getmaxy(), 1); inordine(radacina, 0, 0, getmaxx(), getmaxx()/2, raza); setcolor(WHITE); outtextxy(getmaxx()/2, getmaxy()-40, "Apasati o tasta pt. a termina"); fflush(stdin);getch(); closegraph();
S break; case 'E': break; default: printf("\nOptiune invalida !\nApasati o tasta!\n"); getch(); break;
S
S
while(op!='E');
S/*main*/

void creare(void)
A radacina = NULL; printf("Introduceti nodurile(0 pt. a termina): ");
while(scanf("%d", &x)!=1)
A printf("Introduceti un numar!"); fflush(stdin);
S
while(x!=0)
A h = 0; insertechil(x, &radacina, &h); printf("Introduceti nodurile(0 pt. a termina): ");
while(scanf("%d", &x)!=1)
A printf("Introduceti un numar!\n"); fflush(stdin); printf("Introduceti nodurile(0 pt. a termina): ");
S
S
S/*creare*/

void insertechil(int x, ref *p, int *h)
A ref p1,p2; if((*p)==NULL)
A
/* h=0 */
/* nodul nu exista,se insereaza */
(*p)=malloc(sizeof(Tnod));
(*p)->cheie=x;
(*p)->contor=1;
(*h)=1;
(*p)->ech=0; /* este nod frunza */
(*p)->st=NULL;
(*p)->dr=NULL;
S else if(x<(*p)->cheie)
A
/* continuam pe ramura stanga */ insertechil(x,&((*p)->st),h); if(*h==1) switch((*p)->ech)
A case 1: (*p)->ech=0;
*h=0; break; case 0: (*p)->ech=-1; break; case -1: /* reechilibrarea */ p1=(*p)->st; if(p1->ech==-1)
A
/* cazul 1 stanga */
(*p)->st=p1->dr; p1->dr=(*p);
(*p)->ech=0;
(*p)=p1;
S else
A
/* cazul 2 stanga,p1->ech=1 */ p2=p1->dr; p1->dr=p2->st;
(*p)->st=p2->dr; p2->st=p1; p2->dr=(*p); if(p2->ech==-1)
(*p)->ech=1; else (*p)->ech=0; if(p2->ech==1) p1->ech=-1; else p1->ech=0;
*p=p2;
S/* cazul 2*/
(*p)->ech=0;
*h=0; break; /* reechilibrarea */
S/*switch */
S/* ramura stanga */ else if(x>(*p)->cheie)
A
/* se cauta pe ramura dr */ insertechil(x,&((*p)->dr),h); if(*h==1) switch((*p)->ech)
A case -1: (*p)->ech=0;
*h=0; break; case 0: (*p)->ech=1; break; case 1: /* reechilibrarea */ p1=(*p)->dr; if(p1->ech==1)
A
/* cazul 1 stanga */
(*p)->dr=p1->st; p1->st=(*p);
(*p)->ech=0;
(*p)=p1;
S else
A
/* cazul 2 dreapta,p1->ech=-1 */ p2=p1->st; p1->st=p2->dr;
(*p)->dr=p2->st; p2->dr=p1; p2->st=(*p); if(p2->ech==1)
(*p)->ech=-1; else (*p)->ech=0; if(p2->ech==-1) p1->ech=1; else p1->ech=0;
*p=p2;
S/* cazul 2*/
(*p)->ech=0;
*h=0; break; /* reechilibrarea */
S/*switch */
S/* ramura dreapta */ else
A
/* nodul exista in arbore,increm contorul */
(*p)->contor++;
*h=0;
S
S /* insertechil */ void initializare_mod_grafic(void)
A int gdriver=DETECT, gmode, err;

initgraph(&gdriver, &gmode, CALE); err=graphresult(); if(err!=grOk)
A printf("Eroare la initializarea modului grafic: %s\n", grapherrormsg(err)); printf("Apasati o tasta pentru a termina ...\n"); getch(); exit(1);
S
S/*initializare mod grafic*/

void inordine(ref rad, int nivel, int x1, int x2, int c1, int c2)
A static char sa10i; if(rad!=NULL)
A inordine(rad->st, nivel+1, x1, (x1+x2)/2, (x1+x2)/2, nivel*spatiu+raza); tip(rad, nivel, x1, x2, c1, c2, s); inordine(rad->dr, nivel+1, (x1+x2)/2, x2, (x1+x2)/2, nivel*spatiu+raza);
S
S/*inordine*/

void tip(ref anod, int nivel, int x1, int x2, int c1, int c2, char *s)
A if(afisare==1 && anod==r)
A culoare_scris=BLUE; culoare_fundal=RED; r = NULL;
S else
A culoare_scris=1;/*albastru*/ culoare_fundal=15;/*alb*/
S setcolor(15); line((x1+x2)/2, nivel*spatiu+raza, c1,c2+textheight("1")/2); setfillstyle(SOLID_FILL, culoare_fundal); fillellipse((x1+x2)/2, nivel*spatiu+raza, raza, raza); setcolor(culoare_scris);/*albastru*/ sprintf(s, "%d", anod->cheie); outtextxy((x1+x2)/2, nivel*spatiu+raza, s); delay(timp);
S/*tiparire grafica*/

ref Loc(int x, ref t)
A int gasit = 0;
while((gasit==0)&&(t!=NULL)) if(t->cheie == x) gasit=1; else if(x < t->cheie) t = t->st; else t= t->dr; return t;
S/*Loc*/

void echilibru2(ref *p, int *h)
A ref p1, p2;

switch((*p)->ech)
A case 1:(*p)->ech = 0; break; case 0:(*p)->ech = -1;
*h = 0; break; case -1: /* reechilibrare */ p1 = (*p)->st; if(p1->ech<=0) /* cazul I stanga */
A
(*p)->st = p1->dr; p1->dr = *p; if(p1->ech==0)
A
(*p)->ech = -1; p1->ech = 1;
*h = 0;
S else
A
(*p)->ech = 0; p1->ech = 0;
S
*p = p1;
S else /* cazul II stanga */
A p2 = p1->dr; p1->dr = p2->st;
(*p)->st = p2->dr; p2->dr = (*p); p2->st = p1; if(p2->ech==-1)
A
(*p)->ech = 1; p1->ech = 0;
S else if(p2->ech==0)




Colt dreapta
Creeaza cont
Comentarii:

Nu ai gasit ce cautai? Crezi ca ceva ne lipseste? Lasa-ti comentariul si incercam sa te ajutam.
Esti satisfacut de calitarea acestui referat, eseu, cometariu? Apreciem aprecierile voastre.

Nume (obligatoriu):

Email (obligatoriu, nu va fi publicat):

Site URL (optional):


Comentariile tale: (NO HTML)




Noteaza referatul:
In prezent referatul este notat cu: ? (media unui numar de ? de note primite).

2345678910



 
Copyright© 2005 - 2024 | Trimite referat | Harta site | Adauga in favorite
Colt dreapta