Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - albero BST
Forum - C/C++ - albero BST

Avatar
steve4891 (Normal User)
Newbie


Messaggi: 12
Iscritto: 05/02/2008

Segnala al moderatore
Postato alle 21:08
Mercoledì, 06/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
        
    }

}

PM Quote
Avatar
Babel (Normal User)
Newbie


Messaggi: 5
Iscritto: 07/02/2008

Segnala al moderatore
Postato alle 17:03
Giovedì, 07/02/2008
Non ho neanche guardato il codice eh... e non ho intenzione di farlo... ^^

Comunque direi sei un segmentation fault... ovvero quegli errori che nascono quando si fanno casini con i puntatori... prova ad isolare l'errore e a capire esattamente quando avviene, poi cerca l'errore da lì.


E... usa il tag codice... ^^

PM Quote