steve4891 (Normal User)
Newbie
Messaggi: 12
Iscritto: 05/02/2008
|
ciao a tutti ancora.. ho fatto un programma che crea un albero funziona tutto però dopo un pò mi esce un errore di 0xC0000005 Access violation..
quacuno mi saprebbe dire perche?
GRAZIE!!!
qui sotto c'è codice:
#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);
struct tree_node *bst_min(struct tree_node *root);
void preorder(struct tree_node *root);
void inorder(struct tree_node *root);
void postorder(struct tree_node *root);
void visit(struct tree_node *root);
struct tree_node *successore(struct tree_node *root,int val);
//----------------------------MAIN-----------------------------
void main()
{
int val,ris,menu = 15,num;
struct tree_node *max,*min;
init_bst(&root);
for(;
{
printf("inserisci elemento: 1 \n");
printf("cerca elemento: 2 \n");
printf("cancella elemento: 3 \n");
printf("visualizza in postorder: 4 \n");
printf("visualizza in inorder: 5 \n");
printf("visualizza in preorder: 6 \n");
printf("visualizza massimo valore nell'albero: 7 \n");
printf("visualizza minimo valore nell'albero: 8 \n");
printf("trova successore di un numero: 9 \n");
printf("exit: 10 \n\n");
while((menu<=0) || (menu>10))
{
printf("scegli l'opzione da fare: ");
scanf("%d",&menu);
}
switch(menu)
{
case 1:
define_bst(&root); //inserisce i valori
break;
case 2:
printf("inserire valore da cercare: ");
scanf("%d",&val);
ris = bst_search(root,val);
if(ris == 1)
printf("TROVATO\n");
else
printf("NON TROVATO\n");
break;
case 3:
printf("inserire valore da cancellare: ");
scanf("%d",&val);
ris = bst_search(root,val);
if(ris == 1)
printf("TROVATO VADO A CANCELLARE\n");
else
{
printf("NON TROVATO immetti un altro numero da cancellare\n");
break;
}
bst_delete(root,val);
break;
case 4:
postorder(root);
break;
case 5:
inorder(root);
break;
case 6:
preorder(root);
break;
case 7:
max = bst_max(root);
printf("%d\n",max->key);
break;
case 8:
min = bst_min(root);
printf("%d\n",min->key);
break;
case 9:
printf("inserire valore di cui si vuole il successore: ");
scanf("%d",&val);
successore(root,val);
break;
case 10:
exit(1);
break;
}
menu = 15;
printf("\n\n\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;
}
//--------------------MINIMO IN BST-------------------------------
struct tree_node *bst_min(struct tree_node *root)
{
while(root->left)
root = root->left;
return root;
}
//------------------------PREORDER--------------------------------------
void preorder(struct tree_node *root)
{
if(root)
{
visit(root);
preorder(root->left);
preorder(root->right);
}
}
//---------------------------INORDER---------------------------------------
void inorder(struct tree_node *root)
{
if(root)
{
inorder(root->left);
visit(root);
inorder(root->right);
}
}
//------------------------------POSTORDER------------------------------------
void postorder(struct tree_node *root)
{
if(root)
{
postorder(root->left);
postorder(root->right);
visit(root);
}
}
//--------------------------------STAMPA ELEMENTO--------------------------------
void visit(struct tree_node *root)
{
printf("%d ",root->key);
}
//----------------TROVA SUCCSSORE--------------------------
struct tree_node *successore(struct tree_node *root,int val)
{
struct tree_node *root_x,*min,*prec,*root_y,*root_x1;
int minimo,var;
root_x = root;
if(!root)
{
printf("nessun valore già non presente");
exit(1); //non trovato
}
while(root_x->key != val) //trova elemento
{
if(root_x->key < val)
{
prec = root_x;
root_x = root_x->right;
}
else
{
prec = root_x;
root_x = root_x->left;
}
}
if(root_x->right != NULL)
{
min = bst_min(root_x->right);
minimo = min->key;
printf("il successore e: %d\n",minimo);
return (min);
}
root_y = prec;
while((root_y != NULL) && (root_x == root_y->right))
{
root_x = root_y;
root_x1 = root;
while(root_x1->key != root_x->key) //trova elemento padre
{
if(root_x1->key < root_x->key)
{
prec = root_x1;
root_x1 = root_x1->right;
}
else
{
prec = root_x1;
root_x1 = root_x1->left;
}
}
root_y = prec;
}
printf("il successore e: %d\n",root_y->key);
return(min);
}
//------------------------CANCELLA VALORE BST-------------------------
void bst_delete(struct tree_node *root,int val)
{
struct tree_node *root_copy,*prec,*succ,*root_sost;
int var;
root_copy = root;
if(!root)
{
printf("albero vuoto");
exit(1);
}
while(root_copy->key != val) //trova elemento da cancellare problemi se nn trova elemento
{
if(root_copy->key < val)
{
prec = root_copy;
root_copy = root_copy->right;
}
else
{
prec = root_copy;
root_copy = root_copy->left;
}
}
if((root_copy->left==NULL) && (root_copy->right==NULL) && (root_copy->key > prec->key)) //cancella se l'elemento non ha figli
{
prec->right = NULL;
free(root_copy);
return (0);
}
else if((root_copy->left==NULL) && (root_copy->right==NULL) && (root_copy->key < prec->key)) //cancella se l'elemento non ha figli
{
prec->left = NULL;
free(root_copy);
return (0);
}
else if((root_copy->left!=NULL) && (root_copy->right==NULL) && (root_copy->key > prec->key)) //cancella se l'elemento ha 1 figli
{
prec->right = root_copy->left;
root_copy->left = NULL;
free(root_copy);
return (0);
}
else if((root_copy->left==NULL) && (root_copy->right!=NULL) && (root_copy->key > prec->key)) //cancella se l'elemento ha 1 figli
{
prec->right = root_copy->right;
root_copy->right = NULL;
free(root_copy);
return (0);
}
else if((root_copy->left!=NULL) && (root_copy->right==NULL) && (root_copy->key < prec->key)) //cancella se l'elemento ha 1 figli
{
prec->right = root_copy->left;
root_copy->left = NULL;
free(root_copy);
return (0);
}
else if((root_copy->left==NULL) && (root_copy->right!=NULL) && (root_copy->key < prec->key)) //cancella se l'elemento ha 1 figli
{
prec->left = root_copy->right;
root_copy->right = NULL;
free(root_copy);
return (0);
}
if((root_copy->left!=NULL) && (root_copy->right!=NULL)) //cancella se l'elemento ha 2 figli
{
succ = successore(root_copy,root_copy->key); //trova succ da cancellare
var = succ->key;
bst_delete(root_copy,var); //cancella successore
root_copy->key = var; //sostituisco nella cella il valore del successore
}
}
|
