Funzione ricorsiva BST

di Anonimizzato29386 il
6 risposte
/
Anonimizzato29386
Utente anonimizzato
BuonSalve,
Mi sto approcciando alle strutture dati e in questo caso nello specifico gli alberi.
Questo è un esercizio:
"Scrivere una funzione ricorsiva struct treeNode * inalbera(int * a, int N) che, ricevuto in ingresso un array di N interi, restituisca un albero binario contenente tali interi. Che tipo di albero viene prodotto se l'array e' ordinato?"
Questo è il codice scritto fino adesso: 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

 
typedef struct tree_
{
   struct tree_* left;
   int data;
   struct tree_* right;
}tnode;
typedef tnode* tlink;
 
tlink inalbera(int * a, int N)
{
  if(N == 0) 
  {
  tlink node = NULL;
  return node;
  }
  else inalbera(a, N - 1);
}

void stampa(tlink pippo)
{   static int level = 0;
    if(pippo)
    {    
        level++;
        stampa(pippo->left);
        level--;
        printf("%*s %d\n",level*5," ",pippo->data);
        level++;
        stampa(pippo->right);
        level--;
    }  
}

int main()
{
  srand(time(0));
    printf("quanti elementi vuoi inserire?\n");
    int n;
    scanf("%d",&n);
    
    int *a= malloc(sizeof(int)*n);
    
    for(int i = 0; i < n; i++)
    {
        a[i] = rand() % 100+1;
        printf("%d|", a[i]);
    }       
 
       puts("");
       
    /*tlink f = inalbera(a,n);
    stampa(f);  */
}

In teoria quello che chiede l'esercizio è appunto inserire gli elementi dell'array ricorsivamente in modo tale che il primo elemento dell'array coincida con quello della radice dell'albero e questo è evidenziato anche dal quesito posto alla fine. L'idea sarebbe quindi richiamare la funzione ricorsivamente fino ad avere il caso base dove viene creato il link alla radice ,e dopo, cominciare ad inserire in ordine tutti gli elementi dell'array in ordine nell'albero.

6 Risposte

  • Avatar di Weierstrass
    Utente Famoso
    Iscritto da
    feb, 2019
    Messaggi
    2221
    Si ma non hai fatto niente.
    L'albero binario in C c'è su wikipedia - ci metti poco ad adattarlo.
    E se l'array è ordinato non hai più un albero perché procedi ad aggiungere solo da una parte, quindi hai una ...
  • /
    Anonimizzato29386
    Utente anonimizzato
    Si lo so, è una lista concatenata ordinata; ho aggiunto la funzione classica per l'inserimento a quella dell'esercizio, semplicemente volevo sapere se potevo semplificare 
    #include <stdio.h>
#include <stdlib.h>
#include <time.h>


typedef struct tree_
{
   struct tree_* left;
   int data;
   struct tree_* right;
}tnode;
typedef tnode* tlink;

void insert(tlink* treePtr, int value)
{
  if(*treePtr == NULL)
  {
    *treePtr = malloc(sizeof(tnode));
    if(*treePtr)
    {
      (*treePtr)->data = value;
      (*treePtr)->left = NULL;
      (*treePtr)->right = NULL;
    }
    else printf("memoria non disponibile.\n");    
  }
  else
  {
     if(value < (*treePtr)->data)
       insert(&((*treePtr)->left), value);
     else if(value > (*treePtr)->data)
       insert(&((*treePtr)->right), value);
     else printf("%s", "dup");
  }
}

  void inOrder(tlink treePtr) 
{
  if (treePtr) 
  { 
    
    inOrder(treePtr->left);         
    printf("%5d", treePtr->data);     
    inOrder(treePtr->right);    
    
  }                           
} 

void stampa(tlink pippo) 
{
  static int level = 0;
  if (pippo) 
  {
    level++;
    stampa(pippo->right);         
    printf(">%*s%5d\n", level*5, "", pippo->data);      
    stampa(pippo->left);
    level--;
  }                           
} 



tlink inalbera(int * array, unsigned int n)
{
  if(n == 0)
  {
    tlink t = NULL;
    
    return t;
  }
    tlink t = inalbera(array, n - 1);
    insert(&t, array[n -1]);
    return t;
}

int main(void) 
{  
  
  srand(time(NULL)); 
  unsigned int n = rand()% 20 + 1;
  int* a = malloc(sizeof(int)*n);
  for(size_t i = 0; i < n; i++)
  {
     a[i] = 10 + i;
    printf("%d|", a[i]);
  }
  tlink f = inalbera(a, n);
  puts("\nInOrder:\n");
  inOrder(f);
  puts("\n");
  stampa(f);
}
  • Avatar di Weierstrass
    Utente Famoso
    Iscritto da
    feb, 2019
    Messaggi
    2221
    Va bene così, il codice è chiaro

    Puoi anche scrivere 
    
tlink inalbera(int * array, unsigned int n)
{
  if(!n)
    return NULL;
    Ma è proprio un dettaglio
  • /
    Anonimizzato29386
    Utente anonimizzato
    Ma ben venga anche se è solo per un dettaglio; grazie comunque
  • Utente Attivo
    Iscritto da
    apr, 2020
    Messaggi
    86
    Perdonami curiosavo un po sul forum e sto leggendo il tuo codice, per quanto riguarda l'algoritmo ricorsivo, secondo quale stringa di codice inserisce effettivamente nella tua lista i vari elementi, forse mi è sfuggita questa cosa
  • /
    Anonimizzato29386
    Utente anonimizzato
    Nella funzione "inalbera" viene inizializzato l'albero quando arriva al caso base e successivamente inserisce i vari elementi dell'array con la funzione "insert".
Devi accedere o registrarti per scrivere nel forum
6 risposte