Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Programma che stampa la visita preordine: loop
Forum - C/C++ - Programma che stampa la visita preordine: loop

Avatar
Puffetta (Normal User)
Rookie


Messaggi: 21
Iscritto: 29/11/2009

Segnala al moderatore
Postato alle 15:31
Sabato, 21/05/2011
Ciao a tutti, devo creare un programma che preso in input un albero binario completo o semicompleto(se la foglia non c'è metto zero), mi stampa la sua visita preordine. Io ho fatto vari tentativi ma il programma va sempre in loop.
Potreste darmi una mano a risolvere questo problema? io programmo da poco e non so bene dove mettere le mani.

Il codice che ho fatto è il seguente:

Codice sorgente - presumibilmente C++
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<math.h>
  4. #define SIZE 31
  5.  
  6. int main()
  7.     {
  8.           int v[SIZE];
  9.           int i=0, padre=0, rad=0;
  10.          
  11.           scanf("%d",&(v[0]));
  12.           scanf("%d %d", &(v[1]),&v[2]);
  13.           scanf("%d %d %d %d", &(v[3]),&v[4], &v[5], &v[6]);
  14.           scanf("%d %d %d %d %d %d %d %d", &(v[7]),&v[8], &v[9], &v[10], &(v[11]), &(v[12]), &(v[13]), &(v[14]));
  15.           scanf("%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d", &(v[15]),&v[16], &v[17], &v[18], &(v[19]), &(v[20]), &(v[21]), &(v[22]), &(v[23]), &(v[24]), &(v[25]), &(v[26]), &(v[27]), &(v[28]), &(v[29]), &(v[30]));        
  16.          
  17.           while(i<SIZE)
  18.                  {
  19.                      if((v[i]==0)&&(i<SIZE))
  20.                             i=2*padre+2;
  21.                            
  22.                      if((v[i]!=0)&&(i<SIZE))
  23.                         {
  24.                             printf("%d\n", v[i]);      
  25.                            
  26.                             //Ho figlio sinistro?
  27.                             if((v[(2*i+1)]!=0)&&((2*i+1)<SIZE))
  28.                                 {
  29.                                    padre=i;
  30.                                    i=2*i+1;
  31.                                 }
  32.                            
  33.                             else
  34.                                {  
  35.                                    
  36.                                    //se non ho il figlio sinistro, ho il figlio destro?
  37.                                    if((v[2*i+2]!=0)&&((2*i+2)<SIZE))
  38.                                        {
  39.                                           padre=i;
  40.                                           i=2*i+2;
  41.                                        }                                      
  42.                                    //se non ho nessuno dei due cerco di tornare alla prima radice non nulla.
  43.                                    else
  44.                                        {
  45.                                             i++;
  46.                                  
  47.                                             if((v[i]!=0)&&(i<SIZE))   printf("%d\n", v[i]);
  48.                                            
  49.                                             rad=(int)ceil(((double)padre)/2.-1.);
  50.                                            
  51.                                             if((2*i+1<SIZE)&&(2*i+2<SIZE))
  52.                                               {                                  
  53.                                                  if((v[2*i+1]==0)&&(v[2*i+2]==0))
  54.                                                   {
  55.                                                       i=2*rad+2;
  56.                                          
  57.                                                       if(i==padre)
  58.                                                           {
  59.                                                               padre=(int)ceil(((double)rad)/2.-1.);
  60.                                                               i=2*padre+2;    
  61.                                                           }                            
  62.                                                   }
  63.                                               }
  64.                                          
  65.                                             else
  66.                                               {
  67.                                                   i=2*rad+2;
  68.                                                  
  69.                                                   if(i==padre)
  70.                                                       {
  71.                                                           padre=(int)ceil(((double)rad)/2.-1.);
  72.                                                           i=2*padre+2;
  73.                                                          
  74.                                                           if(padre==1)    i=padre++;
  75.                                                       }                                                              
  76.                                               }    
  77.                                         }
  78.                                }
  79.                         }                    
  80.                  
  81.                  }      
  82.          
  83.           system("PAUSE");
  84.           return 0;
  85.     }

Ultima modifica effettuata da Puffetta il 21/05/2011 alle 15:33
PM Quote
Avatar
Oligoatria (Founder Member)
Pro


Messaggi: 79
Iscritto: 20/02/2006

Segnala al moderatore
Postato alle 16:29
Sabato, 21/05/2011
Non penso sia la strada migliore. Google risponde bene alla ricerca "visita preorder C". Una semplice realizzazione è al link

it.wikipedia.org/wiki/Visita_pre-order

void PreOrder(nodo)
{
  if ( nodo == NULL ) return;
  visita( nodo );
  PreOrder( nodo->sinistra );
  PreOrder( nodo->destra );
  return;
}

Naturalmente questo necessita di una struttura dati di qualità migliore, diciamo. Ti consiglio dunque, se non l'hai già fatto, di prendere confidenza con i concetti di "puntatore" e "ricorsione". Di libri, guide ecc. ne trovi facilmente su google.
Piuttosto che far fatica inutilmente, secondo me, ti conviene imparare questi concetti basilari che ti saranno utili in molte altre cose.

PM Quote
Avatar
Puffetta (Normal User)
Rookie


Messaggi: 21
Iscritto: 29/11/2009

Segnala al moderatore
Postato alle 18:19
Sabato, 21/05/2011
hai pienamente ragione a riguardo, ma mi è stata imposta la seguente realizzazione iterativa...

PM Quote
Avatar
Ultimo (Member)
Guru


Messaggi: 877
Iscritto: 22/05/2010

Segnala al moderatore
Postato alle 18:34
Sabato, 21/05/2011

Se rimane in loop vuol dire che i rimane sempre inferiore a 31

If ok Then GOTO Avanza else GOTO Inizia

PM Quote
Avatar
Puffetta (Normal User)
Rookie


Messaggi: 21
Iscritto: 29/11/2009

Segnala al moderatore
Postato alle 23:40
Sabato, 21/05/2011
si, l'avevo pensato anche io, ma il problema è che qualsiasi altra condizione io imposti o è inutile e quindi continua ad andare in loop o mi blocca l'esecuzione del programma.

PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 5:53
Domenica, 22/05/2011
:noway:

Ricomincia da capo. Quel codice è un guazzabuglio. Se devi utilizzare il C che non ti offre gli stack, utilizza un array per simulare uno stack (un push assegna il valore all'elemento corrente e incrementa l'indice, un pop decrementa l'indice).

http://en.wikipedia.org/wiki/Stack_%28data_structure%29

Codice sorgente - presumibilmente C++
  1. public void iterativePreorder(Node root) {
  2.    Stack nodes = new Stack();
  3.    nodes.push(root);
  4.    Node currentNode;
  5.    while (! nodes.isEmpty()){
  6.       currentNode = nodes.pop();
  7.       Node right = currentNode.right();
  8.       if (right != null)
  9.          nodes.push(right);
  10.       Node left = currentNode.left();
  11.       if (left != null)
  12.          nodes.push(left);      
  13.       System.out.println("Node data: "+currentNode.data);
  14.    }
  15. }

Il mio blog: https://piero.dev
PM Quote
Avatar
Puffetta (Normal User)
Rookie


Messaggi: 21
Iscritto: 29/11/2009

Segnala al moderatore
Postato alle 16:26
Domenica, 22/05/2011
so che praticamente per fare questo programma ci sono metodi e strutture migliori di quelle che uso, ma mi è stato imposto di farlo senza ricorsione e ci sono stati insegnati a stento i puntatori, quindi io non so usare tutte queste strutture comode che mi chiedete di fare

PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 18:40
Domenica, 22/05/2011
Ti sono stati insegnati gli array e bastano ed avanzato per simulare uno stack. E non è magia nera. Hai letto la pagina che ti ho linkato? Hai capito cos'è uno stack? Dopo che hai capito quello, implementare l'algoritmo che ti ho riportato dovrebbe essere piuttosto semplice. Se hai dubbi chiedi.

Il mio blog: https://piero.dev
PM Quote