Questo era il codice sui Binary Search Tree che ho ancora dalla triennale... forse ti è utile. Per avere un array con numeri casuali bisogna semlicemente sostituire array[i] con la funzione rand.

codice:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct node{
	int value;
	struct node *leftChild;
	struct node *rightChild;
	}*root = NULL;


struct node *findMin(struct node *);
struct node *findMax(struct node *);
struct node *leftRotation(struct node *);
struct node *rightRotation(struct node *);
struct node *search(struct node *, int);
struct node *searchRicorsivo(struct node *, int);
void add(struct node **, int);
void addPathfinder (struct node *, int);
void delete(struct node **, struct node *, int);
void newNode(struct node **, int);
void traverse(struct node *);
void visit(struct node *);


void main(){

	int i, array[] = {5, 3, 7, 2, 4, 8};

/*			  5
			 / \
			3    7
		    /   \ /
	   	   2    4 8		*/

	srand(time(NULL));
	for(i = 0; i < 6; i++){
		add(&root, array[i]);
	}

	traverse(root);
}


void traverse(struct node *node){

	if(node == NULL)
		return;

	traverse(node->leftChild);
	traverse(node->rightChild);
	visit(node);
}


void visit(struct node *node){

	printf("%d\n", node->value);
}


//Ritorna un puntatore all'elemento piu piccolo (il child piu a sinistra senza child sinistro)
struct node *findMin(struct node *node){

	if(node == NULL)
		return NULL;
	else
		return((node->leftChild != NULL) ? findMin(node->leftChild) : node);
}


//Ritorna un puntatore all'elemento piu grande (il child piu a destra senza child destro)
struct node *findMax(struct node *node){

	if(node == NULL)
		return NULL;
	else
		return((node->rightChild != NULL) ? findMax(node->rightChild) : node);
}


//Ricerca iterativa: in caso positivo ritorna un puntatore all'elemento cercato
struct node *search(struct node *node, int x){

	if(node == NULL)
		return(NULL);

	else if(node->value == x)
		return(node);

	else if (node->value > x)
		return (search(node->leftChild, x));

	else
		return(search(node->rightChild, x));
}


//Ricerca ricorsiva
struct node *searchRicorsivo(struct node *node, int x){

	while((node != NULL) && (node->value != x)){
		if(node->value > x)
			node = node->leftChild;
		else
			node = node->rightChild;
		}

return(node);
}



void add(struct node **node, int x) {

	if((*node) == NULL)
		newNode(node, x);
	else
		addPathfinder(*node, x);
}


void newNode(struct node **node, int x){

	if(!((*node) = malloc(sizeof(struct node))))
		abort();
	(*node)->leftChild = NULL;
	(*node)->rightChild = NULL;
	(*node)->value = x;
}


void addPathfinder (struct node *node, int x) {

	if(x < node->value){
		if(node->leftChild != NULL)
			addPathfinder(node->leftChild, x);
		else
			newNode(&(node->leftChild), x);
		}
	else{
		if(node->rightChild != NULL)
			addPathfinder(node->rightChild, x);
		else
			newNode(&(node->rightChild), x);
		}
}


void delete(struct node **father, struct node *tree, int x){

	if(tree->value != x){
		if(x < tree->value)
			delete(&(tree->leftChild), tree->leftChild, x);
		else
			delete(&(tree->rightChild), tree->rightChild, x);
		}

	else{
		if((tree->leftChild == NULL) && (tree->rightChild == NULL)){	// il nodo e' una foglia
			*father = NULL;
			free(tree);
			}
		else if(tree->leftChild == NULL){		// il nodo ha solo il figlio di destra
			*father = tree->rightChild;
			free(tree);
			}
		else if(tree->rightChild == NULL){		// il nodo ha solo il figlio di sinistra
			*father = tree->leftChild;
			free(tree);
			}
		else{ 													// il nodo ha due figli
			tree->value = (findMax(tree->leftChild))->value;
			delete(&(tree->leftChild),
			tree->leftChild,
			tree->value);
			}
		}
}


struct node *rightRotation(struct node *node){

	struct node *temp = node->leftChild;
	node->leftChild = temp->rightChild;
	temp->rightChild = node;

return temp;
}


struct node *leftRotation(struct node *node){

	struct node *temp = node->rightChild;
	node->rightChild = temp->leftChild;
	temp->leftChild = node;

return temp;
}