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?