[C] albero 4 figli verificare se è un ABR considerando nodi a due a due

[mame83]

Ciao , ho il seguente problema in C: dato un albero definito in questo modo:

typedef struct nodo
   {
     int info;
     struct nodo  *left1;
     struct nodo  *left2;
     struct nodo  *right1;
     struct nodo  *right2;
   } nod;

devo verificare se l abero è un ABR rispetto alla somma dei nodi left1 e left2 e alla somma dei nodi right1 e right2.

void visita(nod *radice, int *min, int *risp , int *somma)
{
  if (radice != NULL)
    {
      visita(radice->left1,min,risp,somma);
      *somma= *somma+radice->info;
      visita(radice->left2,min,risp,somma);  
      if (radice->info != *somma)
        *somma=radice->info+ *somma;
      if (*min < *somma)
        {
         *min = *somma;
         printf("\n aggiorniamo min %d \n",*min);
           
        }
      else
        {
          *risp = 1;
          printf("aggiorniamo risp %d \n",*risp); 
        }
      somma=0;    
      visita(radice->right1,min,risp,somma);
      visita(radice->right2,min,risp,somma);
    }            
}  

int isBst(nod *root)/*0 se abr 1 NO - FUNZIONE PRINCIPALE- */
{
  int min = INT_MIN;
  int ok = 0;
  int somma = 0;
  visita(root,&min,&ok,&somma);
  printf("valore di ok e' %d \n",ok);
  if (ok == 0)
    return 0;
  else
    return 1;
}

La funzione prinicipale è isBst, all interno richiamo visita inizializzando min al minimo intero, somma e ok a 0.
In output mi restituisce sempre 1 cioe che non è un abr. Ragazzi non so piu come fare
Spero che qualcuno mi aiuti, grazie in anticipo

[mame83]

Spero di aver spiegato bene il problema, Ragazzi spero mi aiutate help help!!!!!!!

[mame83]

nell albero binario per vedere se è un ABR, verifico se la successione che ho in output, facendo la visita in ordine è crescente. Nell albero a 4 figli questo non è possibile. qualcuno mi saprebbe dire come devo ragionare per verificarlo ??????? grazie!!!!!!!!!

[mame83]

ragazzi non mi vengono idee MI AIUTATE!!!!!!!!

[mame83]

nell albero binario per verificare se è un abr faccio in questo modo:

int isBST2(nod *root, int min, int max)
{
  
  if (root == NULL) 
     return 0;
  
  if (root->info > min && root->info <= max &&
       isBST2(root->sinistro, min, root->info) == 0 &&
       isBST2(root->destro, root->info, max) == 0) 
     return 0;
  else 
     return 1;
}

int isBst(nod *root)/*0 se abr 1 NO*/
{
 if (isBST2(root,INT_MIN,INT_MAX) == 0)/*minimo intero e massimo intero gia
                                         assegnati di default*/
   {
    printf("l albero e' un ABR \n");
    return 0;
   } 
 else
   {
    printf("l albero non e' un ABR \n");
    return 1;  
   } 
}

come devo modificarlo in caso di albero a 4 figli considerando sinistro= left1+left2 e destro =right1 + right2?????

[pistilloi]

Scusa, ma cosa intendi per "abr" ?

[mame83]

per ABR si intende un albero binario di ricerca. nel cao in questione verifichiamo che la somma dei valori di left1 e left2 deve essere minore o uguale alla radice e la somma dei valori di right1 e right2 maggiore della radice

[pistilloi]

Per l'appunto, avendo il tuo albero 4 figli, non è un'albero binario(max 2 figli); quindi si può determinare a priori, che non è un'abr.

[mame83]

andiamo a considerare l albero binario prendendo sinistro=left1+left2 e destro=right1+right2. Cosi facendo formiamo un albero binario e dobbiamo vedere se è un albero binario di ricerca. spero di essere stato chiaro

[pistilloi]

Io approccerei il problema in maniera diversa: prima di tutto, creerei un'albero binario contenente nel figlio di destra la somma dei figli destri dell'albero con quattro figli e in maniera analoga definirei anche il figlio sinistro. Poi senza creare nuove funzioni di visita, utilizzerei quella che sicuramente hai già costruito per visitare un'albero binario.
Che ti pare?