06[1]. arbori (rezumat studenti)

Arbori binari (C++ partea 6)

1. Arbori binari.........................................................................................................................31.1. Crearea şi parcurgerea RSD, SRD, SDR (afişarea) unui arbore binar..........................61.2. Ştergerea unui nod dintr-un arbore binar....................................................................101.3. Inserarea unui nod într-un arbore binar.......................................................................141.4. Numărarea nodurilor şi determinarea numărului de niveluri......................................161.5. Programul complet......................................................................................................17

Năchilă Cătălin – Laborator UPG – 2 –


1. Arbori binari

Un arbore binar este un arbore în care fiecare vârf are cel mult doi descendenţi făcându-se distincţie clară între descendentul drept şi descendentul stâng al fiecărui vârf.

Pentru discuţiile referitoare la arbori este necesară o terminologie specială: – fiecare element este numit nod;– primul element dintr-un arbore se numeşte rădăcină;– celelalte noduri formează fiecare câte un arbore; aceşti arbori se numesc subarbori;– într-un arbore există noduri cărora nu le mai corespund subarbori; un astfel de nod se numeşte

nod terminal sau frunză;– un nod rădăcină este numit nod tată; rădăcina unui subarbore se numeşte nod fiu; – rădăcina unui arbore se află pe nivelul 1; dacă un nod are nivelul m atunci fii lui au nivelul m + 1;

– prin înălţimea arborelui înţelegem numărul total de niveluri al unui arbore determină .Un arbore binar în care fiecare nod care nu este terminal are exact doi descendenţi se

numeşte arbore binar complet.

Pentru utilizarea nodurilor unui arbore binar vom folosi o structura cu următoarele câmpuri:– inf – informaţia conţinuta in nod– st – adresa nodului descendent stâng;– dr – adresa nodului descendent drept.

DateAdresă

descendent stâng

Adresă descendent

drept

infst dr

struct NOD{int inf;struct NOD *st,*dr;};



Exemplul 1 – (Structura unui arbore):

10

15

25

8

9

7

3

10Ad 7 Ad 15

7Ad 3 Ad 9 15NULL Ad 25

9Ad 8 NULL3NULL NULL 25NULL NULL

8NULL NULL

Prin parcurgerea (traversarea) unui arbore se înţelege examinarea în mod sistematic a nodurilor sale astfel încât fiecare nod sa fie parcurs o singura dată.

Există trei moduri de parcurgere (recursivă) a arborilor binari:

a) Preordine (RSD) b) Inordine (SRD)– se vizitează rădăcina; – se traversează arborele stâng;– se traversează arborele stâng; – se vizitează rădăcina;– se traversează arborele drept. – se traversează arborele drept.

c) Postordine (SDR)– se traversează arborele stâng;– se traversează arborele drept;– se vizitează rădăcina.



Exemplul 1 (Parcurgere): Fie arborele:

1

2

4

5

3

7

8

6

– parcurs în preordine (RSD): 1, 2, 4, 5, 3, 6, 7, 8;

– parcurs în inordine (SRD): 4, 5, 2, 1, 6, 3, 8, 7;

– parcurs în postordine (SDR): 5, 4, 2, 6, 8, 7, 3, 1.

Exemplul 2 – (Structura unui arbore & Parcurgere): Fie arborele:

10

15

25

8

9

7

3

– parcurs în preordine: 10, 7, 3, 9, 8, 15, 25;

– parcurs în inordine: 3, 7, 8, 9, 10, 15, 25;

– parcurs în postordine: 3, 8, 9, 7, 25, 15, 10.



Structura arborelui:

10Ad 7 Ad 15

7Ad 3 Ad 9 15NULL Ad 25

9Ad 8 NULL3NULL NULL 25NULL NULL

8NULL NULL

1.1. Crearea şi parcurgerea RSD, SRD, SDR (afişarea) unui arbore binar

# include <stdio.h># include <conio.h># include <alloc.h># include <stdlib.h># define NEW (NOD*)malloc(sizeof(NOD));

struct NOD{int inf;struct NOD *st,*dr;};

/////////////////// Crearea arborelui by necNOD *creare(){NOD *p;int nr;p=NEW;printf("Nr=");scanf("%d",&nr);p->inf=nr;p->st=NULL;



