Creazione albero binario di ricerca mediante array

**Peppyno** · 29-01-2015, 13:12

Salve a tutti.
Sto avendo un problema con questo esercizio universitario.
Dato in input un tot di elementi che si vanno ad inserire in un array, attraverso l'algoritmo di ricerca binaria dovrei costruirmi questo "BST". Ma il programma mi crasha gia al primo while della funzione "Creaalbero".

codice:

#include <stdio.h>
#include <stdlib.h>

struct nodo{
    int valore;
    struct nodo *sinistro;
    struct nodo *destro;
};

typedef struct nodo NODO;

void CreaAlbero(int Array[], int dim, void **);
void PREORDER(void **);
void INORDER(void **);
void POSTORDER(void **);

void main()
{
    int dim;

    printf("Inserire la dimensione dell'array (numero elementi albero binario):\n");
    scanf("%d",&dim);

    int Array[dim];

    int i;
    for(i=0; i<dim; i++)
    {
        printf("Inserire un valore numerico: ");
        scanf("%d",&Array[i]);
    }

    NODO *radice;
    radice = malloc(sizeof(NODO));
    radice->valore = Array[0];

    system("cls");
    printf("Creazione albero...\n\n");

    CreaAlbero(Array, dim, (void **)&radice);

    INIZIO:
    printf("\n");
    int selezione;

    printf("Digitare:\n");
    printf("0 per la visita preorder\n");
    printf("1 per la visita inorder\n");
    printf("2 per la visita postorder\n");

    scanf("%d",&selezione);

    switch(selezione)
    {

        case 0:
        {
            printf("\nVisita dell'albero in ordine Preoder\n");
            PREORDER((void **)&radice);
        }
        break;

        case 1:
        {
            printf("\nVisita dell'albero in ordine Inorder\n");
            INORDER(radice);
        }
        break;

        case 2:
        {
            printf("\nVisita dell'albero in ordine Postorder\n");
            POSTORDER(radice);
        }
        break;
    }

    system("pause");
    system("cls");
    goto INIZIO;

    _getch();
}


void CreaAlbero(int Array[], int dim, void **radice)
{
    int i = 0;

    NODO *pt;
    pt = malloc(sizeof(NODO));

    NODO *corr;
    corr = malloc(sizeof(NODO));

    while(i < dim-1)
    {
        pt->valore = Array[i+1];
        corr = *radice;
        
        /* IL PROGRAMMA MI CRASHA QUI!!! */    

        while(pt->valore <= corr->valore   &&   corr->sinistro != "NULL")
        {
            corr = corr->sinistro;   /* IPOTIZZO CHE IL PROBLEMA STIA NEL COPIARE IL FIGLO      ALL'INTERNO DEL NODO PADRE */
        }

        while(pt->valore >= corr->valore   &&   corr->destro != "NULL")
        {
            corr = corr->destro;
        }

        if(pt->valore <= corr->valore)
        {
            corr->sinistro = pt;
        }
        else
        {
            corr->destro = pt;
        }

        i++;
    }
}


void PREORDER(void **radice)
{
    NODO *nodo;
    nodo = *radice;

    if(nodo != "NULL")
    {
        printf("%d\n", nodo->valore);
        PREORDER( nodo->sinistro );
        PREORDER( nodo->destro );
    }
}


void INORDER(void **radice)
{
    NODO *nodo;
    nodo = *radice;

    if(nodo != "NULL")
    {
        INORDER( nodo->sinistro );
        printf("%d\n", nodo->valore);
        INORDER( nodo->destro );
    }
}


void POSTORDER(void **radice)
{
    NODO *nodo;
    nodo = *radice;

    if(nodo != "NULL")
    {
        POSTORDER( nodo->sinistro );
        POSTORDER( nodo->destro );
        printf("%d\n", nodo->valore);
    }
}

Ho fatto gia altri esercizi con liste linkate e con alberi generici e binari ma questi passaggi mi creano ancora problemi.
Ringrazio chiunque possa darmi una dritta!

**Krahos** · 29-01-2015, 13:58

Non ne sono sicuro ma l'errore potrebbe stare nel passare radice come void ** quando potresti passarlo come NODO *.
Poi un consiglio che posso darti (anche se magari lo sai già) è quello di controllare dopo ogni malloc se il puntatore che hai cercato di allocare resta nullo. La malloc potrebbe non andare a buon fine e non appena cerchi di utilizzare quel puntatore il programma va in crash.
Quindi per esempio

codice:

radice = malloc (sizeof (*radice)); //o sizeof (NODO) se preferisci
if (radice == NULL) {
  return ERROR; //gestisci l'errore come vuoi tu
}

Poi cerca di non utilizzare goto e simili (break e continue) a meno che non sia strettamente necessario se non vuoi essere bacchettato dai tuoi professori.

