PDA

Visualizza la versione completa : [C++] funzioni ricorsive su strutture dati


gemis
11-07-2009, 18:16
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?


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...

gemis
15-07-2009, 20:05
nessuno che sappia rispondermi??
Ho un dubbio, non capisco se le chiamate sul sottoalbero sinistra e destra avvengano simmetricamente (come quando visitando l'albero scendessi per livelli dalla radice ed andassi al primo figlio a sx e al primo figlio a dx e così via fino in fondo) oppure una volta terminata la chiamata sul sottoalbero dx iniziano, richiudendo la ricorsione sul dx, le chiamate sul sottoalbero sx.

Help me!

Mi basterebbe anche un esempio numerico usando l'albero che ho postato per esempio ed elencando come vengono effettuate le chiamate e su quali nodi, grazie

Loading