[C] Inserimento degli elementi di un BST attraversato per livello in un array

Messaggioda Cicchi27 » 30/06/2020, 14:39

Salve vorrei qualche chiarimento su un esercizio: è richiesto, dato un BST, l'inserimento dei suoi elementi all'interno di un array.
Questo è il codice per l'inserimento e la stampa classici che ho preso da degli appunti:
Codice:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct treeNode
{
  struct treeNode *left;
  int data;
  struct treeNode *right; 
};

typedef struct treeNode Tree;
typedef Tree *Treeptr;

void treeInit(Treeptr root)
{
  root = NULL;
}

void insert(Treeptr *tree, int value)
{
  if (*tree == NULL)
  {
    *tree = malloc(sizeof(Tree));
    if (*tree != NULL)
   {
      (*tree)->data = value;
      (*tree)->left = NULL;
      (*tree)->right = NULL;
    }
    else printf("No memory available.\n");
  }
  else
  {
    if (value < (*tree)->data)
      insert(&((*tree)->left), value);
    else if (value > (*tree)->data)
      insert(&((*tree)->right), value);
    else printf("%s", "(cut)");
  }
}

void print(Treeptr tree, int level) {
  if (tree != NULL)
  {
    level++;
    print(tree->right, level);         
    printf(">%*s%5d\n", level*5, "", tree->data);     
    print(tree->left, level);
    level--;
  }         
 
}

int main()


  Treeptr root;
  treeInit(root);
  srand(time(NULL));
  puts("");
 printf("Numero massimo di elementi: \n\n");
 unsigned int N;
 scanf("%u", &N);


  for (unsigned int i = 0; i < N; ++i)
  {
    int value = rand() % 250;
    printf("%5d", value);
    insert(&root, value);
  }
 
  puts("\n\n\n");
  print(root, 0);
}

La funzione dovrebbe avere un prototipo di questo tipo: int* fun(Treeptr* root); .
L'idea era innanzitutto era contare il numero di nodi generati che non sarà sempre uguale ad N poiché non possono esserci duplicati nell'albero, quindi creare un array dinamicamente formato dalle N celle, e infine attraversare il BST per livelli(in modo simile a quello che succede nella funzione print), cioè inserire prima i nodi padre di ogni nodo e poi i figli partendo da quello più a sinistra. Ultimo dubbio riguarda il ritorno dell'array(come *int in in questo caso). Qualche idea per come cominciare?
Cicchi27
Starting Member
Starting Member
 
Messaggio: 32 di 33
Iscritto il: 01/03/2020, 10:11

Re: [C] Inserimento degli elementi di un BST attraversato per livello in un array

Messaggioda vict85 » 01/07/2020, 13:46

Ma per aggiungere in un array non dovresti usare una ricerca in profondità? Insomma, il root va aggiunto dopo aver aggiunto tutti gli elementi nell'albero a sinistra.
vict85
Moderatore
Moderatore
 
Messaggio: 10147 di 10156
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: [C] Inserimento degli elementi di un BST attraversato per livello in un array

Messaggioda Cicchi27 » 01/07/2020, 14:17

Si effettivamente faceva confondere il nome root nel prototipo: int* (Treeptr* tree). Comunque il dubbio è proprio quello dell'array: come conto il numero di elementi da inserire nell'array di volta in volta? Ricordo di aver visto da qualche parte l'utilizzo di una coda per l'attraversamento per livelli.
Cicchi27
Starting Member
Starting Member
 
Messaggio: 33 di 33
Iscritto il: 01/03/2020, 10:11

Re: [C] Inserimento degli elementi di un BST attraversato per livello in un array

Messaggioda vict85 » 01/07/2020, 14:41

Puoi usare una "pila" oppure, come nel codice da te postato, puoi usare delle funzioni ricorsive (usando quindi la pila delle chiamate di funzioni).
vict85
Moderatore
Moderatore
 
Messaggio: 10149 di 10156
Iscritto il: 16/01/2008, 00:13
Località: Berlin


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 10 ospiti