Ho visto che le tue dichiarazioni di variabili stanno in mezzo al codice. Questo va bene se stai utilizzando il C99 ma è un errore se stai utilizzando l'ANSI C.

**Peppyno** · 29-01-2015, 15:08

Per il passaggio di radice alla funzione, posso provare come dici tu ma ho gia costatato che il valore radice viene passato correttamente nella funzione e anche alla cariabile corr con delle printf subito dopo i passaggi.
Il crash l'ho risolto inserendo le allocazioni di memoria dei nodi figli.

corr->sinistro = calloc(1, sizeof (struct nodo));
corr->destro = calloc(1, sizeof (struct nodo));

Ho modificato anke tutte le altre allocazioni di memoria da malloc a calloc.
Con malloc ad ogni ciclo while mi tornava la copia dell'indirizzo di memoria, adesso mi torna il valore 0 sempre.

Questo è il codice aggiornato

codice:

#include <stdio.h>
#include <stdlib.h>

struct nodo{
    int valore;
    struct nodo *sinistro;
    struct nodo *destro;
};

typedef struct nodo NODO;

void CreaAlbero(int Array[], int dim, void **);
void PREORDER(void **);
void INORDER(void **);
void POSTORDER(void **);

void main()
{
    int dim;

    printf("Inserire la dimensione dell'array (numero elementi albero binario):\n");
    scanf("%d",&dim);

    int Array[dim];

    int i;
    for(i=0; i<dim; i++)
    {
        printf("Inserire un valore numerico: ");
        scanf("%d",&Array[i]);
    }

    NODO *radice;
    radice = calloc(1, sizeof (struct nodo));
    radice->valore = Array[0];

    system("cls");
    printf("Creazione albero...\n\n");

    CreaAlbero(Array, dim, (void **)&radice);

    INIZIO:
    printf("\n");
    int selezione;

    printf("Digitare:\n");
    printf("0 per la visita preorder\n");
    printf("1 per la visita inorder\n");
    printf("2 per la visita postorder\n");

    scanf("%d",&selezione);

    switch(selezione)
    {

        case 0:
        {
            printf("\nVisita dell'albero in ordine Preoder\n");
            PREORDER((void **)&radice);
        }
        break;

        case 1:
        {
            printf("\nVisita dell'albero in ordine Inorder\n");
            INORDER(radice);
        }
        break;

        case 2:
        {
            printf("\nVisita dell'albero in ordine Postorder\n");
            POSTORDER(radice);
        }
        break;
    }

    system("pause");
    system("cls");
    goto INIZIO;

    _getch();
}


void CreaAlbero(int Array[], int dim, void **radice)
{
    int i = 0;

    printf("\n");
    NODO *pt;
    pt = calloc(1, sizeof (struct nodo));

    while(i < dim-1)
    {
        pt->valore = Array[i+1];

        NODO *corr;
        corr = calloc(1, sizeof (struct nodo));
        corr = *radice;

        corr->sinistro = calloc(1, sizeof (struct nodo));
        corr->destro = calloc(1, sizeof (struct nodo));

        while(pt->valore <= corr->valore && corr->sinistro != NULL)
        {
            corr = corr->sinistro;
        }

        while(pt->valore >= corr->valore && corr->destro != NULL)
        {
            corr = corr->destro;
        }

        if(pt->valore >= corr->valore)
        {
            corr->sinistro = pt;
        }
        else
        {
            corr->destro = pt;
        }

        i++;
        printf("\n");
    }
}


void PREORDER(void **radice)
{
    NODO *nodo;
    nodo = *radice;

    if(nodo != NULL)
    {
        printf("%d\n", nodo->valore);
        PREORDER( nodo->sinistro );
        PREORDER( nodo->destro );
    }
}


void INORDER(void **radice)
{
    NODO *nodo;
    nodo = *radice;

    if(nodo != NULL)
    {
        INORDER( nodo->sinistro );
        printf("%d\n", nodo->valore);
        INORDER( nodo->destro );
    }
}


void POSTORDER(void **radice)
{
    NODO *nodo;
    nodo = *radice;

    if(nodo != NULL)
    {
        POSTORDER( nodo->sinistro );
        POSTORDER( nodo->destro );
        printf("%d\n", nodo->valore);
    }
}

**Samuele_70** · 29-01-2015, 19:28

Qualche consiglio.
non usare

codice:

int Array[dim];

è una estensione del C che praticamente compila solo con gcc, questa soluzione non ti da modo di sapere se l'allocazione implicita è andata a buon fine, è da evitare assolutamente imo.
Usa un puntatore a int (inizializzato a NULL !) e poi alloca gli elementi necessari con la malloc()
Il semplice passaggio da malloc() a calloc() non può essere la soluzione ovviamente, il problema è altrove.

Inizializzare sempre le varibili quando le dichiari è una buona pratica per eliminare molti problemi.
Soprattutto la varibile radice andrebbe inizializzata a NULL.
Come ti è già stato consigliato sarebbe bene anche spostare tutte le dichiarazioni delle varialbili all'inizio di ogni blocco di istruzioni.

