[C] Visita simmetrica albero binario di ricerca

Messaggioda JustBreathe » 26/06/2019, 16:30

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!
JustBreathe
Starting Member
Starting Member
 
Messaggio: 40 di 45
Iscritto il: 13/05/2019, 20:59

Re: [C] Visita simmetrica albero binario di ricerca

Messaggioda giovx24 » 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!



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);
giovx24
Junior Member
Junior Member
 
Messaggio: 158 di 200
Iscritto il: 13/06/2018, 12:53

Re: [C] Visita simmetrica albero binario di ricerca

Messaggioda JustBreathe » 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);


Ciao, innanzitutto grazie per avermi risposto.
Sto digerendo il concetto anche se non mi risulta facilissimo.
Ti volevo chiedere se secondo te, il comportamento delle funzioni ricorsive in un programma può essere riassunto da questa immagine:


Immagine


P.s. So che non è buona norma pubblicare foto nei post, ma non sapevo come altro rappresentare ciò.
JustBreathe
Starting Member
Starting Member
 
Messaggio: 43 di 45
Iscritto il: 13/05/2019, 20:59

Re: [C] Visita simmetrica albero binario di ricerca

Messaggioda giovx24 » 28/06/2019, 18:58

che casino :-D
non mi convince molto, magari prova a spiegarmi
giovx24
Junior Member
Junior Member
 
Messaggio: 165 di 200
Iscritto il: 13/06/2018, 12:53

Re: [C] Visita simmetrica albero binario di ricerca

Messaggioda JustBreathe » 29/06/2019, 19:59

giovx24 ha scritto:che casino :-D
non mi convince molto, magari prova a spiegarmi


ok provo a spiegarmi meglio prendendo in considerazione la funzione proposta.
Voglio fare un esempio per capire bene.
Prendo per esempio tale albero.




Immagine






provo a fare una descrizione step-by-step di cosa succederebbe se utilizzassi tale funzione su questo albero...

Codice:
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);


Fino a che il puntatore sarà diverso da NULL
effettuerò stampa (I search the left son)
Dopodichè effettuerò chiamata a funzione della stessa con input puntatore al "figlio" sinistro.
Effettuerò tale operazione ricorsiva fino a che non giungerò al'ultimo "figlio" posto nella posizione più a sinistra, (la foglia posta nella posizione più a sinistra).
Una volta giunto al tale figlio, a tale foglia....

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... ");
 }


stampo (I print the value..) (I search the right son) e verifico se foglia posta in posizione "estrema sinistra" ha figlio destro.

Nell'albero preso in considerazione, foglia contenente valore 6 non ha figlio destro.
Cosa succede a questo punto all'interno della funzione, come procede?
Come fa a passare al nodo contenente il valore 16?

Grazie mille in anticipo!
JustBreathe
Starting Member
Starting Member
 
Messaggio: 44 di 45
Iscritto il: 13/05/2019, 20:59

Re: [C] Visita simmetrica albero binario di ricerca

Messaggioda giovx24 » 29/06/2019, 20:26

è 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
giovx24
Junior Member
Junior Member
 
Messaggio: 167 di 200
Iscritto il: 13/06/2018, 12:53

Re: [C] Visita simmetrica albero binario di ricerca

Messaggioda JustBreathe » 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


Grazie mille, gentilissimo!!
JustBreathe
Starting Member
Starting Member
 
Messaggio: 45 di 45
Iscritto il: 13/05/2019, 20:59


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 14 ospiti