[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)
Ah questo non è un albero binario di ricerca (che vedrò nel prossimo capitolo insieme agli AVL) ma un banale albero binario che contiene in ogni nodo qualcosa che potrei voler ricercare.

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

[khelidan1980]

questo codice comunque non funzionerà,quando tu chiami la tua funzione sul nodo che contiene la chiave voluta,il tuo if ritorna k al ramo else della chiamata precedente,e poi?quando sei nell'else non hai nessun return

[Albi89]

questo codice comunque non funzionerà,quando tu chiami la tua funzione sul nodo che contiene la chiave voluta,il tuo if ritorna k al ramo else della chiamata precedente,e poi?quando sei nell'else non hai nessun return

Penso che dovrebbero essere due return nell'else... per il resto mi sembra ok =P

[DanieleC88]

Penso che dovrebbero essere due return nell'else... per il resto mi sembra ok =P
Non esattamente, in tal caso verrebbe restituito solo il risultato della visita sul sottoalbero sinistro: in pratica sta facendo una visita in preorder, dunque, se la chiave non è la radice, bisogna restituire il valore della visita sul sottoalbero sinistro quando questa non dà NULL, altrimenti restituire il valore della visita sul sottoalbero destro.

[...]
ELSE // Caso generale
risultato = CercaElemento(nodo figlio sinistro di r, chiave k)
if (!risultato)
{
return CercaElemento(nodo figlio destro di r, chiave k)
}
return risultato

[D4rkAng3l]

mmm e se lo facessi così:


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

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

return NULL;


Così per esempio se considero l'albero in figura:

http://www.siatec.net/andrea/uni/easd/albero.jpg

mettiamo che voglia sapere il puntatore del nodo con chiave E allora dovrebbe succedere che inizialmente ho:

1)Chiamo sul nodo A
CercaElemento(nodo A, chiave E):
risultato=CercaElemento(nodo B, chiave E):

2)Chiamo sul nodo B
CercaElemento(nodo B, chiave E):
risultato=CercaElemento(nodo D, chiave E):

3)Chiamo sul nodo D
CercaElemento(nodo D, chiave E):
risultato=CercaElemento(nodo F, chiave E)

4)Chiamo sul figlio sinistro di F che è NULL e ritorna null alla chiamata 3 a questo punto prova a chiamare sul figlio destro di F che è anch'esso null quindi torna indietro

5)Chiama sul figlio destro del nodo D che è null e restituisce null e torna indietro sul nodo B

6)2)Chiamo sul nodo B
CercaElemento(nodo B, chiave E):
risultato=CercaElemento(nodo E, chiave E): TROVATO e ritorna E al chiamnte che era la chiamata sul nodo B che a sua volta ritorna E al chiamante che era il nodo A

Ci pò stare così?

Ma secondo voi ho una sorta di handicap che tutte le volte che in qualche corso mi trovo a maneggiare ricorsioni sugli alberi mi impicco di brutto a capirle e non le manipolo mai con fluidità? :-(

Tnx
Andrea