p->dr=NULL;printf("Introducem arbore in stanga pentru nodul cu informatia %d (d/n)? \n",nr);if(getch()=='d') p->st=creare();printf("Introducem arbore in dreapta pentru nodul cu informatia %d (d/n)? \n",nr);if(getch()=='d') p->dr=creare();return p;}

/////////////////// Parcurgerea RSD arborelui by necvoid parc_preord (NOD *p){if(p!=NULL)

{ printf("\t Nr=%d", p->inf); parc_preord(p->st); parc_preord(p->dr);}

}

/////////////////// Parcurgerea SRD arborelui by necvoid parc_inord (NOD *p){if(p!=NULL)

{ parc_inord(p->st); printf("\t Nr=%d", p->inf); parc_inord(p->dr);}

}

/////////////////// Parcurgerea SDR arborelui by necvoid parc_postord (NOD *p){if(p!=NULL)

{ parc_postord(p->st); parc_postord(p->dr); printf("\t Nr=%d", p->inf);}

}



/////////////////// Stergerea arborelui by necvoid stergarbore(NOD *p){if (p!=NULL)

{stergarbore(p->st);stergarbore(p->dr);delete p;}

}

/////////////////// Afisare spatii by necvoid spatii(int n){int i;for(i=0;i<n;i++)putchar(' ');}

/////////////////// Afisare arbore by necvoid afisare(int n, int f, int k, int vb, int *vn){int i;spatii(4);if(n)

{for(i=1;i<n;i++)

{if(vn[i]) putchar(' ');else putchar('|');spatii(4);}

if(f) putchar('|');else putchar('|');for(i=0;i<4;i++) putchar('-');}

if(vb) printf("%d\n",k);else printf("...\n");}



/////////////////// Afisare pe niveluri by necvoid afisare_nivel (NOD *p, int n=0){static int vn[50],f=1;if(p)

{afisare(n,f,p->inf,1,vn);if(p->st || p->dr)

{f=1;vn[n+1]=0;afisare_nivel(p->st,n+1);}

if(p->st || p->dr){f=0;vn[n+1]=1;afisare_nivel(p->dr,n+1);}

}else afisare(n,f,10,0,vn);}

/////////////////// Programul principal by necvoid main(){NOD *rad;int nr,nivel,nrnou,nrsters;clrscr();rad=creare();printf("--------------------------------------------------- \n");printf("Parcurgere preordine \n");parc_preord(rad);printf("\n");

printf("Parcurgere inordine \n");parc_inord(rad);printf("\n");

printf("Parcurgere postordine \n");parc_postord(rad);printf("\n");

printf("\n");printf("Afisarea pe niveluri: \n");afisare_nivel(rad);



printf("\n");getchar();getchar();}

1.2. Ştergerea unui nod dintr-un arbore binar

Aceasta operaţie va avea în vedere faptul că după efectuarea ştergerii nodului dorit, arborele va trebui să rămână tot arbore binar. Funcţia de ştergere a unui nod trebuie mai întâi sa efectueze căutarea nodului cu informaţia utilă dorită. Ştergerea efectiva a nodului va avea două cazuri:

Cazul 1) Nodul de şters are cel puţin un descendent vid, caz în care se reactualizează legătura nodului părinte şi se şterge fizic nodul (funcţia din program este stergerenod):

10

15

25

7

9

5

3

10

15

257

5

3

Înainte de ştergere După ştergerea nodului 9

Cazul 2) Nodul de şters are doi fii. Nodul respectiv nu se va şterge fizic.Informaţia lui va fi înlocuită cu informaţia celui mai din stânga nod al subarborelui drept sau cu informaţia a celui mai din dreapta nod al subarborelui stâng, care apoi va fi şters (nodul are informaţia imediat mai mare, respectiv imediat mai mică, decât informaţia nodului ce va trebui şters, deci arborele în ansamblu va rămâne tot de căutare) (funcţia din program este sterg):

10

15

25

7

9

5

3

Înainte de ştergere După ştergerea nodului 5

8

10

15

25

8

9

7

3

Funcţia va returna informaţia nodului care se va şterge fizic pentru a înlocui informaţia nodului căutat pentru a fi şters.



Funcţia de ştergere a unui nod este:

