Visita di un albero pre-in-post order

di il
8 risposte

Visita di un albero pre-in-post order

Ragazzi ho sviluppato la funzione per la visita preorder di un albero sviluppato tramite array
void preorder (int tree[])
{
    int radice=1, i=0, el=0, ver=1, figlio=1;
    Coda *head=NULL;
        head=calloc(1,sizeof(Coda));
        head->elem=radice;
        el++;
        printf("nodo:%d\n",tree[head->elem]);
        while(ver==1)
	{
		figlio=(head->elem)*2; //vedo se c'è il figlio sinistro
		if(figlio<=16 && tree[figlio]!=-1)
		{
			ins_nodo(figlio,&head); //inserisco il figlio sinistro nella pila
			el++;
			printf("nodo:%d\n",tree[head->elem]); //stampo l'elemento in cima alla pila
		}
		else
		{
			figlio=head->elem; //ritorno all'ultimo nodo visualizzato
			elim_testa(&head); //elimino elemento in testa alla pila
			el--;
			ver=0; //ver è una variabile di verifica
			while(ver==0)
			{
				figlio=(figlio*2)+1; //vedo se c'è il figlio destro
				if(figlio<=16 && tree[figlio]!=-1)
				{
					ins_nodo(figlio,&head); //inserisco il figlio destro nella pila
					el++;
					printf("nodo:%d\n",tree[head->elem]); //stampo l'elemento in cima alla pila
					ver=1; //quando trovo un figlio a destra la incremento ad uno cosi posso verificare se ci sono figli sinistri
				}
				else
				{
					if(el>0) //elimino elemento solo se la pila ha almeno un elemento..
					{
						figlio=head->elem;
						elim_testa(&head);
						el--;
					}
					else //altrimenti esco dal programma..
					ver=2;
                }
            }
        }
    }
}
come la modifico in modo tale da farla diventare le altre modalità di visità? grazie mille per le risposte

8 Risposte

  • Re: Visita di un albero pre-in-post order

    Nessuno proprio mi può aiutare?? è abbastanza urgente
  • Re: Visita di un albero pre-in-post order

    Perche ciò che hai fatto non è una visita in pre/post order ma un miscuglio di cose. Le visite sono fatte in modo ricorsivo almeno che la visita non sia in ampiezza.

    Guarda e studia la parte del codice presentato quà.
  • Re: Visita di un albero pre-in-post order

    Purtroppo per esercizio devo farlo in modo iterativo, se dovevo farlo ricorsivo avevo già finito da un pezzo
  • Re: Visita di un albero pre-in-post order

    Da Wikipedia:
    
    Diversamente dalla visita in profondità per i grafi e dalle sue varianti (pre-ordine, ordine, post-ordine) sugli alberi, la visita in ampiezza non può essere implementata come algoritmo puramente ricorsivo, ma è piuttosto un esempio di programmazione dinamica.
    
    http://it.wikipedia.org/wiki/Visita_in_ampiezz
  • Re: Visita di un albero pre-in-post order

    skynet ha scritto:


    Da Wikipedia:
    
    Diversamente dalla visita in profondità per i grafi e dalle sue varianti (pre-ordine, ordine, post-ordine) sugli alberi, la visita in ampiezza non può essere implementata come algoritmo puramente ricorsivo, ma è piuttosto un esempio di programmazione dinamica.
    
    http://it.wikipedia.org/wiki/Visita_in_ampiezz
    ma per me wikipedia può dire quello che vuole perdonami, ma la mia prof lo vuole iterativo ed io lo devo fare iterativo altrimenti l'esame non lo passo
  • Re: Visita di un albero pre-in-post order

    Ma hai un albero o una pila? Che centra l'inserimento e l'eliminazione con una visita?
  • Re: Visita di un albero pre-in-post order

    http://en.wikipedia.org/wiki/Tree_traversa

    Tutti gli esempi (tutti i modi di attraversamento, ricorsivo e non, RB-tree e NON) sono quì. Usa quel che ti chiede il prof. A me sembra strano che si parla di albero e tu lo rappresenti con un vettore cmq cavoli del prof se chiede cose senza senso.
  • Re: Visita di un albero pre-in-post order

    skynet ha scritto:


    http://en.wikipedia.org/wiki/Tree_traversa

    Tutti gli esempi (tutti i modi di attraversamento, ricorsivo e non, RB-tree e NON) sono quì. Usa quel che ti chiede il prof. A me sembra strano che si parla di albero e tu lo rappresenti con un vettore cmq cavoli del prof se chiede cose senza senso.
    No sò cavoli miei che le devo fare per passare l'esame al prof non importa. Comunque è un albero rapprensentato mediante array, quindi con la famosa regola del padre i/2 (con i indice dell'array) se diverso da 1 e che il figlio sinistro è 2*i ed il figlio destro è 2*i+1
Devi accedere o registrarti per scrivere nel forum
8 risposte