[Alberi] cammini

[MMPP12]

Ciao a tutti! Sto risolvendo questo esercizio:

Scrivere una funzione C che, ricevendo come parametri di input un albero binario di interi
T ed un intero x, restituisce la lista vuota se x non appare come etichetta in T,
altrimenti restituisce una lista con tutte le etichette che appaiono nel cammino
dalla radice a x. Se x occorre più volte in T, restituire un cammino ad una
qualsiasi delle occorrenze di x in T



Ho provato ad utilizzare una filosofia da visita preorder scrivendo:

lista cammino(lista W, tree A, int h){
	addCODA(W,A->key);
	if(A->key==h) return W;
	cammino(W,A->right,h);
	cammino(W,A->left,h);
}


lista camminoG(tree Tr, int x){
	lista LO; LO==NULL;
	if(Tr==NULL) return LO;
	LO=cammino(LO,Tr,x);
	return LO;
}

Ma il programma si arresta appena inserisco il valore x da ricercare!!
Mi potete dire cosa non va??

Vi lascio sotto il codice completo

#include<stdio.h>
#include<stdlib.h>

typedef struct Lis {
	int val;
	struct Lis *next;
} listanode ;

typedef listanode * lista;

typedef struct tNode {
	int key;
	struct tNode *left;
	struct tNode *right;
} treeNode ;

typedef treeNode * tree;


lista addHead(lista L, int elem){
	lista lAux=(lista) malloc(sizeof(listanode));
	lAux->val=elem;
	lAux->next=L;
	return lAux;
}

lista addCODA(lista L, int elemento){
	if (!L) return addHead(L,elemento);
	L->next=addCODA(L->next,elemento);
	return L;
}

void stampalista(lista s){
	lista p;
	p = s;
	while (p != NULL) {			
		printf("%d ", p->val);
		p = p->next;			
	}
	return;

}


lista cammino(lista W, tree A, int h){
	addCODA(W,A->key);
	if(A->key==h) return W;
	cammino(W,A->right,h);
	cammino(W,A->left,h);
}


lista camminoG(tree Tr, int x){
	lista LO; LO==NULL;
	if(Tr==NULL) return LO;
	LO=cammino(LO,Tr,x);
	return LO;
}


tree from_array_to_tree(int *V, int start, int size) {
	tree t;

	if (start >= size) return NULL; 
	
	if (V[start] == 0)return NULL;  
	else {

		t = (tree)malloc(sizeof(treeNode));
		t->key = V[start];
		t->left = NULL;
		t->right = NULL;
	}
	t->left = from_array_to_tree(V, 2*start+1, size); 
	t->right = from_array_to_tree(V, 2*start+2, size); 

	return t; 	
}

main(){
	lista l; l=NULL;
	tree TREE; TREE=NULL;
	
	
	int i, n, valore;
	int *A; 
	
	
	scanf("%d", &n);

	A = (int*)malloc(sizeof(int)*n);	
	for (i = 0; i < n; i++) {
		scanf("%d", &valore);
		A[i] = valore;
	}

	TREE = from_array_to_tree(A, 0, n);

    printf("\n\elemento g= ");
	int g; scanf("%d", &g);
		
	l = camminoG(TREE,g);
	stampalista(l);
	
return 0;
}

[apatriarca]

Guardo poi il codice con più attenzione, ma noto subito che hai sbagliato a inizializzare LO in camminoG.. Hai infatti scritto:

lista LO; LO==NULL;

ma avrebbe dovuto esserci un solo uguale.

In cammino devi poi memorizzare il valore restituito da addCODA. Il valore iniziale della lista è infatti NULL per cui L rimane tale e non gli viene assegnata la nuova testa come invece dovrebbe accadere. Manca inoltre da considerare il caso in cui l'albero passato a cammino sia uguale a NULL (possibilità tutt'altro che remota visto che ad un certo punto la ricorsione sull'albero dovrà arrivare ad un qualche nodo nullo..

[MMPP12]

Grazie per le osservazioni!
Essendo lista un puntatore alla testa della lista, non dovrebbe aggiornarsi in automatico ad ogni chiamata?
Sto pensando al caso mancante (in effetti avevo diemnticato che il valore x potrebbe non esserci!!)

[vict85]

Noto sin da subito che ti manca una funzione e ne hai messa almeno una inutile. Quello che tu devi implementare con la lista è quello che viene chiamato pila. Pertanto a te manca la funzione pop (mentre push è implementata da addCODA oppure da addHead a seconda di come vuoi implementare la cosa). Se usi addHead allora devi ricordarti di stampare la lista al contrario, se usi addCODA allora dovresti cambiare sia la sua implementazione che la definizione di lista perché scorrere tutta la lista ogni volta che metti qualcosa alla fine è terribilmente inefficiente per una pila. Io personalmente ti suggerisco di usare addHead perché la stampa la fai solo una volta e le implementazioni di push e pop risultano più semplici. Inoltre sarebbe meglio se non distruggessi immediatamente i nodi che togli con pop ma che li riutilizzassi nel successivo push (ma questo rientra nelle ottimizzazioni). Nota che comunque in genere le pile sono implementate con array e non come liste (cosa che potresti in realtà fare anche tu).

Inoltre, from_array_to_tree potrebbe allocare direttamente tutto l'albero (il numero di nodi dell'albero è uguale al numero di elementi nell'array) e chiamare una seconda funzione (volendo ricorsiva) per popolarlo.

[EDIT] Devi anche aggiungere tutto il codice per deallocare la memoria.

[MMPP12]

Grazie vict85!
L'esercizio richiede espressemente che dato l'albero e il nodo x, produca la lista del cammino dalla radice a x... Quindi sono "obbligato" ad usare l'inserimento in testa / coda delle liste.. in effetti per come ho impostato l'algoritmo una volta ottenuta la lista giusta, potrei rovesciare tutti gli elementi, senza complicare troppo tutto il resto

[apatriarca]

Una cosa che si dimentica spesso quando si lavora con la ricorsione è che questa passa due volte da ogni nodo: prima in discesa e poi in salita. Questo significa che è possibile eseguire del codice sia prima che dopo la ricorsione senza problemi. Nel tuo caso, siccome l'inserimento in testa è l'operazione più comoda per una lista e sai se l'elemento deve essere inserito nella lista solo dopo aver fatto la ricorsione, conviene fare tutto dopo. Quindi qualcosa tipo:

if (T->key == x) { return addHead(NULL, x); }
else if (T->left != NULL) { 
    L = cammino(L, T->left, x);
    if (L != NULL) { return addHead(L, T->key); }
} else if (T->right != NULL) { 
    L = cammino(L, T->right, x);
    if (L != NULL) { return addHead(L, T->key); }
} else { return NULL; }

[MMPP12]

"apatriarca":Una cosa che si dimentica spesso quando si lavora con la ricorsione è che questa passa due volte da ogni nodo: prima in discesa e poi in salita. Questo significa che è possibile eseguire del codice sia prima che dopo la ricorsione senza problemi. Nel tuo caso, siccome l'inserimento in testa è l'operazione più comoda per una lista e sai se l'elemento deve essere inserito nella lista solo dopo aver fatto la ricorsione, conviene fare tutto dopo. Quindi qualcosa tipo:

if (T->key == x) { return addHead(NULL, x); }
else if (T->left != NULL) { 
    L = cammino(L, T->left, x);
    if (L != NULL) { return addHead(L, T->key); }
} else if (T->right != NULL) { 
    L = cammino(L, T->right, x);
    if (L != NULL) { return addHead(L, T->key); }
} else { return NULL; }

grazie mille! sono riuscito a cogliere il senso!!