Curs 4 - Arbori Binari 1u1fy
This document was ed by and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this report form. Report r6l17
Overview 4q3b3c
& View Curs 4 - Arbori Binari as PDF for free.
More details 26j3b
- Words: 1,249
- Pages: 7
//arbori binari #include
//pt cout #include <stdlib.h> using namespace std;//pt scrierea prescurtata, fara std::cout, etc typedef int info; typedef struct nod{ info informatie; nod *ss;//subarbore stang nod *sd;//subarbore drept } NOD, *PNOD;//arbore de cautare typedef struct nodAVL{ int informatie; int echilibru; nodAVL *ss, *sd; } NODAVL, *PNODAVL;//arbore de cautare echilibrat PNOD arboreDinVector(int *v, int dim); void arboreAfisareParanteze(PNOD rad);//RSD - preordine void stergeArbore(PNOD rad); int nrNoduri(PNOD rad); int inaltime(PNOD rad); PNODAVL insereazaAVL(PNODAVL rad, int nr); void arboreAfisareAVL(PNODAVL rad); PNODAVL stergeNodAVL(int nr, PNODAVL rad); PNODAVL stergeNodAVLechil(int nr, PNODAVL rad); bool cautaInformatieAVL(PNODAVL rad, int informatie); int main(){ info tablou[7] = {1, -2, 3, 4, -5, -1, 2}; PNOD rad = NULL; cout << "Arbore din vector" << endl; rad = arboreDinVector(tablou, 7); arboreAfisareParanteze(rad); cout << endl; cout << "Arborele are " << nrNoduri(rad) << " noduri" << endl; cout << "Arborele are inaltimea " << inaltime(rad) << endl; cout << "Stergem arborele"; stergeArbore(rad); rad = NULL; arboreAfisareParanteze(rad); cout << endl; PNODAVL radAVL = NULL; int tablouAVL[7] = {1, 2, 3, 4, 5, 6, 7};
for(int i=0; i<7; i++) radAVL = insereazaAVL(radAVL,tablouAVL[i]); arboreAfisareAVL(radAVL); cout << endl; // l; // // // // // // // // // // // // // // // // // // // //
cout << "Cauta 5" << endl << cautaInformatieAVL(radAVL,5) << endl << end cout << "Sterge 4" << endl; radAVL = stergeNodAVL(4, radAVL); arboreAfisareAVL(radAVL); cout << endl << endl; cout << "Sterge 5" << endl; radAVL = stergeNodAVL(5, radAVL); arboreAfisareAVL(radAVL); cout << endl << endl; cout << "Adauga 4" << endl; radAVL = insereazaAVL(radAVL, 4); arboreAfisareAVL(radAVL); cout << endl << endl; cout << "Adauga 5" << endl; radAVL = insereazaAVL(radAVL, 5); arboreAfisareAVL(radAVL); cout << endl << endl; cout << "Sterge 2" << endl; radAVL = stergeNodAVL(2, radAVL); arboreAfisareAVL(radAVL); cout << endl << endl; cout << "Sterge 3" << endl; radAVL = stergeNodAVL(3, radAVL); arboreAfisareAVL(radAVL); cout << endl << endl; cout << "Sterge 1" << endl; radAVL = stergeNodAVL(1, radAVL); arboreAfisareAVL(radAVL); cout << endl << endl; radAVL = insereazaAVL(radAVL, 3); arboreAfisareAVL(radAVL); cout << endl << endl; radAVL = insereazaAVL(radAVL, 2); arboreAfisareAVL(radAVL); cout << endl << endl; radAVL = insereazaAVL(radAVL, 1); arboreAfisareAVL(radAVL); cout << endl << endl; cout << "Sterge 2 cu reechilibrare arbore" << endl; radAVL = stergeNodAVLechil(2, radAVL); arboreAfisareAVL(radAVL);
cout << endl << endl; cout << "Sterge 3 cu reechilibrare arbore" << endl; radAVL = stergeNodAVLechil(3, radAVL); arboreAfisareAVL(radAVL); cout << endl << endl; cout << "Sterge 1 cu reechilibrare arbore" << endl; radAVL = stergeNodAVLechil(1, radAVL); arboreAfisareAVL(radAVL); cout << endl << endl; system("PAUSE");//in stdlib return 0; } PNOD arboreDinVector(int *v, int dim){ PNOD rad = new NOD, temp, radTemp; if(!rad){ cout << "Nu mai este loc liber in memorie"; return rad; } rad->informatie = v[0]; rad->ss = NULL; rad->sd = NULL; for(int i = 1; i < dim; i++){ temp = new NOD; if(!temp){ cout << "Nu mai este loc liber in memorie"; return rad; } temp->informatie = v[i]; temp->ss = NULL; temp->sd = NULL; radTemp = rad; while(radTemp){ if(radTemp->informatie > v[i]) if(radTemp->ss == NULL){ radTemp->ss = temp; break; } else radTemp = radTemp->ss; else if(radTemp->sd == NULL){ radTemp->sd = temp; break; } else radTemp = radTemp->sd; } } return rad; } void arboreAfisareParanteze(PNOD rad){ if(rad){ cout << rad->informatie; if((rad->ss!=NULL)||(rad->sd!=NULL)){
cout << '('; arboreAfisareParanteze(rad->ss); cout << ","; arboreAfisareParanteze(rad->sd); cout << ")"; } } else cout << "-"; } void stergeArbore(PNOD rad){ if(rad->ss) stergeArbore(rad->ss); if(rad->sd) stergeArbore(rad->sd); delete rad; } int nrNoduri(PNOD rad){ if ( rad == NULL ) return 0; //arbore gol //avem cel putin nodul radacina return (1 + nrNoduri(rad->ss) + nrNoduri(rad->sd)); } int inaltime(PNOD rad){ if ( rad == NULL ) return 0; //arbore gol int inaltimeSS, inaltimeSD; //avem cel putin nodul radacina inaltimeSS = inaltime(rad->ss); inaltimeSD = inaltime(rad->sd); return (inaltimeSS>inaltimeSD)?(inaltimeSS+1):(inaltimeSD+1); // Return the total }
//arbori AVL int inaltimeAVL(PNODAVL rad){ if ( rad == NULL ) return 0; //arbore gol int inaltimeSS, inaltimeSD; //avem cel putin nodul radacina inaltimeSS = inaltimeAVL(rad->ss); inaltimeSD = inaltimeAVL(rad->sd); return ((inaltimeSS>inaltimeSD)?(inaltimeSS+1):(inaltimeSD+1)); // Return t he total } void calculEchilibru(PNODAVL rad){ rad->echilibru = inaltimeAVL(rad->sd) - inaltimeAVL(rad->ss); } PNODAVL sRotireStanga(PNODAVL rad){//rotire simpla stanga PNODAVL temp; temp = rad->sd; rad->sd = temp->ss; temp->ss = rad; calculEchilibru(rad); calculEchilibru(temp); rad = temp;
return rad; } PNODAVL sRotireDreapta(PNODAVL rad){//rotire simpla dreapta PNODAVL temp; temp = rad->ss; rad->ss = temp->sd; temp->sd = rad; calculEchilibru(rad); calculEchilibru(temp); rad = temp; return rad; } PNODAVL dRotireStanga(PNODAVL rad){//rotire dubla right-left rad->sd = sRotireDreapta(rad->sd); rad = sRotireStanga(rad); return rad; } PNODAVL dRotireDreapta(PNODAVL rad){//rotire dubla left-right rad->ss = sRotireStanga(rad->ss); rad = sRotireDreapta(rad); return rad; } PNODAVL echilibrare(PNODAVL rad){ PNODAVL temp; calculEchilibru(rad); if(rad->echilibru == -2){ temp = rad->ss; if (temp->echilibru == 1) rad = dRotireDreapta(rad); else rad = sRotireDreapta(rad); } else if(rad->echilibru == 2){ temp = rad->sd; if (temp->echilibru == -1) rad = dRotireStanga(rad); else rad = sRotireStanga(rad); } return rad; } PNODAVL insereazaAVL(PNODAVL rad, int nr){ if(!rad){ rad = new NODAVL; rad->informatie = nr; rad->echilibru = 0; rad->sd = NULL; rad->ss = NULL; return rad; } else if (nr < rad->informatie) rad->ss = insereazaAVL(rad->ss, nr); else if (nr > rad->informatie) rad->sd = insereazaAVL(rad->sd, n r); else printf("Nodul exista deja"); rad = echilibrare(rad); return rad; } void arboreAfisareAVL(PNODAVL rad){
if(rad){ cout << rad->informatie; if((rad->ss!=NULL)||(rad->sd!=NULL)){ cout << "("; arboreAfisareAVL(rad->ss); cout << ","; arboreAfisareAVL(rad->sd); cout << ")"; } } else cout << "-"; } PNODAVL removeMin(PNODAVL rad){//sterge val minima din arbore PNODAVL temp = rad; if (!rad) cout << "arbore gol" << endl; else if (rad->ss) rad->ss = removeMin(rad->ss);//parcurgem arborele pe s tanga else{ rad = rad->sd;//leg sd si eliberez radacina delete temp; } return rad; } PNODAVL stergeNodAVL(int nr, PNODAVL rad){//sterge nr din arbore, neconsiderand mentinerea echilibrului arborelui PNODAVL temp = rad; if (!rad) cout << "nu exista acest nr in arbore" << endl; else if(nr < rad->informatie) rad->ss = stergeNodAVL(nr, rad->ss); else if(nr > rad->informatie) rad->sd = stergeNodAVL(nr, rad->sd ); else if (rad->ss != NULL && rad->sd != NULL){//am gasit nr, si are si ss si sd temp = temp->sd;//cautam val cea mai mica in sd while(temp->ss) temp = temp->ss; rad->informatie = temp->informatie; rad->sd = removeMin(rad->sd);//si o eliminam } else{ rad = (rad->ss != NULL) ? rad->ss : rad>sd; //atasam unul din copii radacinii delete temp;//eliberare vechea radacina } return rad; } PNODAVL reechilibrare(PNODAVL rad, int nr){ if(!rad) return NULL; if(nr < rad->informatie) rad->ss = reechilibrare(rad->ss, nr); else if (nr > rad->informatie) rad->sd = reechilibrare(rad->sd, nr); rad = echilibrare(rad); return rad; } PNODAVL stergeNodAVLechil(int nr, PNODAVL rad){//sterge nr din arbore, neconside rand mentinerea echilibrului arborelui si echilibreaza apoi arborele if((rad->ss == NULL)&&(rad->sd == NULL)) {delete rad; return NULL;}
PNODAVL curent = rad, anterior = NULL; while(curent){ if(nr < curent->informatie) {anterior = curent; curent = curent ->ss;} else if(nr > curent->informatie) {anterior = curent; curent = cu rent->sd;} else if(curent->ss != NULL && curent->sd != NULL){//am gasit nr, si are si ss si sd PNODAVL temp = curent->sd, anteriorTemp = NULL;//cautam val cea mai mica in sd while(temp->ss){ anteriorTemp = temp; temp = temp->ss; } curent->informatie = temp->informatie; curent->sd = removeMin(curent->sd);//si o eliminam if(anteriorTemp) rad = reechilibrare(rad, anteriorTemp-> informatie); break; } else{ PNODAVL temp; temp = (curent->ss != NULL) ? curent->ss : curent->sd;// atasam unul din copii radacinii if(anterior == NULL) return temp; if(anterior->ss->informatie == nr) anterior->ss = temp; else anterior->sd = temp; rad = reechilibrare(rad, anterior->informatie); delete curent;//eliberare nod break; } } if (!curent) cout << "nu exista acest nr in arbore" << endl; return rad; } bool cautaInformatieAVL(PNODAVL rad, int informatie){ bool temp = false; if(!rad) return temp; // else cout << rad->informatie; if(rad->informatie == informatie) temp = true; if(!temp) temp = cautaInformatieAVL(rad->ss, informatie); if(!temp) temp = cautaInformatieAVL(rad->sd, informatie); return temp; }
for(int i=0; i<7; i++) radAVL = insereazaAVL(radAVL,tablouAVL[i]); arboreAfisareAVL(radAVL); cout << endl; // l; // // // // // // // // // // // // // // // // // // // //
cout << "Cauta 5" << endl << cautaInformatieAVL(radAVL,5) << endl << end cout << "Sterge 4" << endl; radAVL = stergeNodAVL(4, radAVL); arboreAfisareAVL(radAVL); cout << endl << endl; cout << "Sterge 5" << endl; radAVL = stergeNodAVL(5, radAVL); arboreAfisareAVL(radAVL); cout << endl << endl; cout << "Adauga 4" << endl; radAVL = insereazaAVL(radAVL, 4); arboreAfisareAVL(radAVL); cout << endl << endl; cout << "Adauga 5" << endl; radAVL = insereazaAVL(radAVL, 5); arboreAfisareAVL(radAVL); cout << endl << endl; cout << "Sterge 2" << endl; radAVL = stergeNodAVL(2, radAVL); arboreAfisareAVL(radAVL); cout << endl << endl; cout << "Sterge 3" << endl; radAVL = stergeNodAVL(3, radAVL); arboreAfisareAVL(radAVL); cout << endl << endl; cout << "Sterge 1" << endl; radAVL = stergeNodAVL(1, radAVL); arboreAfisareAVL(radAVL); cout << endl << endl; radAVL = insereazaAVL(radAVL, 3); arboreAfisareAVL(radAVL); cout << endl << endl; radAVL = insereazaAVL(radAVL, 2); arboreAfisareAVL(radAVL); cout << endl << endl; radAVL = insereazaAVL(radAVL, 1); arboreAfisareAVL(radAVL); cout << endl << endl; cout << "Sterge 2 cu reechilibrare arbore" << endl; radAVL = stergeNodAVLechil(2, radAVL); arboreAfisareAVL(radAVL);
cout << endl << endl; cout << "Sterge 3 cu reechilibrare arbore" << endl; radAVL = stergeNodAVLechil(3, radAVL); arboreAfisareAVL(radAVL); cout << endl << endl; cout << "Sterge 1 cu reechilibrare arbore" << endl; radAVL = stergeNodAVLechil(1, radAVL); arboreAfisareAVL(radAVL); cout << endl << endl; system("PAUSE");//in stdlib return 0; } PNOD arboreDinVector(int *v, int dim){ PNOD rad = new NOD, temp, radTemp; if(!rad){ cout << "Nu mai este loc liber in memorie"; return rad; } rad->informatie = v[0]; rad->ss = NULL; rad->sd = NULL; for(int i = 1; i < dim; i++){ temp = new NOD; if(!temp){ cout << "Nu mai este loc liber in memorie"; return rad; } temp->informatie = v[i]; temp->ss = NULL; temp->sd = NULL; radTemp = rad; while(radTemp){ if(radTemp->informatie > v[i]) if(radTemp->ss == NULL){ radTemp->ss = temp; break; } else radTemp = radTemp->ss; else if(radTemp->sd == NULL){ radTemp->sd = temp; break; } else radTemp = radTemp->sd; } } return rad; } void arboreAfisareParanteze(PNOD rad){ if(rad){ cout << rad->informatie; if((rad->ss!=NULL)||(rad->sd!=NULL)){
cout << '('; arboreAfisareParanteze(rad->ss); cout << ","; arboreAfisareParanteze(rad->sd); cout << ")"; } } else cout << "-"; } void stergeArbore(PNOD rad){ if(rad->ss) stergeArbore(rad->ss); if(rad->sd) stergeArbore(rad->sd); delete rad; } int nrNoduri(PNOD rad){ if ( rad == NULL ) return 0; //arbore gol //avem cel putin nodul radacina return (1 + nrNoduri(rad->ss) + nrNoduri(rad->sd)); } int inaltime(PNOD rad){ if ( rad == NULL ) return 0; //arbore gol int inaltimeSS, inaltimeSD; //avem cel putin nodul radacina inaltimeSS = inaltime(rad->ss); inaltimeSD = inaltime(rad->sd); return (inaltimeSS>inaltimeSD)?(inaltimeSS+1):(inaltimeSD+1); // Return the total }
//arbori AVL int inaltimeAVL(PNODAVL rad){ if ( rad == NULL ) return 0; //arbore gol int inaltimeSS, inaltimeSD; //avem cel putin nodul radacina inaltimeSS = inaltimeAVL(rad->ss); inaltimeSD = inaltimeAVL(rad->sd); return ((inaltimeSS>inaltimeSD)?(inaltimeSS+1):(inaltimeSD+1)); // Return t he total } void calculEchilibru(PNODAVL rad){ rad->echilibru = inaltimeAVL(rad->sd) - inaltimeAVL(rad->ss); } PNODAVL sRotireStanga(PNODAVL rad){//rotire simpla stanga PNODAVL temp; temp = rad->sd; rad->sd = temp->ss; temp->ss = rad; calculEchilibru(rad); calculEchilibru(temp); rad = temp;
return rad; } PNODAVL sRotireDreapta(PNODAVL rad){//rotire simpla dreapta PNODAVL temp; temp = rad->ss; rad->ss = temp->sd; temp->sd = rad; calculEchilibru(rad); calculEchilibru(temp); rad = temp; return rad; } PNODAVL dRotireStanga(PNODAVL rad){//rotire dubla right-left rad->sd = sRotireDreapta(rad->sd); rad = sRotireStanga(rad); return rad; } PNODAVL dRotireDreapta(PNODAVL rad){//rotire dubla left-right rad->ss = sRotireStanga(rad->ss); rad = sRotireDreapta(rad); return rad; } PNODAVL echilibrare(PNODAVL rad){ PNODAVL temp; calculEchilibru(rad); if(rad->echilibru == -2){ temp = rad->ss; if (temp->echilibru == 1) rad = dRotireDreapta(rad); else rad = sRotireDreapta(rad); } else if(rad->echilibru == 2){ temp = rad->sd; if (temp->echilibru == -1) rad = dRotireStanga(rad); else rad = sRotireStanga(rad); } return rad; } PNODAVL insereazaAVL(PNODAVL rad, int nr){ if(!rad){ rad = new NODAVL; rad->informatie = nr; rad->echilibru = 0; rad->sd = NULL; rad->ss = NULL; return rad; } else if (nr < rad->informatie) rad->ss = insereazaAVL(rad->ss, nr); else if (nr > rad->informatie) rad->sd = insereazaAVL(rad->sd, n r); else printf("Nodul exista deja"); rad = echilibrare(rad); return rad; } void arboreAfisareAVL(PNODAVL rad){
if(rad){ cout << rad->informatie; if((rad->ss!=NULL)||(rad->sd!=NULL)){ cout << "("; arboreAfisareAVL(rad->ss); cout << ","; arboreAfisareAVL(rad->sd); cout << ")"; } } else cout << "-"; } PNODAVL removeMin(PNODAVL rad){//sterge val minima din arbore PNODAVL temp = rad; if (!rad) cout << "arbore gol" << endl; else if (rad->ss) rad->ss = removeMin(rad->ss);//parcurgem arborele pe s tanga else{ rad = rad->sd;//leg sd si eliberez radacina delete temp; } return rad; } PNODAVL stergeNodAVL(int nr, PNODAVL rad){//sterge nr din arbore, neconsiderand mentinerea echilibrului arborelui PNODAVL temp = rad; if (!rad) cout << "nu exista acest nr in arbore" << endl; else if(nr < rad->informatie) rad->ss = stergeNodAVL(nr, rad->ss); else if(nr > rad->informatie) rad->sd = stergeNodAVL(nr, rad->sd ); else if (rad->ss != NULL && rad->sd != NULL){//am gasit nr, si are si ss si sd temp = temp->sd;//cautam val cea mai mica in sd while(temp->ss) temp = temp->ss; rad->informatie = temp->informatie; rad->sd = removeMin(rad->sd);//si o eliminam } else{ rad = (rad->ss != NULL) ? rad->ss : rad>sd; //atasam unul din copii radacinii delete temp;//eliberare vechea radacina } return rad; } PNODAVL reechilibrare(PNODAVL rad, int nr){ if(!rad) return NULL; if(nr < rad->informatie) rad->ss = reechilibrare(rad->ss, nr); else if (nr > rad->informatie) rad->sd = reechilibrare(rad->sd, nr); rad = echilibrare(rad); return rad; } PNODAVL stergeNodAVLechil(int nr, PNODAVL rad){//sterge nr din arbore, neconside rand mentinerea echilibrului arborelui si echilibreaza apoi arborele if((rad->ss == NULL)&&(rad->sd == NULL)) {delete rad; return NULL;}
PNODAVL curent = rad, anterior = NULL; while(curent){ if(nr < curent->informatie) {anterior = curent; curent = curent ->ss;} else if(nr > curent->informatie) {anterior = curent; curent = cu rent->sd;} else if(curent->ss != NULL && curent->sd != NULL){//am gasit nr, si are si ss si sd PNODAVL temp = curent->sd, anteriorTemp = NULL;//cautam val cea mai mica in sd while(temp->ss){ anteriorTemp = temp; temp = temp->ss; } curent->informatie = temp->informatie; curent->sd = removeMin(curent->sd);//si o eliminam if(anteriorTemp) rad = reechilibrare(rad, anteriorTemp-> informatie); break; } else{ PNODAVL temp; temp = (curent->ss != NULL) ? curent->ss : curent->sd;// atasam unul din copii radacinii if(anterior == NULL) return temp; if(anterior->ss->informatie == nr) anterior->ss = temp; else anterior->sd = temp; rad = reechilibrare(rad, anterior->informatie); delete curent;//eliberare nod break; } } if (!curent) cout << "nu exista acest nr in arbore" << endl; return rad; } bool cautaInformatieAVL(PNODAVL rad, int informatie){ bool temp = false; if(!rad) return temp; // else cout << rad->informatie; if(rad->informatie == informatie) temp = true; if(!temp) temp = cautaInformatieAVL(rad->ss, informatie); if(!temp) temp = cautaInformatieAVL(rad->sd, informatie); return temp; }
Related Documents 171j1w
Curs 4 - Arbori Binari 1u1fy
December 2021 0
Curs 4 4q1c65
August 2021 0
Curs 4 4q1c65
August 2021 0
Curs Filosofie 4 244l4c
November 2019 9
Curs 4 Viroze Cutanate 5o6rt
November 2021 0
Scambio Di Binari 175m3b
October 2021 0More Documents from "Adriana" 73k5z
2c82t
March 2021 0
Caracterizarea Lui Harap-alb [pdf] 5u53
August 2021 0
Crescendo Com O Eneagrama Na Espiritualidade, De Pe Domingos Cunha 662q2w
August 2022 0
Sdr.sevraj Etanolic 183872
November 2019 93
istracion+de+recursos+humanos+16a.+ed.+scott+snell 4m706h
October 2019 86