Pointeri La Min Si Max Unui Abc

[+skyler_sdf]

Un arbore binar ale carui chei iau valori de un tip total ordonat sn. arbore binar de cautare(ABC) daca cheia fiecarui nod este mai mare decat orice cheie din fiul sau stang si mai mica decat orice cheie din fiul drept. Arborii binari sunt special conceputi pentru a imbunatati operatia de cautare a unei chei.

Prezint mai jos un algoritm de cautare ce returneaza un pointer catre minimul si maximul dintr-un ABC. Pentru parcurgerea arborelui in folosim SRD si SDR, prezentate la Metodele de parcurgere a arborilor.

OBS: minimul se gaseste in subarborele stang, iar maximul se gaseste in subarborele drept.

#include<stdio.h>

#include<conio.h>

//pointeri la minimul si maximul unui ABC

struct arb

{ int info;

arb*st,*dr; //st=stanga, dr=dreapta

};

//functia de inserare

void inserare(arb *&r,int k)

{ arb *pp;

if (!r)

{ pp=new arb; //aloca spatiu ptr noul nod

pp->info=k;

pp->st=NULL;

pp->dr=NULL;

r=pp;

}

else

if (r->info>k) inserare(r->st,k);

 else if (r->info<k) inserare(r->dr,k);

       else  printf("Elementul deja exista! \n");

}


void SRD(arb *pp)

{ if (pp)

{ SRD(pp->st);

printf(" %d ",pp->info);

SRD(pp->dr);

}

}


void SDR(arb *pp)

{ if (pp)

{ SDR(pp->st);

SDR(pp->dr);

printf(" %d ",pp->info);

}

}


int minim(arb *r)

{

    if(r->st!=NULL) return minim(r->st);

     else return r->info; //minimul se gaseste in sub. stang

}


int maxim(arb *r)

{

    if(r->dr) return maxim(r->dr); 

     else return r->info; //maximul se gaseste in sub. drept

}


int main()

{

arb *root=NULL,*p;

int min,max;

int nr;

printf("Radacina: "); //se citeste radacina

scanf("%d",&nr);

while (nr!=0) //daca este diferita de 0, se continua prin citirea nodurilor

{ 

inserare(root,nr);

printf("Valoare noua:");

scanf("%d",&nr); }

SRD(root);

min=minim(root);

printf("\n\nMinimul este: ");

printf("%d", min);

SDR(root);

max=maxim(root);

printf("\n\nMaximul este: ");

printf("%d", max);


getch();

return 0;

}