PDA

Visualizza la versione completa : [C] alberi binari


shAke82
21-04-2004, 12:04
Mi servirebbe il programma per stampare un albero in preordine in modo ITERATIVO. Non riesco a capire come si possa fare :cry:

PunkIvi
21-04-2004, 12:50
http://datastructures.itgo.com/trees/nrtraversal.htm

shAke82
25-04-2004, 15:35
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... :cry:

shAke82
21-05-2004, 14:31
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... :cry:

help! :stordita:

cristiano_longo
21-05-2004, 16:10
Potresti salvare su uno stack i nodi mentre scendi. In tutto così simuli però una ricorsione.

anx721
21-05-2004, 17:37
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]{®©
23-05-2004, 22:43
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... :cry:

help! :stordita:
guarda che funziona.. io con quello ho implementato il programma :fagiano:
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... :fagiano:

Loading