ciao avrei da farvi una domanda circa le funzioni ricorsive su strutture dati quali ad esempio gli alberi binari
Ad esempio avendo un albero binario di ricerca( che come si sa ha già un proprio ordinamento: la radice dell'albero è minore dei figli del sottoalbero destro e maggiore di quelli del sottoalbero sinistro).
Se volessi scrivere una funzione che dato un intero n dato come argomento della funzione, mi dia l'ennesimo numero più grande, come avvengono le chiamate ricorsive nello stack?
se l'albero è ' |50|
|30| |60|
|55| |70|
dunque radice 50,sottoalbero sx 30, radice del sottoalbero dx 60 con figlio sx 55 e destro 70,
se n= 5 devo ottenere 30, se n= 1 restituisce la max etichetta cioè 70 , se n=2 la seconda più grande cioè 60 ecc.
da questo codice chi mi spiega le varie chiamate come vengono svolte dal compilatore?
codice:
struct Node{
int etichetta;
Node* left;
Node* right;
};
int funz( Node* tree, int& n){
if (tree){
int r= funz(tree->right, n);
n--;
if(n<0) return r;
if (n==0) return tree->etichetta;
return funz(tree->left, n); }
}
int n_max(Node*t, int n){
int i=n;
return n_max(t, i); }
all'atto della chiamata continueranno le chiamate ricorsive sempre sul sottoalbero dx cioè su 60 e 70 e appena è NULL si richiude la ricorsione ed inizia il controllo dell'if e la chiamata sul sottoalbero sx quindi appena si chiude quella su 70 , quando si è su 60 si genera la chiamata su 55 e si risale fino a 50 per generare poi la chiamata su 30???
grazie mille...