[c] visita albero

[Prince_81]

Seguendo alcuni esempi per creare un algoritmo di visita preorder di un albero ho creato il seguente algoritmo.

int i,j,n=15;
int albero[]={-1,0,1,2,3,4,5,6,-2,-2,7,8,-2,-2,-2,9};
int stack[4];

j=1,i=0;
while(j<=n){
if(j == 1){
stack[i]=j;
i++;
}
while(albero[stack[i-1]*2] != -2 && 2*stack[i-1] <= n){
stack[i++]=j*2;
j++;
}
i--;
while(albero[stack[i]*2+1] == -2 || stack[i]*2+1 > n){
printf("%d\t",albero[stack[i]]);
i--;
}
if(i >= 0){
printf("%d\t",albero[stack[i]]);
puts("");
}
if(albero[stack[i]*2+1] != -2 && stack[i]*2+1 <= n){
j=stack[i];
stack[i]=j*2+1;
j=stack[i++];
}

}

il problema è che per me la visita è inorder no preorder sapreste dirmi voi che tipo di visita è ?

p.s. l'algorimo alla fine visualizza un messaggio di errore non fateci caso devo metterlo a punto.

[DanieleC88]

Puoi partecipare all'IOCCC (http://en.wikipedia.org/wiki/International_Obfuscated_C_Code_Contest) secondo me. :D
Prima di darti da fare con gli alberi, lavora un po' sulla leggibilità del codice. Delle discussioni illuminanti al riguardo sono quelle in cui fek ha partecipato all'incirca un paio di anni fa, purtroppo non ce l'ho nei segnalibri, sennò te le passerei. Io nel tuo codice (è anche che stasera sto un po' stonato) non riesco a leggere niente, abituati a scrivere codice "che si spiega da solo", i tuoi occhi ringrazieranno.
Insomma, stasera non sono in grado di aiutarti, magari domani provo a spulciare un po' il tuo codice. :)

ciao ;)

[Prince_81]

Penso d'aver rispettato alla lettera le istruzioni del materiale didattico che mi hanno dato, è un metodo iterativo per visualizzare un albero, è normale che ci saranno codici migliori anche sotto l'aspetto computazionale, ma non è il mio caso che sto all'inizio.

Per quanto riguarda il concorso che mi hai consigliato non penso proprio in quanto il codice è leggibile e per il livello che ho raggiunto, cioè base, è più che sufficiente.

Lascia stare comunque se devi sforzarti gli occhi per leggere il mio umile codice [c] ci rimarrei male.

:tapiro:

[wingman87]

Indenta il codice. Poi forse qualcuno ti aiuterà

[Prince_81]

non c'è niente da indentare non voglio sapere se il codice funziona e nemmeno come migliorarerne la complessità volevo sapere solo se in base ai dati di output la visita era preorder inorder o postorder.

[wingman87]

Allora perché hai postato il codice? Posta input e output e basta

[DanieleC88]

Pince_81, non è un problema di performance o costo computazionale, l'alternativa è ricorrere alla ricorsione, che è un metodo più dispendioso in termini di tempo e spazio.

Mi sembra che tu l'abbia presa a male, ma guarda che il mio era un semplice consiglio. Hai detto tu stesso di essere agli inizi: bene, un motivo in più per iniziare col piede giusto invece di prendere cattive abitudini da correggere con fatica più tardi. Se ti abitui a fare degli sforzi per rendere il codice "autoesplicativo", vedrai che sarà molto più facile scrivere codice corretto ed eventualmente isolarne i difetti o le parti che è possibile migliorare. Insomma, il problema non è lo sforzo dei miei occhi, il problema è che così sono i tuoi stessi occhi a doversi sforzare più del necessario...

Tornando al punto centrale del thread, al momento non mi è possibile compilare, quindi se vuoi un aiuto posta l'output del tuo programma.

[Prince_81]

Daniele lo so che la ricorsione andrebbe meglio e sarebbe anche più elegante da scrivere ma se all'esame vogliono un algoritmo iterativo io che ci posso fare? comunque è anche vero che potevo postare anche solo input e output non ci avevo pensato. Disegnerò gli alberi di input e output e li allegherò al prossimo messaggio.

Non mi sono arrabbiato sono stato frainteso a causa dello sbaglio che mi hanno fatto notare cioè non dovevo postare l'algoritmo.

Grazie lo stesso.

[71104]

Daniele lo so che la ricorsione andrebbe meglio e sarebbe anche più elegante da scrivere ma se all'esame vogliono un algoritmo iterativo io che ci posso fare? prendi in giro...? rileggi il post #7 e stavolta leggilo bene.

[71104]

posto il codice formattato un po' meglio.

int i, j, n = 15;

int albero[] = { -1, 0, 1, 2, 3, 4, 5, 6, -2, -2, 7, 8, -2, -2, -2, 9 };

int stack[4];

j = 1;
i = 0;

while (j <= n)
{
if (j == 1)
{
stack[i]=j;
i++;
}
while ((albero[stack[i - 1] * 2] != -2) &&
(2 * stack[i - 1] <= n))
{
stack[i++] = j * 2;
j++;
}
i--;
while ((albero[stack[i] * 2 + 1] == -2) ||
(stack[i] * 2 + 1 > n))
{
printf("%d\t", albero[stack[i]]);
i--;
}
if (i >= 0)
{
printf("%d\t", albero[stack[i]]);
puts("");
}
if ((albero[stack[i] * 2 + 1] != -2) &&
(stack[i] * 2 + 1 <= n))
{
j = stack[i];
stack[i] = j * 2 + 1;
j = stack[i++];
}
}