[C] Visite Alberi

[Malloc]

Cavolo ragazzi....programmare sembrava una cosa carina per questo avevo deciso di impegnare l'estate provando a studiare il C da autodidatta grazie al web...Ma sta diventando assurdo..

Ho letto degli appunti sugli alberi, ed ho provato a fare un algoritmo che legge un array secondo i tre ordini di visita di un albero...

Ora però, o mi trovo le idee confuse, o qualcosa non va..

vi faccio vedere l'algoritmo

#include<stdio.h>

typedef struct {
	int dato; 
	int esiste;
	} nodo;


void inorder(nodo *albero,int i);
void preorder(nodo *albero,int i);
void postorder(nodo *albero,int i);

void main()
{

nodo albero[15]={{0,0},{1,1},{2,1},{3,1},{4,1},{5,1},{6,1},{0,0},{0,0},{7,1},{8,1},{0,0},{0,0},{9,1},{0,0}};
int pila[15],i=1;



printf("Inorder:\n");
inorder(albero,i);
printf("\n\n");
printf("Preorder:\n");
preorder(albero,i);
printf("\n\n");
printf("Postorder:\n");
postorder(albero,i);

system("PAUSE");
}



void inorder(nodo *albero,int i)
{
	if (albero[i].esiste==1) 
    {
		if  (albero[2*i].esiste==1)     
        inorder(albero,2*i);
		printf("%d \n",albero[i].dato);
		if  (albero[(2*i)+1].esiste==1) 
        inorder(albero,(2*i)+1);
		}
}

void preorder(nodo *albero,int i)
    {

     
if(albero[i].esiste==1)
     {
printf("%d\n",albero[i].dato);
       if (albero[(2*i)].esiste==1)
       preorder(albero,2*i);
                      
       if (albero[(2*i)+1].esiste==1)
       preorder(albero,(2*i)+1);
      }

} 



void postorder(nodo *albero,int i)
{    
	if (albero[i].esiste==1) 
    {
		if  (albero[2*i].esiste==1)
        postorder(albero,2*i);
		if  (albero[(2*i)+1].esiste==1)
        postorder(albero,(2*i)+1);
		printf("%d\n",albero[i].dato);
	}
}

i risultati sono

Inorder: 4-7-2-8-5-1-6-9-3
Preorder: 1-2-4-7-5-8-3-6-9
Postorder: 7-4-8-5-2-9-6-3-1


Avrò fatto un pò troppa confusione leggendo gli alberi...ma secondo me i risultati che stampa sono totalmente sbagliati...voi esperti che dite?



P.S. Lo so lo so il system("pause") non ci vuole..ma siccome non ci devo lavorare con il C, per ora mi esercito con questo visto che sempre sotto windows li devo provare i programmi

[YuYevon]

In ogni procedura di visita, prima di procedere con la chiamata ricorsiva, devi non solo chiederti se quel nodo che andrai a visitare esista o meno, ma innanzitutto se moltiplicando i per 2 o moltiplicandolo per 2 e poi sommandogli 1 non eccedi con l'indice di spiazzamento dell'array... ci sono solo 15 elementi, quindi se ad esempio i valesse 21 non dovresti procedere, e invece tu lo fai lo stesso. Prova a stampare gli indici per vedere cosa succede, e visto che stai imparando a programmare ora, prova a trovare una soluzione. Si tratta di apportare una piccola modifica...

[Malloc]

da quel che dici ho provato ad inserire negli if un limite alla i di 7 (i<=7)..così che nel caso di controllo a sinistra non andrò oltre il 14 per il controllo di destra non andrò oltre al 15...Ma i risultati me li stampa lo stesso in quell'ordine...ma mi chiedo l'ordine stampato è giusto o no?

Io da quel che ho letto un pò sugli alberi direi di no...eppure le tre visite se non sbaglio sono scritte bene o comunque nel loro ordine giusto...

Preorder stampa controlla a sinistra e poi a destra
Inorder controlla a sinistra, stampa e poi a destra
Post order controlla a sinistra, a destra e poi stampa

[YuYevon]

void inorder(nodo *albero,int i)
{
      if (albero[i].esiste==1) {

            if  (  i * 2 < 15 && albero[2*i].esiste==1)     
                  inorder(albero, 2 * i);

            printf("%d \n",albero[i].dato);

            if  (  i * 2 + 1 < 15 && albero[(2*i)+1].esiste==1) 
                  inorder(albero, 2 * i + 1);
      }
}

Similmente per gli altri due algoritmi.

Comunque guarda che i risultati che ottenevi fin dal primo post erano corretti

Pensavo fossero sbagliati non solo perché tu li hai presentati come tali ma anche perché compilando tutto con gcc su Linux ottenevo effettivamente qualche 0 qua e la che non ci doveva essere (e non mi ero accorto che a te questo non capitava).

Inorder:
4
7
2
8
0
5
1
6
9
3


Preorder:
1
2
4
7
5
8
0
3
6
9


Postorder:
7
4
0
8
5
2
9
6
3
1

In ogni caso apporta comunque quella correzione... che ti funzioni lo stesso dipende solo dal fatto che quando vai ad accedere ad un nodo che non c'è ottieni che il suo campo "esiste" è inizializzato a 0, ma questo è casuale... tant'è che compilando su linux il programma mi visitava un inesistente nodo di indice 21 il cui campo "esiste" era inizializzato a 1...

Con quella modifica ottengo infatti anche io l'output corretto, cioè quello che hai postato all'inizio!