[C] BST tramite array: Problemi visite

[darksergio]

Ok, mi è stato chiesto di implementare un algoritmo per creare un Albero binario di ricerca, implementandolo su array... la costruzione va a buon fine, e in effetti ottengo l'albero da me desdiderato... tuttavia a questo punto non riesco ad implementare correttamente una function di visita INorder, utile a dimostrare la correttezza della costruzione del mio albero... il risultato dovrebbe essere la visualizzazione ordinata degli elementi dell'array (in linea teorica ) ma sfortunatamente ottengo solo una parte dei valori e nemmeno ordinati

il codice è questo:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/*Scrivere function C iterativa per la costruzione
  di un albero binario di ricerca rappresentato mediante array.*/



int* creatree(int[],int);//crea albero
void inorder(int*);//visita inorder



int main()
{

    int  i,*albero;
    int array[10]={0,5,7,8,1,6,3,4,9,2};

	printf("--Array iniziale: \n\n-");
	for(i=0;i<9;i++)
	 printf("%d-",array[i+1]);

	albero=creatree(array,10);

	printf("--Array finale: \n\n-");
	for(i=0;i<15;i++)
	 printf("%d-",albero[i+1]);

	printf("--Visita inorder: \n\n-");
	inorder(albero);

    return 0;
 }

 int* creatree(int vett[],int dim)
{
   int *pt;
   int i,j=1;

      pt=calloc(16,sizeof(int));


   pt[1]=vett[1];
   i=2;//secondo elemento effettivo

   while(i<dim)
   {
     j=1;
printf("\n#%d# - #%d# (%d)",vett[i],pt[j],j);
   do{

      while(vett[i]<pt[j] && pt[j]!=0)
      {j=2*j;printf("\n#%d# - #%d# (%d)",vett[i],pt[j],j);}

      while(vett[i]>pt[j] && pt[j]!=0)
      {j=2*j+1;printf("\n#%d# - #%d# (%d)",vett[i],pt[j],j);}

    }while(pt[j]!=0);

    pt[j]=vett[i];

      i++;
   }
			return pt;
}

void inorder(int *pt)
{
   int i=1;
   printf("\n*%d*\n",pt[i]);

  if(pt[i]!=0)
  {
     inorder(pt+(2*i));
     printf("%d-",*(pt+i));
     inorder(pt+(2*i+1));
  }
}

non riesco bene a capire dove sia l'errore... probabilmente è una sciocchezza da flaggellazione ma ho passato la notte in bianco e sto perdendo colpi :S un anima pia potrebbe aiutarmi ad identificare l'errore?

[darksergio]

c'è qualcosa chen non va nel post??? 6 visite e nessuna risposta

Oregon, Batti un colpo x)

[darksergio]

Originariamente inviato da darksergio
Ok, mi è stato chiesto di implementare un algoritmo per creare un Albero binario di ricerca, implementandolo su array... la costruzione va a buon fine, e in effetti ottengo l'albero da me desdiderato... tuttavia a questo punto non riesco ad implementare correttamente una function di visita INorder, utile a dimostrare la correttezza della costruzione del mio albero... il risultato dovrebbe essere la visualizzazione ordinata degli elementi dell'array (in linea teorica ) ma sfortunatamente ottengo solo una parte dei valori e nemmeno ordinati

il codice è questo:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/*Scrivere function C iterativa per la costruzione
  di un albero binario di ricerca rappresentato mediante array.*/



int* creatree(int[],int);//crea albero
void inorder(int*);//visita inorder



int main()
{

    int  i,*albero;
    int array[10]={0,5,7,8,1,6,3,4,9,2};

	printf("--Array iniziale: \n\n-");
	for(i=0;i<9;i++)
	 printf("%d-",array[i+1]);

	albero=creatree(array,10);

	printf("--Array finale: \n\n-");
	for(i=0;i<15;i++)
	 printf("%d-",albero[i+1]);

	printf("--Visita inorder: \n\n-");
	inorder(albero);

    return 0;
 }

 int* creatree(int vett[],int dim)
{
   int *pt;
   int i,j=1;

      pt=calloc(16,sizeof(int));


   pt[1]=vett[1];
   i=2;//secondo elemento effettivo

   while(i<dim)
   {
     j=1;
printf("\n#%d# - #%d# (%d)",vett[i],pt[j],j);
   do{

      while(vett[i]<pt[j] && pt[j]!=0)
      {j=2*j;printf("\n#%d# - #%d# (%d)",vett[i],pt[j],j);}

      while(vett[i]>pt[j] && pt[j]!=0)
      {j=2*j+1;printf("\n#%d# - #%d# (%d)",vett[i],pt[j],j);}

    }while(pt[j]!=0);

    pt[j]=vett[i];

      i++;
   }
			return pt;
}

void inorder(int *pt)
{
   int i=1;
   printf("\n*%d*\n",pt[i]);

  if(pt[i]!=0)
  {
     inorder(pt+(2*i));
     printf("%d-",*(pt+i));
     inorder(pt+(2*i+1));
  }
}

non riesco bene a capire dove sia l'errore... probabilmente è una sciocchezza da flaggellazione ma ho passato la notte in bianco e sto perdendo colpi :S un anima pia potrebbe aiutarmi ad identificare l'errore?

ovviamente il problema si trova nella function di visualizzazione, quindi non si tratta di leggere tutto il codice...

[darksergio]

bhè alla fine ho risolto da solo, grazie comunque...