[C]Funzione Alberi

[domenico88]

Salve a tutti!!

Ieri ho fatto all'uni la parte pratica di algoritmi e strutture dati...il compito consisteva nell' implementazione di un menù con i richiami alle funzioni standard sugli alberi(inseriemento, cancellazione, ricerca, stampa) e poi c'erano da fare due funzioni:

1-Stampa solo i nodi che hanno un campo chiave compreso in un dato intervallo.Implementazione ricorsiva
Questa l'ho fatta bene perchè mi stampava effettivamente solo i nodi in quell'intervallo...

2-Ricerca e cancellazione dei nodi che hanno il campo satellite(stringa) uguale ad un data stringa passata come parametro alla funzione.
Sempre ricorsiva senza usare la funzione standard delete...

Non dico di postarmi l'intero codice assolutamente, solo un idea che potrebbe farmi capire come procedere...Grazie a tutti !

[cionci]

C'è un problema, se trovi un nodo poi come si comporta la cancellazione con i figli ? Non c'è un comportamento standard.

[domenico88]

Originariamente inviato da cionci

C'è un problema, se trovi un nodo poi come si comporta la cancellazione con i figli ? Non c'è un comportamento standard.

Nn so, penso si dovrebbe comportare come la delete standare. I casi, nodo foglia, solo figlio destro, solo figlio sinistro e nodo con entrambi i figli, penso!
Non so se è quello che dicevi tu....forse se rimpiazza il nodo trovato col successivo, nel caso di solo figlio destro, con un campo satellite aguale??

[cionci]

Nel caso in cui ci siano due figli come si comporta la delete che avete fatto ?

[domenico88]

Ah scusami...dovevo specificare due cose...sono alberi binari di ricerca....quindi con al max due nodi e ordinati....

ti posto il codice della delete che abbiamo fatto

TNode *delete_standard(TTree tree,  TKey key)
{
  if(tree == NULL)
 return NULL;

 else if( tree->info.key > key)
 {
 tree->left = delete_standard(tree->left, key);
 return tree;
 }
 else if( tree->Info.key < key)
 tree->right = delete_standard(tree->right, key);
 return tree;
 }
else
{
  if( tree->left == NULL && tree->right == NULL)
  {
   free(tree);
   return NULL;
  } 
  
 if( tree->left == NULL)
 {
  TTree alias;
  alias = tree->right;
  free(tree);
  return alias;
  }

 if( tree->right == NULL)
 {
  TTree alias;
  alias = tree->left;
  free(tree);
  return alias;
  }

   TTree min_right;
   min_right = cerca_minimo(tree->right);
   tree->info = min_rght->info;
   tree->right =  delete_standard(tree->right, min_right->key);
   
  return tree;
}
 
  
}

[domenico88]

[cionci]

Gli eventuali valori uguali a quelli del nodo corrente si trovano a destra o a sinistra ?

[domenico88]

mmm....si potrebbero trovare sia a destra che a sinistra....

[domenico88]