Nella funzione CreaAlbero()

codice:

        corr = calloc(1, sizeof (struct nodo));
        corr = *radice;

In queste righe di codice c'è qualcosa che non va, cosa volevi ottenere ?

Quel goto e quelle due chiamate a system() consecutive... non si possono proprio vedere ...

**Peppyno** · 29-01-2015, 20:50

Il problema credo ke sia sempre qui:

while(pt->valore <= corr->valore && corr->sinistro != NULL)
{
corr = corr->sinistro;
}

while(pt->valore >= corr->valore && corr->destro != NULL)
{
corr = corr->destro;
}

Per inserire ad esempio i valori 5,6,7 fino al 6 il programma non mi da problemi, inserendo 5 come radice e 6 come
nodofiglio destro di radice. Il problema è quando inserisce il valore 7, che dovrebbe posizionarsi come figlio
destro del figlio destro di radice ma il programma non passa corr->destro in corr...

Questa è la versione aggiornata con alcune modifiche consigliate da voi...

codice:

#include <stdio.h>
#include <stdlib.h>

struct nodo{
    int valore;
    struct nodo *sinistro;
    struct nodo *destro;
};

typedef struct nodo NODO;

void CreaAlbero(int Array[], int dim, void **);
void PREORDER(void **);
void INORDER(void **);
void POSTORDER(void **);

void main()
{
    int dim;

    printf("Inserire la dimensione dell'array (numero elementi albero binario):\n");
    scanf("%d",&dim);

    int Array[dim];

    int i;
    for(i=0; i<dim; i++)
    {
        printf("Inserire un valore numerico: ");
        scanf("%d",&Array[i]);
    }

    NODO *radice;
    radice = malloc(sizeof(NODO));
    radice->valore = Array[0];

    system("cls");
    printf("Creazione albero...\n\n");

    CreaAlbero(Array, dim, (void **)&radice);

    INIZIO:
    printf("\n");
    int selezione;

    printf("Digitare:\n");
    printf("0 per la visita preorder\n");
    printf("1 per la visita inorder\n");
    printf("2 per la visita postorder\n");

    scanf("%d",&selezione);

    switch(selezione)
    {

        case 0:
        {
            printf("\nVisita dell'albero in ordine Preoder\n");
            PREORDER((void **)&radice);
        }
        break;

        case 1:
        {
            printf("\nVisita dell'albero in ordine Inorder\n");
            INORDER(radice);
        }
        break;

        case 2:
        {
            printf("\nVisita dell'albero in ordine Postorder\n");
            POSTORDER(radice);
        }
        break;
    }

    system("pause");
    system("cls");
    goto INIZIO;

    _getch();
}


void CreaAlbero(int Array[], int dim, void **radice)
{
    int i = 0;

    NODO *pt;
    pt = malloc(sizeof(NODO));

    NODO *corr;
    corr = malloc(sizeof(NODO));
    corr = *radice;
    corr->sinistro = malloc(sizeof(NODO));
    corr->sinistro = NULL;
    corr->destro = malloc(sizeof(NODO));
    corr->destro = NULL;

    while(i < dim-1)
    {
        pt->valore = Array[i+1];

        while(pt->valore <= corr->valore && corr->sinistro != NULL)
        {
            corr = corr->sinistro;
        }

        while(pt->valore >= corr->valore && corr->destro != NULL)
        {
            corr = corr->destro;
        }

        if(pt->valore <= corr->valore)
        {
            corr->sinistro = pt;
        }
        else
        {
            corr->destro = pt;
        }

        i++;
    }
}


void PREORDER(void **radice)
{
    NODO *nodo;
    nodo = *radice;

    if(nodo != NULL)
    {
        printf("%d\n", nodo->valore);
        PREORDER( nodo->sinistro );
        PREORDER( nodo->destro );
    }
}


void INORDER(void **radice)
{
    NODO *nodo;
    nodo = *radice;

    if(nodo != NULL)
    {
        INORDER( nodo->sinistro );
        printf("%d\n", nodo->valore);
        INORDER( nodo->destro );
    }
}


void POSTORDER(void **radice)
{
    NODO *nodo;
    nodo = *radice;

    if(nodo != NULL)
    {
        POSTORDER( nodo->sinistro );
        POSTORDER( nodo->destro );
        printf("%d\n", nodo->valore);
    }
}

**Peppyno** · 05-02-2015, 18:19

Ragazzi, scusate se non ho risposto più... ringrazio tutti per l'aiuto, alla fine sono riuscito a risolvere. Ad ogni nodo che creavo, non aggiungevo il rispettivo nodo sx e dx

Discussione: Creazione albero binario di ricerca mediante array

Strumenti discussione

Ricerca discussione

Visualizza

Creazione albero binario di ricerca mediante array

Permessi di invio