[C++] Albero binario di ricerca

[Gianni91]

Qualcuno potrebbe gentilmente aiutarmi a chiarire dei dubbi,sul comportamento di queste due funzioni.Sicuramente omettendo l'else il return finale viene eseguito sempre,ma non riesco a capire bene come si comporta la funzione,nel caso in cui entra nell'if precedente dove n<radice.In quel caso chiama la funzione con i nuovi paramatri e poi esegue l'ultimo return??

Node* findNode(InfoType n,Node* tree){
if(!tree) return 0;                                         //albero vuoto
if(n==tree->label)return tree;                         //n==radice
if(n<tree->label) return findNode(n,tree->left);  //n<radice
return findNode(n,tree->right);                       //n>radice
}

diverso da ..

Node* findNode(InfoType n,Node* tree){
if(!tree) return 0;                                         //albero vuoto
if(n==tree->label)return tree;                         //n==radice
if(n<tree->label) {return findNode(n,tree->left);}  //n<radice
else{
         return findNode(n,tree->right); }                      //n>radice
}

grazie!!

[alka]

Il linguaggio va indicato anche nel titolo, come da Regolamento.

Qui l'ho aggiunto io, tienilo a mente per il futuro.

[Gianni91]

grazie starò attento...

[Celebron]

Originariamente inviato da Gianni91
Qualcuno potrebbe gentilmente aiutarmi a chiarire dei dubbi,sul comportamento di queste due funzioni.Sicuramente omettendo l'else il return finale viene eseguito sempre,ma non riesco a capire bene come si comporta la funzione,nel caso in cui entra nell'if precedente dove n<radice.In quel caso chiama la funzione con i nuovi paramatri e poi esegue l'ultimo return??

Node* findNode(InfoType n,Node* tree){
if(!tree) return 0;                                         //albero vuoto
if(n==tree->label)return tree;                         //n==radice
if(n<tree->label) return findNode(n,tree->left);  //n<radice
return findNode(n,tree->right);                       //n>radice
}

diverso da ..

Node* findNode(InfoType n,Node* tree){
if(!tree) return 0;                                         //albero vuoto
if(n==tree->label)return tree;                         //n==radice
if(n<tree->label) {return findNode(n,tree->left);}  //n<radice
else{
         return findNode(n,tree->right); }                      //n>radice
}

grazie!!

aghf, perché chiamare un nodo "tree"? al massimo poteva chiamarlo subtree, anche se vista la funzione poteva usare root o cose del genere... secondo me è fuorviante, ma vabbé è un problema personale
//fine considerazioni personali

ad ogni modo tra i due codici che hai linkato non cambia niente, le grafe non servono e nemmeno l'else

il

return funzione();

viene considerata un unica istruzione, nella quale prima viene chiamata la funzione "funzione()", viene eseguita e quindi ne viene preso il valore restituito e quindi ha luogo il return.

perciò va letta come:
se n è uguale al valore nella radice attuale -> ritorna n; (il che per come è fatta porrà fine a tutta la funzione ricorsiva ritornando il valore sino al livello "iniziale")
se n è minore del valore nella radice attuale -> ricorri in figlio di sinistra e ritorna il suo valore a fine chiamata;
(in tutti gli altri casi) ricorri sul figlio di destra e ritorna il suo valore a fine chiamata;

[Gianni91]

Grazie per l'aiuto ,ma alla fine ci sono arrivato da solo..