[C] Ricerca in albero binario

[kappa85]

Ciao, ho un albero binario ordinato secondo una chiave intera, io devo fare una ricerca non secondo quella chiave, ma secondo un altro campo della struttura che compone ogni nodo, la quale è una stringa. Ho provato facendo una visita ricorsiva inorder, ma non riesco a far terminare la ricorsione, come faccio? Help!

[VICIUS]

Probabilmente è sbagliata la condinazione di terminazione della funzione ricorsiva. Poter vedere il codice sorgente della funzione aiuterebbe non poco. :)

ciao ;)

[kappa85]

Probabilmente è sbagliata la condinazione di terminazione della funzione ricorsiva. Poter vedere il codice sorgente della funzione aiuterebbe non poco. :)

ciao ;)

Ti ringrazio, il codice è questo:


rbnode *cerca (rbtree *tree, rbnode *node, key k)
{

if(node!=tree->nil)
{
cerca(tree,node->left,k);

if(strcmp(node->v,k)==0)

return node;

cerca(tree,node->right,k);

}
}

Il nil sarebbe il nodo fittizio al quale puntano tutte le foglie dell'albero.

[Ufo13]

ma tu confronti la stringa con la key... hai detto che la key è intera... cosa è node->v? v=valore? Usa nomi di variabili più chiari!!

[crick_pitomba]

Ti ringrazio, il codice è questo:


rbnode *cerca (rbtree *tree, rbnode *node, key k)
{

if(node!=tree->nil)
{
cerca(tree,node->left,k);

if(strcmp(node->v,k)==0)

return node;

cerca(tree,node->right,k);

}
}

Il nil sarebbe il nodo fittizio al quale puntano tutte le foglie dell'albero.


dando un'occhiata veloce al codice, mi sembra un po' incongruente: hai scritto il codice per una visita in order ma hai dimenticato di far fare qualcosa ai valori di ritorno della funzione.

la funzione effettivamente visita l'albero in order ma lo visita solo!!! :mc:

Il problema è questo: se trova la chiave restituisce il nodo alla funzione che l'ha chiamato, ma questa non se ne fa niente...quando trovi qualcosa devi far restituire il nodo corrente alla funzione chiamante che deve saperlo gestire.

Tra l'altro la tua funzione restituisce un valore solo nel caso in cui trova qualcosa... negli altri casi cosa restituisce???? un compilatore java non ti avrebbe fatto mai compilare il tuo codice.

inoltre se il valore cercato è nel nodo corrente è inutile che ti visiti tutto l'albero sinistro... è fatica sprecata

(scrivo pseudocodice perché in c sono un po' arrigginito)

se non sei in una foglia
{
controlla il valore del nodo corrente
se è il valore cercato restituisci il nodo corrente

nodotrovato=visita foglia sinistra
se nodotrovato è non nullo restituisci questo valore

nodotrovato= visita foglia destra
se nodotrovato è non nullo restituisci questo valore

restituisci il nodo nullo
}

[kappa85]

Aspetta, facciamo chiarezza: quello che devo fare io è questo, cercare se un particolare nodo appartiene all'albero, come nell'esempio sotto, SOLO CHE io non devo restituire TRUE o FALSE ma devo restituire il NODO per poi lavorarci: rbnode *cerca(rbtree *tree, rbnode *node, key k){
//caso base (albero vuoto)
if (node==tree->nil) return NULL;
//caso ricorsivo (albero non vuoto)
else
if (strcmp(node->v,k)==0)
return node;
else
if (cerca(tree,node->left,k))
return node;
else
return (cerca(tree,node->right,k));
}

[kappa85]

Nel frattempo ho trovato una soluzione, non molto elegante però va :)

eseguo la procedura di cui sopra che restituisce TRUE o FALSE per poter effettuare il test dal chiamante, e nel momento in cui trovo la chiave salvo in una variabile puntatore globale il puntatore al nodo trovato... può andare? C'è qualche controindicazione? C'è qualche soluzione più elegante?

//caso base (albero vuoto)
if (node==tree->nil) return 0;
//caso ricorsivo (albero non vuoto)
else
if (strcmp(node->v,k)==0){
app=node; // app è il puntatore globale
return 1;
else
if (cerca(tree,node->left,k))
return 1;
else
return (cerca(tree,node->right,k));

[Ufo13]

Nel frattempo ho trovato una soluzione, non molto elegante però va :)

eseguo la procedura di cui sopra che restituisce TRUE o FALSE per poter effettuare il test dal chiamante, e nel momento in cui trovo la chiave salvo in una variabile puntatore globale il puntatore al nodo trovato... può andare? C'è qualche controindicazione? C'è qualche soluzione più elegante?

//caso base (albero vuoto)
if (node==tree->nil) return 0;
//caso ricorsivo (albero non vuoto)
else
if (strcmp(node->v,k)==0){
app=node; // app è il puntatore globale
return 1;
else
if (cerca(tree,node->left,k))
return 1;
else
return (cerca(tree,node->right,k));


Non ti servono gli else, tanto fai return :)

[crick_pitomba]

Aspetta, facciamo chiarezza: quello che devo fare io è questo, cercare se un particolare nodo appartiene all'albero, come nell'esempio sotto, SOLO CHE io non devo restituire TRUE o FALSE ma devo restituire il NODO per poi lavorarci: rbnode *cerca(rbtree *tree, rbnode *node, key k){
//caso base (albero vuoto)
if (node==tree->nil) return NULL;
//caso ricorsivo (albero non vuoto)
else
if (strcmp(node->v,k)==0)
return node;
else
if (cerca(tree,node->left,k))
return node;
else
return (cerca(tree,node->right,k));
}

Se NON devi restituire TRUE o FALSE ma solo il nodo,
la soluzione corretta è proprio questa che, per inciso, è la traduzione in c dello pseudocodice che avevo postao (infatti come ha argutamente osservato ufo13 gli else sono ridondanti visto che fai il return).