[C] Costruzione albero binario di ricerca mediante array

[Peppyno89]

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".



#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;

/* QUI IL PROGRAMMA MI CRASHA */

while(pt->valore <= corr->valore && corr->sinistro != "NULL")
{
corr = corr->sinistro; /* IPOTIZZO IL PROBLEMA STIA NEL COPIARE IL NODO FIGLIO AL 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! :help: :help: :help:

[dStefano93]

Ciao, così, con un'occhiata veloce ti direi che:

1) quando verifichi che una variabile non sia NULL, non devi usare le virgolette: var != NULL

2) è proprio necessario che radice sia void** nella dichiarazione di CreaAlbero? Perchè non può essere semplicemente un NODO* ?

Più tardi ci do un'occhiata un po' più approfondita così ti posso aiutare meglio (sempre che tu non abbia risolto nel frattempo :p )

[Peppyno89]

Ciao! e prima di tutto grazie per l'aiuto.

1) infatti ho notato anche io che in altri esercizi precedenti non ho usato le virgolette... xD

2) Potrei anche procedere come dici tu, passando alla funzione la radice come NODO *, purtroppo il problema non cambia xke con una printf ho verificato che i valori dell'array vengono assegnati ai nodi e funziona.
Il problema persiste nel passaggio:

corr = corr->sinistro

Al momento ho risolto il crash allocando memoria all'inizio del ciclo while principale per i nodi figli:

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

Ma con una printf dopo "corr = corr->sinistro" noto che non passa alcun valore ma solo l'indirizzo di memoria.

[dStefano93]

Allora, con malloc hai risolto il crash perchè prima assegnavi a corr una locazione di memoria non allocata, quindi un problema te lo sei tolto.

Sei sicuro che non ti fa nessun passaggio di valore? Magari stai stampando la cosa sbagliata ( printf("%d", corr) al posto di printf("%d", corr->valore) ).

[Peppyno89]

Sisi, è le printf sono scritte bene.
Adesso ho provato a modificare l'allocazione di memoria per i nodi figli cosi:

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

ad ogni passaggio non mi torna piu l'indirizzo di memoria ma il valore "0"

Forse dovrei provare a cambiare anke le altre allocazioni di memoria? (radice, corr e pt)

[dStefano93]

Ok, penso che tu abbia sbagliato quando assegni corr = * radice. Visto che quello che vuoi fare è far puntare il puntatore corr alla stessa cella del puntatore radice. Dovrebbe essere corr = radice;

Un'altro problema che ho notato è nell'uso del puntatore pt: ad ogni ciclo cambi il suo membro "valore", e ad ogni ciclo fai puntare corr->sinistro o corr->destro alla stessa locazione di memoria, perchè pt non cambia!

Questo si risolve allocando ad ogni ciclo memoria per pt.


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

//dentro crea albero
while(i < dim-1)
{
NODO *pt = malloc(sizeof(NODO));
pt->valore = Array[i+1];
corr = radice;

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) //Non penso sia necessario allocare memoriavisto che è stata già allocata per pt
{
corr->sinistro = pt;
}
else
{
corr->destro = pt;
}

i++;
}