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

[cicchi27]

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:

#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?

[vict85]

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.

[cicchi27]

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.

[vict85]

Puoi usare una "pila" oppure, come nel codice da te postato, puoi usare delle funzioni ricorsive (usando quindi la pila delle chiamate di funzioni).