salve a tutti, ho fatto un programma in c sugli alberi bst..ho fatto tutte le procedure essenziali ma mi manca quella che cancella un elemento e infine quella che cancella tutto l'albero!!
ho provato a implementarla ma tra puntatori ecc mi perdo:
c'è qualcuno che può darmi una mano?? ne sarei veramente grato!!!!!
quello che mi servirebbe sarebbe una procedura che mi permette di eliminare un elemento dall'albero mantenedo intatto quest'ultimo (ho letto che bisogna fare 3 casi a seconda dei figli che quell'elemento ha!) e poi una procedura che mi cancelli completamente l'albero liberando tutta la memoria.
metto di seguito il codice che ho fatto:
#include <stdio.h>
#include <stdlib.h>
//------------------STRUTTURA ALBERO-----------------------------
struct tree_node
{
int key;
struct tree_node *left;
struct tree_node *right;
};
struct tree_node *root; //puntatore alla struttura albero
//------------------DEFINIZIONE FUNZIONI-----------------------
void init_bst(struct tree_node **root);
void define_bst(struct tree_node **root);
struct tree_node *bst_insert(struct tree_node *root,struct tree_node *r,int val);
int bst_search(struct tree_node *root,int val);
void bst_delete(struct tree_node *root,int val);
struct tree_node *bst_max(struct tree_node *root);
//----------------------------MAIN-----------------------------
void main()
{
int val,ris;
init_bst(&root);
define_bst(&root);
printf("cosa vuoi cercare? ");
scanf("%d",&val);
bst_delete(root,val);
ris = bst_search(root,val);
if(ris == 1)
printf("TROVATO");
else
printf("NON TROVATO\n");
}
//-----------INIZIALIZZAZIONE DEL BST------------------
void init_bst(struct tree_node **root)
{
*root = NULL;
}
//-----------------DEFINIZIONE BST------------------------
void define_bst(struct tree_node **root) //dico quanti elementi e quali elementi prendere
{
int n,k,i;
printf("Numeri di elementi: ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Inserisci l'elemento N. %d: ",i);
scanf("%d",&k);
*root = bst_insert(*root,*root,k);
}
}
//--------------------INSERIMENTO ELEMENTO IN BTS-------------------------
struct tree_node *bst_insert(struct tree_node *root,struct tree_node *r,int val)
{
if(!r) //entra se è = a NULL
{
r = (struct tree_node *) malloc(sizeof(struct tree_node));
if(!r)
{
printf("memoria insufficiente!\n");
exit(1);
}
r->key = val;
r->left = NULL;
r->right = NULL;
if(!root) //entra solo all'inizio quando root punta a NULL cioèquando non è stato ancora creato il primo elemento
return r;
if(val < root->key)
root->left = r;
else
root->right = r;
return r;
}
if(val < r->key) //a parte la prima volta prima di inserire il numero nuovo guardo se inserlo a destra se è >
bst_insert(r,r->left,val); // o a sinistra se è <
else
bst_insert(r,r->right,val);
return root;
}
//------------------------RICERCA NEL BST-------------------------
int bst_search(struct tree_node *root,int val)
{
if(!root)
return 0; //non trovato
else if(root->key == val)
return 1; //trovato
else if(root->key < val)
bst_search(root->right,val);
else
bst_search(root->left,val);
//return -1;
}
//----------------------MASSIMO IN BST---------------------------------
struct tree_node *bst_max(struct tree_node *root)
{
while(root->right)
root = root->right;
return root;
}
//------------------------CANCELLA VALORE BST-------------------------
void bst_delete(struct tree_node *root,int val)
{
if(!root)
{
printf("valore già non presente");
exit(1);
}
}
vi ringrazio per l'attenzione e spero di avere una risposta, grazie per l'eventuale aiuto
se per caso qualcuno di voi riesce a implementarlo potrebbe mandarmi il codice a:
ketaki@fastwebnet.it GRAZIE!