///////////////// Stergerea unui nod cu doi descendenti by necint sterg(NOD *&pa)

{if(pa->st) return sterg(pa->st);else

{NOD *a=pa;int k=a->inf;pa=pa->dr;free(a);

return k;}

}///// Stergerea unui nod cu cel putin nu descendent vid by necvoid stergerenod(NOD *& p, int k){NOD *aux;if(p==NULL) printf("\n Nodul %d nu exista ",p->inf);else if(k<p->inf) stergerenod(p->st,k);

elseif(k>p->inf) stergerenod(p->dr,k);else

{aux=p;if(!aux->dr)

{p=aux->st;free(aux);}

elseif(!aux->st)

{p=aux->dr;free(aux);}

else p->inf=sterg(p->dr);}

}



În programul principal se va adăuga secvenţa:printf("----------------------------------------------- \n");printf("Nodul care se sterge = ");scanf("%d",&nrsters);stergerenod(rad,nrsters);

printf("Parcurgere preordine \n");parc_preord(rad);printf("\n");printf("Parcurgere inordine \n");parc_inord(rad);printf("\n");printf("Parcurgere postordine \n");parc_postord(rad);printf("\n");

printf("Afisarea pe niveluri: \n");afisare_nivel(rad);

1.3. Inserarea unui nod într-un arbore binar

Fie arborele:

10

15

25

6

9

7

3

Inserăm nodurile 2, 4, 8, 11, 16, 30. Poziţia lor va fi următoarea:

10

157

11 253 9

42 30166

8



Funcţia de inserare a unui nod este:

/////////////////// Inserare nod by necvoid inserare(NOD *&p,int x){NOD *pnou;if (p==NULL)

{pnou=NEWpnou->inf=x;pnou->st=NULL;pnou->dr=NULL;p=pnou;}

elseif (p->inf>x)

inserare(p->st,x);else

if (p->inf<x)inserare(p->dr,x);

elseprintf("Elementul deja exista! \n");

}

În programul principal se va adăuga secvenţa:

printf("--------------------------------------------------- \n");printf("Numarul de inserat este=");scanf("%d",&nrnou);inserare(rad,nrnou);





1.4. Numărarea nodurilor şi determinarea numărului de niveluri

Funcţiile sunt:

/////////////////// Maximul dintre doua nr by necint max(int x,int y){if (x<y)

return y;else return x;}

/////////////////// Numararea nodurilor arborelui by necint nrnod(NOD *p){if(p!=NULL) return 1+nrnod(p->st)+nrnod(p->dr);else return 0;}

//////// Determinarea numarului de niveluri ale arborelui by necint inaltime(NOD *p){int stanga, dreapta;if(p!=NULL) return 1+max(inaltime(p->st),inaltime(p->dr));else return 0;}

În programul principal se va adăuga secvenţa:

nr=nrnod(rad);printf("Numarul de noduri este=%d \n",nr);nivel=inaltime(rad);printf("Inaltimea este=%d \n",nivel);



1.5. Programul complet # include <stdio.h># include <conio.h># include <alloc.h># include <stdlib.h># define NEW (NOD*)malloc(sizeof(NOD));struct NOD{int inf;struct NOD *st,*dr;};

/////////////////// Crearea arborelui by necNOD *creare(){NOD *p;int nr;p=NEW;printf("Nr=");scanf("%d",&nr);p->inf=nr;p->st=NULL;p->dr=NULL;printf("Introducem arbore in stanga pentru nodul cu informatia %d (d/n)? \n",nr);if(getch()=='d') p->st=creare();printf("Introducem arbore in dreapta pentru nodul cu informatia %d (d/n)? \n",nr);if(getch()=='d') p->dr=creare();return p;}

/////////////////// Parcurgerea RSD arborelui by necvoid parc_preord (NOD *p){if(p!=NULL)

{ printf("\t Nr=%d", p->inf); parc_preord(p->st); parc_preord(p->dr);}

}



/////////////////// Parcurgerea SRD arborelui by necvoid parc_inord (NOD *p){if(p!=NULL)

{ parc_inord(p->st); printf("\t Nr=%d", p->inf); parc_inord(p->dr);}

}

/////////////////// Parcurgerea SDR arborelui by necvoid parc_postord (NOD *p){if(p!=NULL)

