[Pseudo Codice]Ricerca di un elemento in un albero binario

[D4rkAng3l]

Ciao ragazzi,
ho qualche dubbio per l'esame di algoritmi...c'è un esercizio dove chiede di scrivere in pseudo codice (nessun linguaggio specifico quindi...ditemi solo se lalogica può essere corretta) una procedura ricorsiva che verfichi se esiste un nodo dell'albero che abbia un certo contenuto informativo (identficato da una chiave k)

io l'ho pensato così:

CercaElemento(nodo r, chiave k){

      IF(r == null) THEN return null // Caso base 1: gli stò passando un albero vuoto
      IF(chiave(r) == k) THEN return k // Caso base 2: ho trovato l'elemento che cerco

      ELSE    // Caso generale
          CercaElemento(nodo figlio sinistro di r, chiave k)
          CercaElemento(nodo figlio destro di r, chiave k)
}

Così facendo se gli passo un albero vuoto ritorna null al chiamante il che può succedere se l'albero di partenza è vuoto o se raggiunge una foglia: torna indietro restituendo null e se alla fine non ha trovato nulla la funzione dovrebbe restituire proprio null al chiamante di partenza.
Se invece trova l'elemento lo ritorna al chiamante altrimenti scende prima sul sottoalbero sinistro e poi sul sottoalbero destro effettaundo la ricerca.

Pensate che possa andare bene? la soluzione del professore è un po' diversa...ho sbagliato qjualcosa?

Grazie
Andrea

[Vincenzo1968]

Ciao Andrea,

il tuo codice va modificato leggermente:

CercaElemento(nodo r, chiave k){

      IF(r == null) THEN return null // Caso base 1: gli stò passando un albero vuoto
      IF(chiave(r) == k) THEN return k // Caso base 2: ho trovato l'elemento che cerco

      ELSE    // Caso generale
          IF (k < chiave(r)) CercaElemento(nodo figlio sinistro di r, chiave k)
          IF (k > chiave(r)) CercaElemento(nodo figlio destro di r, chiave k)
}

Per le proprietà degli alberi binari di ricerca, se k è minore della chiave del nodo r, bisogna cercare nel sottoalbero di sinistra. Se k è maggiore, cerchiamo nel sottoalbero destro.

[D4rkAng3l]

no non è un albero binario di ricerca (quello è il prossimo capitolo) ma un semplice albero binario dove gli oggetti vengono inseriti dentro "alla cazzum"...cioè devo inserire un nuovo oggetto alla mia collezione? Creo semplicemente un nodo e faccio una ricerca nodo per nodo senza considerare l'efficienza che poi viene ripresa con i BST e gli AVL nel prossimo capitolo.

[LexLex]

Ciao, una cosa che ho notato è che in:

IF(chiave(r) == k) THEN return k

Io invece di k che è il valore cercato, restituirei il (puntatore) all'elemento trovato,
oppure TRUE, dipende da come vuoi strutturare la tua funzione. Mi sembra più logico.

Poi a livello di ricorsione, io credo che nella maniera che hai programmato tu,
la prima funzione chiamante riceve un valore solamente se l'albero è vuoto
oppure il valore è nella radice. Mi spiego meglio..
(prendila con il beneficio del dubbio non sono mai stato un fenomeno nel ricorsivo):

Una funzione quando fa return, restituisce il valore alla funzione che l'ha chiamata..
adesso metti il caso che il valore cercato non sia nel primo elemento e quindi si va in:

CercaElemento(nodo figlio sinistro di r, chiave k)

Adesso, il valore è quello giusto, la funzione ritorna k, ma la funzione chiamante il k non lo riceve..

??? = CercaElemento(nodo figlio sinistro di r, chiave k).



Io non ho avuto modo di testarlo però ho pensato a questa soluzione:

CercaElemento(nodo r, chiave k) {
   IF (r == NULL) THEN return NULL
   IF (chiave(r) == k) THEN return r

   res = CercaElemento(figlio sx di r, k)
   IF (res != NULL) return res;
   res = CercaElemento(figlio dx di r, k)
   IF (res != NULL) return res;

   return NULL;

Forse ho scritto delle sciocchezze, se così fosse scusami

[Vincenzo1968]

Originariamente inviato da D4rkAng3l
no non è un albero binario di ricerca (quello è il prossimo capitolo)

Ti chiedo scusa, avevo letto male.