[C] Cercare un nodo in un albero n-ario

[jacopos81]

ecco il codice:

struct node *cerca(struct node *root,struct node *elemento){
// cerca il nodo elemento nell'albero radicato in root
	printf("nodo in esame: %s\n",root->name);
	if (strcmp(root->name,elemento->name) == 0) {	// controlla radice
		printf("trovato\n");
		return root;
	} else { 
		if (root->children != NULL) {
			iterator i = get_iterator(root->children);
			while (has_next(i)) { 
				struct node *temp = (struct node *)next(i);
				//if (strcmp(temp->name,elemento->name) == 0) return temp;
				return cerca(temp,elemento);
			}
		}
	}		
}

da notare che per scorrere le liste dei figli uso degli "iteratori" che sono delle funzioncine pensate (obblgatorie da specifiche) appunto per scorrere una lista.

struct iterator {
	struct NodoLista *pt;		
}; 

typedef struct iterator *iterator;

iterator get_iterator(list l) {
// crea un nuovo iteratore sulla lista l
	iterator i = (iterator)malloc(sizeof(struct iterator));
	if (l == NULL) {
		i->pt = NULL;
		return i;
	}
	i->pt = l;
	return i;
}
int has_next(iterator i) {
// se i non è alla fine della lista torna 1, altrimenti 0
	if (i->pt == NULL) return 0;
	else return 1;
}

void *next(iterator i) { 
	void *prec; 
	if (i->pt != NULL) { 
    		prec = (i->pt)->value; 
    		i->pt = (i->pt)->next;
    		return prec; 
 	} 
	return NULL; 
}