[C] Alberi

[MMPP12]

Salve a tutti! sto scrivendo un algoritmo in C che dato un albero binario di interi B e un intero q, restituisce la lista delle etichette dei nodi a livello q dell'albero, da sinistra a destra.

Assumo che $0\leqq\leqh(B)$, con $h(B)=$ altezzadell'albero.

La mia idea è questa:

lista livellokAUX(tree A, lista L, int k, int j){
	if(j==k){
	  L=insertTESTA(L,A->key);
	  return L;
	}
	else{
		if(A->right!=NULL)	livellokAUX(A->right,L,k,j+1);
		if(A->left!=NULL)	livellokAUX(A->left,L,k,j+1);
	}
}


lista  livelloK(tree B, int q){
	lista P; P=NULL;
	P=livellokAUX(B,P,q,0);	
	return P;
}

Dove la funzione insertTESTA inserisce in testa ad una lista il valore intero che riceve.

Tuttavia alla fine ottengo una lista che contiene solamente l'etichetta del primo nodo... non riesco a capire perchè non restituisce la lista completa

[Crispolto]

Controlla che cosa te ne fai del risultato delle due chiamate ricorsive!

[MMPP12]

mi sono dimenticato di inserire l'output!!

lista livellokAUX(tree A, lista L, int k, int j){
	
	if(j==k){
	  return L=addHead(L,A->key);
	}
	
	else{
	    if(A->right!=NULL)  	L=livellokAUX(A->right,L,k,j+1);
		if(A->left!=NULL)	L=livellokAUX(A->left,L,k,j+1);
		
	}
	
}

lista  livelloK(tree B, int q){
	lista P; P=NULL;
	P=livellokAUX(B,P,q,0);	
	return P;
}

Ora l'algoritmo sembra funzionare.

Ma nel caso in un livello dell'albero manchino dei nodi, la lista prodotta è incompleta. Esempio[nota](lo so è una rappresentazione orribile!!!)[/nota]:

1
/ \
2 3
/ \ \
4 5 7

se metto in input il livello 2 ottengo la lista

5 -> 4 -> NULL (e non 7->5 -> 4 ->NULL)

eppure mi sembra tutto corretto..........

[Crispolto]

Ora nel caso in cui ti trovi ad un nodo ad un livello diverso da k non restituisci nulla.

[apatriarca]

Ma l'esercizio chiede da sinistra a destra mentre nel tuo caso vedo che l'output che cerchi di ottenere è da destra a sinistra.. Nella funzione ausiliaria c'è inoltre un solo return. Cosa restituisci se non sei al livello corretto?

[MMPP12]

Allora l'agoritmo effettivamente visita prima i nodi a destra inserendoli in testa alla lista cosicché alla fine l'ultimo nodo inserito è quello più a sinistra ed è quindi il primo della lista.


ho inserito un return L; alla fine delle funzione ausiliaria... ora funziona.

Ma sinceramente non capisco perchè com'era scritto prima in questo caso

1
/ \
2 3
/ \ / \
4 5 6 7

per livello=2 fornisca lo stesso la lista giusta 4 5 6 7

mentre se inserisco

1
/ \
2 3
/ \ \
4 5 7

viene fuori la lista 4 5