[C] alberi binari di ricerca

[thesalien]

infinitejustice, ho finito di guardare la tua funzione ma non è quello che stavo cercando. Quello che interessa a me sono gli alberi binari di ricerca, e purtroppo questi non lo sono


Che qualcuno mi aiuti!!

[infinitejustice]

Originariamente inviato da thesalien
infinitejustice, ho finito di guardare la tua funzione ma non è quello che stavo cercando. Quello che interessa a me sono gli alberi binari di ricerca, e purtroppo questi non lo sono

Guarda che quello nn solo è un albero binario di ricerca, ma è pure corretto... forse hai un'idea errata di cosa sia un ABR

Ogni nodo ha alla sua sinistra un nodo piu piccolo ed alla sua destra uno piu grande. Confronti l'elemento che cerchi con il padre (l'elemento di mezzo della sequenza) e se nn è quello che cerchi scendi o a sinistra (perche è minore) o a destra (maggiore) escludendo ad ogni passo metà sequenza...

[thesalien]

ebbene si, hai ragione... VVoVe:
Scusa, mi è sembrato un albero normale eprchè non vedevo nessuna funzione di ricerca modificata..

Questa è la mia ultima variazione: su gcc dovrebbe funzionare ma da me sul borland si bloccain esecuzione :master: e non so spiegarmi il motivo






#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char elemento[40];
typedef struct nodo *tree_pointer;
typedef struct nodo {
elemento key;
tree_pointer figlio_sinistro;
tree_pointer figlio_destro;
} albero;
tree_pointer radice = NULL;
void preorder(tree_pointer ptr);
void inorder(tree_pointer ptr);
void postorder(tree_pointer ptr);
tree_pointer ric_ric(tree_pointer, char*);
tree_pointer ric_iter(tree_pointer, char* );
void insert_nodo(tree_pointer *nodo,char* num);
tree_pointer ric_modificata(tree_pointer , char* );
int menu(void);






main(){
printf("\nEsercitazione numero 14");
char nome_chiave[20];
int scelta=100;
do{scelta=menu();
if(scelta==1){
printf("\nscrivi la chiave ");
scanf("%s",nome_chiave);
insert_nodo(&radice,nome_chiave);
}

if(scelta==2){ printf("\nElemento da ricercare: ");
scanf("%s",nome_chiave);
if(ric_ric(radice,nome_chiave))
printf("\nTrovato!");
else printf("\nNon è stato trovato!");
}


if(scelta==6)inorder(radice);

if(scelta==7)preorder(radice);

if(scelta==8)postorder(radice);

} while(scelta!=0);

fflush(stdin);
getchar();
}


int menu(void)
{
int buf;
printf("\n\nIndica l'operazione da eseguire:\n\n");
printf("inserisci elemento --> 1\n");
printf("ricerca elemento (ric.) --> 2\n");
printf("ricerca elemento (iter.) --> 3\n");
printf("cancella elemento per fusione --> 4\n");
printf("cancella elemento per copiatura --> 5\n");
printf("visita inorder --> 6\n");
printf("visita preorder --> 7\n");
printf("visita postorder --> 8\n");
printf("termina --> 0\n");
scanf("%d",&buf);
fflush;
return buf;
}



void insert_nodo(tree_pointer *nodo,char* num)
{
tree_pointer ptr, temp;
temp = ric_modificata(*nodo, num);
if(temp || !(*nodo)) {
ptr = (tree_pointer)malloc(sizeof(nodo));
if (ptr == NULL) {
printf("\nla memoria è piena");
exit(1);
}
strcpy(ptr->key,num);
ptr->figlio_sinistro = NULL;
ptr->figlio_destro = NULL;
if(*nodo) if(strcmp(num,temp->key)<0) temp->figlio_sinistro = ptr;
else temp->figlio_destro = ptr;
else *nodo = ptr;
}
}



tree_pointer ric_modificata(tree_pointer tree, char* chiave)
{
tree_pointer father;
/* fornisce un puntatore al nodo che contiene item
se tale nodo non esiste fornisce NULL */
father = tree;
while(tree) {
father = tree;
if (strcmp(chiave,tree->key)==0) return NULL;
if (strcmp(chiave,tree->key)<0) tree=tree->figlio_sinistro;
else tree=tree->figlio_destro;
}
return father;
}



/*algoritmo preorder*/
void preorder(tree_pointer ptr){
if(ptr){
printf("%4s",ptr->key);
preorder(ptr->figlio_sinistro);
preorder(ptr->figlio_destro);
}
}


/*algoritmo inorder*/
void inorder(tree_pointer ptr){
if(ptr){

inorder(ptr->figlio_sinistro);
printf("%4s",ptr->key);
inorder(ptr->figlio_destro);
}
}


/*algoritmo postorder*/
void postorder(tree_pointer ptr){
if(ptr){

postorder(ptr->figlio_sinistro);
postorder(ptr->figlio_destro);
printf("%4s",ptr->key);

}
}

tree_pointer ric_ric(tree_pointer radice, char* str)
{
if (!radice) return (NULL);
if (strcmp(str,radice->key) < 0)
return (ric_ric(radice->figlio_sinistro, str));
return (ric_ric(radice->figlio_destro, str));
}

tree_pointer ric_iter(tree_pointer tree, char* str)
{
while(tree)
{
if (strcmp(str,tree->key) == 0)
return(tree);
if (strcmp(str,tree->key) < 0)
return (ric_iter(tree->figlio_sinistro, str));
else tree = tree->figlio_destro;
}
return (NULL);
}

[thesalien]

Ho riportato in alto questo mio vecchio post perchè riprendendo in mano quest'algoritmo sono ritornato allo stesso punto....

Qualcuno ha qualche suggerimento nuovo?