Structuri de Date și Algoritmi

Motivatia alegerii temei. Utilitatea aplicatiei

Am ales aceasta tema ca urmare a cerintelor avute la materia structuri de date si algoritmi, problema aleasa fiind baza si ajutand la fiabilizarea unor probleme mai complexe .

2.Structura aplicatiei: Schema logica main()

3.Detalii tehnice de implementare

#include<stdio.h>

#include<conio.h>

#include<malloc.h>

typedef struct nod

{

int nr;

nod *st, *dr;};

nod *prad=NULL,*a;

int v[50],x;

int sumacif(int i)

{

int s=0,c;

do {

c=i%10;

i=i/10;

s=s+c; } while(i!=0);

return s;

}

void inserare_nod(nod *&p, int k)

{

int n;

nod *q;

if (!p)

{

n=sizeof(nod);

q=(nod *)malloc(n);

q->nr=k;

q->st=q->dr=NULL; p=q; }

else

{

if(p->nr!=k)

if(sumacif(p->nr)>=sumacif(k))

inserare_nod(p->st,k);

else

inserare_nod(p->dr,k);

}

}

void preordine(nod *p)

{if (p)

{

printf(" %d ",p->nr);

preordine(p->st);

preordine(p->dr);

} }

void inordine(nod *p)

{

if (p)

{

inordine(p->st);

printf(" %d ",p->nr);

inordine(p->dr); } }

void postordine(nod *p)

{

if (p)

{

postordine(p->st);

postordine(p->dr);

printf(" %d ",p->nr);

} }

void cautare(int x,int y,nod *&a)

{ int i;

if(!a)

printf("nNodul nu exista! n");

else

if (x<a->nr)

cautare(x,y,a->st);

else

if (x>a->nr)

cautare(x,y,a->dr);

else

if(y !=0 )

a->nr=y;

else

{

a->nr=v[1];

for(i=2;i<=x;i++)

inserare_nod(a,v[i]);

}}

int noduri(nod *p)

{

if (!p)

return 0;

else

return (1+noduri(p->st)+noduri(p->dr));

}

int max(int x,int y)

{

if (x<y) return y;

else return x;

}

int nivel(nod *p)

{

if (!p)

return 0;

else

return (1+max(nivel(p->st),nivel(p->dr)));

}

int nr_frunze(nod *p)

{

if(!p)

return 0;

else

if((!p->st)&&(!p->dr))

return 1;

else

return (nr_frunze(p->st)+nr_frunze(p->dr));

}

int main()

{ int k,y;

printf("Dati radacina arborelui binar:");

scanf("%d",&k);

while(k!=0)

{

inserare_nod(prad,k);

printf("Dati un numar:");

scanf("%d",&k);

}

printf("nCe operatie doriti sa efectuati?n");

printf("a) Afisare arbore in preordine,inordine si postordine;n");

printf("b) Inlocuirea unui nod cu un nod nou;n");

printf("c) Inlocuirea unui nod cu un arbore construit dintr-un vector dat;n");

printf("d) Date despre arborele binar;n");

printf("Dati optiunea dumneavoastra: ");

switch(getche())

{

case 'a':

{

printf("nnPreordine:");

preordine(prad);

printf("nInordine:");

inordine(prad);

printf("nPostordine:");

postordine(prad);

break;

}

case 'b':

{

printf("nnDati nodul vechi:");

scanf("%d",&k);

printf("Dati nodul nou:");

scanf("%d",&y);

cautare(k,y,prad);

printf("Preordine:");

preordine(prad);

printf("nInordine:");

inordine(prad);

printf("nPostordine:");

postordine(prad);

break;

}

case 'c':

{

printf("nnDati nodul vechi:");

scanf("%d",&k);

printf("Numarul de elemente din vector:");

scanf("%d",&x);

for(y=1;y<=x;y++)

{printf("v[%d]= ",y);

scanf("%d",&v[y]);}

cautare(k,0,prad);

preordine(prad);

break;

}