[C] alberi binari

[shAke82]

Mi servirebbe il programma per stampare un albero in preordine in modo ITERATIVO. Non riesco a capire come si possa fare

[PunkIvi]

http://datastructures.itgo.com/trees/nrtraversal.htm

[shAke82]

mi servirebbe qualcosa di specifico. In pratica devo implementare programmi ricorsivi in modo iterativo, per esempio con l'uso delle pile devo trasformare questa funzione hanoi ricorsiva in una iterativa:

void hanoi (int n, int *a, int *b, int *c)
{
........if(n==1) moveDisk(pa, pc);
........else
........{
............... hanoi (n-1,a,c,b);
................moveDisk (a,c);
................hanoi (n-1,b,a,c);
........}
}

(movedisk e' una funzione che sposta un disco)

Spero di esser stato chiaro e che qualcuno possa aiutarmi visto che sto trovando non poche difficolta' con ste cose...

[shAke82]

Originariamente inviato da PunkIvi
http://datastructures.itgo.com/trees/nrtraversal.htm

quest'algoritmo e' errato...

inorder(struct NODE *curr)
{
while(all the nodes are not over )
{
if(curr->left != NULL && ! visited(curr->left))
{
visit(curr->left);
curr = curr->left;
}
else
{
printf("%d", curr->value);
if(curr->right != NULL)
curr = curr->right;
else
if(curr->thread != NULL)
curr = curr->thread;
}
}
}

x esempio se l'albero fosse questo....

1 1
f
1 1
b
0 0
v
0 0
a
0 0
c

con una radice "f" con 2 figlio "b" e "v" e con "b" che ha 2 figli...stamperebbe a, b, c e al ritorno di c stamperebbe nuovamente b...cosa errata...

help!

[cristiano_longo]

Potresti salvare su uno stack i nodi mentre scendi. In tutto così simuli però una ricorsione.

[anx721]

Dal libro 'Strutture dati in C' di horowitz sahni e anderson-fred:

ALGORITMO ITERATIVO DI VISITA INORDER

#define MAX_STACK_SIZE 100


typedef struct nodo *treepointer;

typedef struct nodo {
	int dati;
	tree_pointer figlio_sinistro;
	tree_pointer figlio_destro;
}

void iter_inorder(tree_pointer nodo){
	int top = -1		//inizializza lo stack
	tree_pointer stack[MAX_STACK_SIZE];
	for(;;){
		for(; nodo; nodo = nodo -> figlio_sinistro)
			add(&top, nodo, stack);//inserisce nello stack
		nodo = delete(&top, stack);//elimina dallo stack
		if(! nodo)	//stack vuoto
			break;
		printf("\n%d", nodo -> dati);
		nodo = nodo -> figlio_destro;
	}

}


//inserimento nello stack
void add(int *top, tree_pointer item, tree_pointer stack[]){
	if(*top >= MAX_STACK_SIZE - 1)
		return;	//stack pieno
	stack[++*top] = item;
}


//elimina l'elemento in coma allo stack e lo resituisce
tree_pointer delete(int *top, tree_pointer stack[]){
	if(*top == -1)
		return NULL;//errore
	return stack[(*top)--];
}

:ciauz:

[}gu|do[z]{®©]

Originariamente inviato da shAke82
quest'algoritmo e' errato...

inorder(struct NODE *curr)
{
while(all the nodes are not over )
{
if(curr->left != NULL && ! visited(curr->left))
{
visit(curr->left);
curr = curr->left;
}
else
{
printf("%d", curr->value);
if(curr->right != NULL)
curr = curr->right;
else
if(curr->thread != NULL)
curr = curr->thread;
}
}
}

x esempio se l'albero fosse questo....

1 1
f
1 1
b
0 0
v
0 0
a
0 0
c

con una radice "f" con 2 figlio "b" e "v" e con "b" che ha 2 figli...stamperebbe a, b, c e al ritorno di c stamperebbe nuovamente b...cosa errata...

help!

guarda che funziona.. io con quello ho implementato il programma
sei tu che in visit() devi preoccuparti, oltre che a stampare, ad inserire il nodo in una lista di nodi già visitati (o stampati s preferisci) e in visited() vedere se l'elemento corrente presente nella lista...