Salve ragazzi,
sto studiando gli alberi, in particolari gli alberi binari di ricerca.
L'esercizio che sto provando a svolgere è il seguente:
Dato un albero binario di ricerca, si implementino (con la strategia più efficiente) le funzioni di inserimento e cancellazione in modo che in tale albero possano essere inseriti chiavi uguali. Quali sono le prestazioni asintotiche delle funzioni modificate?
Io ho iniziato a creare le due funzioni richieste, e per l'inserimento delle chiavi uguali, nella funzione "inserisci" al posto di > e < avevo messo >= e <= , ma secondo me è troppo banale e come soluzione non va bene...Per la cancellazione invece, non ho proprio idea ! Come potrei fare? Grazie in anticipo!
#include <stdio.h>
#include <stdlib.h>
struct nodo{
int info;
struct nodo *sinistro, *destro;
};
struct nodo *inserisci(struct nodo *radice, int e){
struct nodo *aux;
if(radice==NULL){
aux=malloc(sizeof(struct nodo));
if(aux){
aux->info=e;
aux->sinistro=aux->destro=NULL;
return aux;
}
else
printf("Memoria non allocata" );
}
else if(e<radice->info){
radice->sinistro = inserisci(radice->sinistro,e);
//printf("X\n");
}
else if(e>radice->info){
radice->destro = inserisci(radice->destro,e);
//printf("Y\n");
}
return radice;
}
void stampa(struct nodo *abr){
if(abr!=NULL){
stampa(abr->sinistro);
printf("%d \n",abr->info);
stampa(abr->destro);
}
}
int main(){
int n,i,el;
struct nodo *abr=NULL;
printf("Quanti nodi vuoi inserire\n");
scanf("%d",&n);
for(i=0;i<n;i++){
printf("Inserisci nodo: ");
scanf("%d",&el);
abr=inserisci(abr,el);
}
stampa(abr);
system("PAUSE");
return 0;
}