[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]

Originariamente inviato da VICIUS

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]

Originariamente inviato da kappa85

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!!!

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]

Originariamente inviato da 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));

Non ti servono gli else, tanto fai return

[crick_pitomba]

Originariamente inviato da 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));
	 }

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