26/06/2019, 16:30
struct btree{
float value;
struct btree * left_ptr;
struct btree * right_ptr;
}
void visit_r(struct btree * ptr){
if (ptr != NULL) { /*if the pointer points to something*/
printf("I search the left son... ");
visit_r(ptr->left_ptr);
printf("\n I print the value: %f \n", ptr->value);
printf("I search the right son... ");
visit_r(ptr->right_ptr);
} printf("Let's go back... ");
}
26/06/2019, 18:00
JustBreathe ha scritto:Ciao a tutti!
Non riesco a comprendere la definizione di una funzione.
Ecco l'esercizio:
Dato un albero di ricerca binario,
Scrivere una funzione ricorsiva che effettui una visita simmetrica e che stampi il valore di ogni nodo dell'albero.
Due note:
La visita simmetrica è una visita ordinata in tal modo:
1) figli sinistri;
2) radice;
3) figli destri.
Ogni nodo dell'albero è siffatto:
- Codice:
struct btree{
float value;
struct btree * left_ptr;
struct btree * right_ptr;
}
Qui sotto scrivo la definizione della funzione che non riesco a capire
- Codice:
void visit_r(struct btree * ptr){
/*function which takes in input a pointer to struct btree*/
- Codice:
if (ptr != NULL) { /*if the pointer points to something*/
printf("I search the left son... ");
visit_r(ptr->left_ptr);
/*I can't understand what happens here. I re-use my
function with a new input, but I will give a new input
until pointer==NULL.
When pointer will be == NULL, I will not
enter in the "if cycle", and I will not be able
to print the value of my nodes!*/
- Codice:
printf("\n I print the value: %f \n", ptr->value);
printf("I search the right son... ");
visit_r(ptr->right_ptr);
} printf("Let's go back... ");
}
/*I can't understand neither how it can go back,
how it can 'climb' the tree*/
Essendo una funzione ricorsiva, quando si raggiunge la riga dove vi è scritto visit_r(ptr->left_ptr); , si ritorna alla prima riga effettuando la visita con un nuovo input.
Tuttavia ancora non riesco a capire come faccia a funzionare.
Tale procedimento verrà re-iterato finchè 'ptr->left_ptr' non sarà uguale a NULL,
ma quando 'ptr->left_ptr' sarà ' == NULL', non potrò entrare nel ciclo "if(...)" e non sarò in grado di stampare i miei valori!
Inoltre non capisco come, a fine ciclo, si possa "risalire" nell'albero..
P.s. il codice è scritto da una professoressa universitaria, i commenti sono scritti da me.
Grazie a tutti!
printf("Let's go back... ");
visit_r(ptr->left_ptr);
printf("\n I print the value: %f \n", ptr->value);
28/06/2019, 16:33
giovx24 ha scritto:
ciao
quando arrivi al nodo in basso a sinistra ovviamente come dici tu ptr->left_ptr sarà uguale a NULL a questo punto viene eseguito
- Codice:
printf("Let's go back... ");
dopo la funziona ritorna e ti ritrovi nella funzione precedente
l'ultima istruzione che la funzione precedente aveva eseguito era
- Codice:
visit_r(ptr->left_ptr);
pertanto adesso verrà eseguita
- Codice:
printf("\n I print the value: %f \n", ptr->value);
28/06/2019, 18:58
29/06/2019, 19:59
giovx24 ha scritto:che casino
non mi convince molto, magari prova a spiegarmi
void visit_r(struct btree * ptr){ /*mia funzione*/
if (ptr != NULL) { /*if the pointer points to something*/
printf("I search the left son... ");
visit_r(ptr->left_ptr);
printf("\n I print the value: %f \n", ptr->value);
printf("I search the right son... ");
visit_r(ptr->right_ptr);
} printf("Let's go back... ");
}
29/06/2019, 20:26
29/06/2019, 20:40
giovx24 ha scritto:è tutto corretto,
devi capire che sono tante funzioni che si chiamano una dentro l'altra non appena una termina si ritorna a quella precedente.
in questo caso ad esempio quando viene stampato il valore 6 ci sono 4 funzioni attive
dopo se ne crea una quinta per controllare se il nodo 6 ha un figlio a destra
il nodo 6 non ha figli a destra e quindi la funzione termina e ci sono di nuovo 4 funzioni attive
adesso la quarta funzione che sarebbe quella relativa al nodo 6 termina e ti ritrovi nella terza funzione relativa al nodo 16
quindi viene stampato il numero 16
e si crea nuovamente una quarta funzione stavolta relativa al nodo 18
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.
Powered by phpBB © phpBB Group - Privacy policy - Cookie privacy
phpBB Mobile / SEO by Artodia.