Ciao a tutti, non riesco a venirne fuori con il problema seguente, quindi chiedo un vostro aiuto.
Dato un albero e un intero k, devo creare una nuova struttura dati (FIFO) contenente i valori dell'albero, solo se il nodo di quest'ultimo è un multiplo di k e visitando l'albero in ordine infisso, ovvero prima il nodo a sinistra, poi la radice e infine il nodo a destra. Ad esempio l'albero
4
/ \
2 6
/ \ /
1 3 5
sarebbe visitato in modo infisso in ordine 1 2 3 4 5 6.
Ho queste strutture già definite:
struct nodo { int info; nodo* next; nodo(int a=0, nodo* b=0) {info=a; next=b;}}; //nodo lista
struct FIFO { nodo* primo, *ultimo; FIFO(nodo*a=0, nodo*b=0) {primo=a; ultimo=b;}}; //primo punta al primo nodo della lista, ultimo all'ultimo
struct nodot { int info; nodot* left, *right; nodot(int a=0, nodot* b=0, nodot* c=0) {info=a; left=b; right=c;}}; //nodo albero
La funzione che fa quanto richiesto ha il seguente prototipo
FIFO crea_lista (nodot *R, int &n, int k) //R punta al nodo dell'albero, n mi serve per vedere se sono arrivato al nodo k-esimo ed è inizializzato a 1
Quindi la lista la devo creare al ritorno delle chiamate ricorsive. E quello che non ho capito è proprio questo, come faccio a "visitare" l'albero all'andata delle chiamate di funzione e costruire la struttura al ritorno? Aggiungo, così magari può esservi più chiaro, una funzione simile che però invece di creare la lista con i nodi "giusti", semplicemente li stampa
void stampa(nodot *R, int &n, int k){
if(R){
stampa(R->left, n, k);
if(n==k){
n=0;
cout<<R->info<<" ";
}
n=n+1;
stampa(R->right, n, k);
}
}
Spero siate riusciti a capire il problema nonostante la mia spiegazione un po' confusa