sub16_i.cpp

STRUCTURI DE DATE SI ALGORITMI

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

typedef int Atom;
struct Nod
	{
	Atom data;
	Nod *stg,*drt;
	};

void initarb(Nod*& N);
Nod* make_nod(Atom a);
void insert(Nod*& N,Atom a);
void afisarb(Nod* N);
int search(Nod *N,Atom a);  //NU MERGE
int echilibru(Nod* N);      //NU MERGE
int adinc(Nod *& N);        // ????


void main()
{
Nod *rad;
int n,x;
clrscr();
printf("\nIntroduceti valorile(intregi separate de spatii) :\n");
scanf("%d",&n);
rad=make_nod(n);
scanf("%d",&n);
while(n!=0)
	{
	insert(rad,n);
	scanf("%d",&n);
	}
printf("\nArborele :");
afisarb(rad);
printf("\nValoarea cautata :");
scanf("%d",&x);
if(search(rad,x)==1)
	printf("\nValoarea %d ESTE in arbore!",x);
else
	printf("\nValoarea %d NU ESTE in arbore!",x);
if(echilibru(rad)==1)
	printf("\nArborele ESTE echilibrat!");
else
	printf("\nArborele NU ESTE echilibrat!");
getch();
}


Nod* make_nod(Atom a)
{
Nod *N;
N=new Nod;
N->data=a;
N->stg=N->drt=0;
return(N);
}

void insert(Nod*& N,Atom a)
{
if(N==0)
	N=make_nod(a);
else
	if(a<N->data)
		insert(N->stg,a);
	else
		if(a>N->data)
			insert(N->drt,a);
}

void initarb(Nod*& N)
{
	N=0;
}

void afisarb(Nod* N)
{
if(N->data!=0)
	{
	if(N->stg!=0)
		afisarb(N->stg);
	printf(" %d",N->data);
	if(N->drt!=0)
		afisarb(N->drt);
	}
}

int search(Nod *N,Atom a)
{
if(N->data!=0)
	{
	if(a==N->data)
		return 1;
	else
		if(a<N->data)
			search(N->stg,a);
		else
			search(N->drt,a);
	}
return 0;
}


int max=1;
int t=1;

int adinc(Nod *& N)
{
while(N->data!=0)
	{
	if(N->stg!=0)
		{
		t++;
		adinc(N->stg);
		if(t>max)
			max=t;
		}
	else
		if(N->drt!=0)
			{
			t++;
			adinc(N->stg);
			if(t>max)
				max=t;
			}
       return(max);
	}
}

int echilibru(Nod* N)
{
if(N->data!=0)
	{
	if((adinc(N->stg)-adinc(N->drt))>1)
		return 0;
	else
		{
		echilibru(N->stg);
		echilibru(N->drt);
		}
	}
return 1;
}