Alberi, inserimento nodo iterativo

[Mesh89]

Salve a tutti
devo sviluppare una funzione iterativa che inserisca un nodo in un albero di ricerca. Nessun problema con la versione ricorsiva, ne con la versione iterativa della ricerca, ma questa proprio non mi esce. Ecco l'abbozzo di codice:

void inserisci(nodo* root, int n)
{
while (true)
{
if (root == NULL)
{
root = new nodo;
root->info = n;
root->sx = NULL;
root->dx = NULL;
return;
}
else
if (root->info > n) root = root->sx;
else root = root->dx;
}
}

int main()
{
nodo* root=NULL;
int n;

cin >> n;
root = new nodo;
root->info = n;
root->sx = NULL;
root->dx = NULL;
for (int i=1; i<7; i++)
{
cin >> n;
inserisci(root,n);
}
}

ed ecco la versione ricorsiva (corretta) della funzione:

void inserisci(nodo* &root, int n)
{
if (root == NULL)
{
root = new nodo;
root->info = n;
root->sx = NULL;
root->dx = NULL;
}
else
if (root->info > n) inserisci(root->sx,n);
else inserisci(root->dx,n);
}

grazie a tutti in anticipo

[recoil]

ciao

il perché la versione iterativa non funziona è piuttosto semplice da intuire. quando root diventa pari a NULL fai la tua bella new e ti ritrovi con un nuovo oggetto che però non puoi collegare a niente, visto che nella precedente iterazione ti sei "mangiato" il riferimento al padre

puoi risolvere in più modi, uno ad esempio può essere quello di controllare se root->sx o root->dx (insomma dove ti stai per muovere) è pari a NULL e in quel caso creare il nuovo oggetto e connetterlo a sx o dx.

[Mesh89]

Allora devo avere qualche errore concettuale in testa O.o

Ma com'è che la versione ricorsiva funziona allora? Mi pare faccia la stessa cosa, scorre fino a trovare un NULL, e poi ci piazza un new...

[recoil]

la versione ricorsiva va grazie a quel & prima di root nei parametri della funzione.
tu prova a toglierlo e vedrai che smetterà di funzionare...

la versione iterativa può essere questa


void inserisci_iterativo(nodo *root, int n)
{
while (1)
{
if (root->info > n)
if (root->sx != NULL)
root = root->sx;
else
{
root->sx = new nodo;
(root->sx)->info = n;
(root->sx)->sx = NULL;
(root->sx)->dx = NULL;
break;
}
else
if (root->dx != NULL)
root = root->dx;
else
{
root->dx = new nodo;
(root->dx)->info = n;
(root->dx)->sx = NULL;
(root->dx)->dx = NULL;
break;
}
}
}


poi vedi tu come adattarla in base tuoi gusti :D
edit: una doverosa precisazione: la funzione è corretta nel tuo caso perché passi un puntatore che non è NULL, se provi a passare un NULL vai in segmentation fault

se vuoi provare l'ordinamento basta una visita inorder


void visita(nodo *root)
{
if (root != NULL)
{
visita(root->sx);
printf("%d ", root->info);
visita(root->dx);
}
}


che visualizzerà i numeri ordinati dal più piccolo al più grande

[Mesh89]

Grazie mille! Ora che ho il coidce davanti il problema del mio mi è chiaro...

Si, ho già sviluppato le 3 modalità di visita in order, post order e pre order... Sono estremamente semplici, ma non riesco a venire a capo di quella a livelli! Qualche consiglio?

[recoil]

quella a livelli sarebbe la visita in ampiezza?
per quella dovresti usare una coda, hai provato a vedere qualche implementazione in pseudocodice e adattarla in C?

[Mesh89]

Scusa, ero partito, così... é.è

La visita per livelli è quella per cui tu stampi il nodo padre, poi quelli del livello successivo, poi successivo ancora, e via così. Con la semplice ricorsione nn ci riesco, ora provo a seguire il tuo consiglio e provo con una coda