Ciao a tutti, sto svolgendo un progetto che consiste in questo: dato un array di interi, non contenente elementi ripetuti, costruire un albero binario di ricerca bilanciato le cui chiavi siano elementi dell'array.
Ora la mia idea è stata quella di ordinare il vettore, prendere l'elemento mediano e metterlo nella radice dell'albero per poi agire ricorsivamente. Il codice sembra però non funzionare correttamente per problemi di allocazione dei nodi, almeno così è secondo me. Qualcuno riesce ad aiutarmi?
Grazie.
PS nell'originale la lista è letta da file ma qui ho inserito un esempio specifico.

codice:
#include <stdio.h>#include <stdlib.h>
typedef struct NODE {
	int key;
	struct NODE *left;
	struct NODE *right;
	struct NODE *up;
} NODE;


int pivot(int *A,int p,int r){
    return p+rand()%(r-p+1);
}
  
void swap(int *A,int i, int j){
     int tmp; 
     tmp=A[i];
     A[i]=A[j];
     A[j]=tmp;
}
  
int partition(int *A,int p,int q,int r){
    int i=p, j=r,pivot;
    swap(A,q,p);
    pivot=A[p];
    while(i<j){
               while(j>p && pivot<=A[j]){
                         j--;
               }
               while(i<r && pivot>A[i]){
                         i++;
               }
               if(i<j){
                       swap(A,i,j);
               }
    }
    swap(A,p,j);
    return j;
} 


void quicksort(int *A,int p,int r){
     if (p<r){
        int q=pivot(A,p,r);
        int i=partition(A,p,q,r);
        quicksort(A,p,i);
        quicksort(A,i+1,r);
     }
}
  


NODE *NodeAlloc(int key) {
	NODE *node = (NODE *)malloc(sizeof(NODE));
	node ->key  = key;
	node ->left = NULL;
	node->right = NULL;
	node->up    = NULL;
	return node;
}


NODE* Alb(int* list, int j, int u){
	int m;
	NODE *nodo;
	if (j<=u){
		m = ((j + u) / 2);
		nodo = NodeAlloc(list[m]);
		nodo->left = Alb(list, j, m - 1);
		nodo->right = Alb(list, m + 1, u);
		return nodo;
	}
	else
		return NULL;


}
NODE *BalancedBST(int *list, int n) {
	NODE *T = NULL;
	int k;


	k = n - 1;
	quicksort(list, 0, k);


	T = Alb(list, 1, n);


	return T;
}


void PreOrderPrint(NODE *T) {
	if(T!=NULL){
                 printf("%d ",T->key);
                 PreOrderPrint(T->left);
                 PreOrderPrint(T->right);
     } 
}


void DeleteBST(NODE *T) {
	if(T!=NULL){
                 DeleteBST(T->left);
                 DeleteBST(T->right);
                 free(T);
     } 
}


int main() {
	int list[]={8, 5, 18, 15, 17, 9, 7, 16},n=8;
	NODE *T;


	
	T = BalancedBST(list,n);
	PreOrderPrint(T);
	DeleteBST(T);
	return 0;
}