{ parc_postord(p->st); parc_postord(p->dr); printf("\t Nr=%d", p->inf);}

}

/////////////////// Stergerea arborelui by necvoid stergarbore(NOD *p){if (p!=NULL)

{stergarbore(p->st);stergarbore(p->dr);delete p;}

}

/////////////////// Afisare spatii by necvoid spatii(int n){int i;for(i=0;i<n;i++)putchar(' ');}



/////////////////// Afisare arbore by necvoid afisare(int n, int f, int k, int vb, int *vn){int i;spatii(4);if(n)

{for(i=1;i<n;i++)

{if(vn[i]) putchar(' ');else putchar('|');spatii(4);}

if(f) putchar('|');else putchar('|');for(i=0;i<4;i++) putchar('-');}

if(vb) printf("%d\n",k);else printf("...\n");}

/////////////////// Afisare pe nivele by necvoid afisare_nivel (NOD *p, int n=0){static int vn[50],f=1;if(p)

{afisare(n,f,p->inf,1,vn);if(p->st || p->dr)

{f=1;vn[n+1]=0;afisare_nivel(p->st,n+1);}

if(p->st || p->dr){f=0;vn[n+1]=1;afisare_nivel(p->dr,n+1);}

}else afisare(n,f,10,0,vn);}



///////////////// Stergerea unui nod cu doi descendenti by necint sterg(NOD *&pa)

{if(pa->st) return sterg(pa->st);else

{NOD *a=pa;int k=a->inf;pa=pa->dr;free(a);

return k;}

}///// Stergerea unui nod cu cel putin nu descendent vid by necvoid stergerenod(NOD *& p, int k){NOD *aux;if(p==NULL) printf("\n Nodul %d nu exista ",p->inf);else if(k<p->inf) stergerenod(p->st,k);

elseif(k>p->inf) stergerenod(p->dr,k);else

{aux=p;if(!aux->dr)

{p=aux->st;free(aux);}

elseif(!aux->st)

{p=aux->dr;free(aux);}

else p->inf=sterg(p->dr);}

}



/////////////////// Inserare nod by necvoid inserare(NOD *&p,int x){NOD *pnou;if (p==NULL)

{pnou=NEWpnou->inf=x;pnou->st=NULL;pnou->dr=NULL;p=pnou;}

elseif (p->inf>x)

inserare(p->st,x);else

if (p->inf<x)inserare(p->dr,x);

elseprintf("Elementul deja exista! \n");

}

/////////////////// Maximul dintre doua nr by necint max(int x,int y){if (x<y)

return y;else return x;}

/////////////////// Numararea nodurilor arborelui by necint nrnod(NOD *p){if(p!=NULL) return 1+nrnod(p->st)+nrnod(p->dr);else return 0;}

//////// Determinarea numarului de niveluri ale arborelui by necint inaltime(NOD *p){int stanga, dreapta;if(p!=NULL)

return 1+max(inaltime(p->st),inaltime(p->dr));else return 0;}



/////////////////// Programul principal by nec

void main(){NOD *rad;int nr,nivel,nrnou,nrsters;clrscr();

///// Crearea si afisarea RSD, SRD, SDR a unui arbore by necrad=creare();printf("--------------------------------------------------- \n");printf("Parcurgere preordine \n");parc_preord(rad);printf("\n");

printf("Parcurgere inordine \n");parc_inord(rad);printf("\n");

printf("Parcurgere postordine \n");parc_postord(rad);printf("\n");

printf("\n");printf("Afisarea pe niveluri: \n");afisare_nivel(rad);printf("\n");

///// Stergerea unui nod by necprintf("--------------------------------------------------- \n");printf("Nodul care se sterge = ");scanf("%d",&nrsters);stergerenod(rad,nrsters);





///// Inserarea unui nod by necprintf("--------------------------------------------------- \n");printf("Numarul de inserat este=");scanf("%d",&nrnou);inserare(rad,nrnou);



///// Nr. noduri & nr. niveluri by necnr=nrnod(rad);printf("Numarul de noduri este=%d \n",nr);nivel=inaltime(rad);printf("Inaltimea este=%d \n",nivel);

getchar();getchar();}


06[1]. arbori (rezumat studenti)

Documents