[C] Creazione di un albero binario di ricerca da array non ordinato

[Paul90]

ciao ragazzi,
non riesco trovare una soluzione a questo programma che dato un array non ordinato mi metta gli elementi in un ABR.
esempio:

array----> 10 5 40 23 8 56 2 17 13->null


albero deve essere:


10
5 40
2 8 23 56
17 13


posto qui il mio codice (SBAGLIATO)

node *crea(int a[],int i,int x,int *flag){
node *radice=NULL;
node *aux;
if((*flag)==0){ radice=creanodo(NULL,NULL,a[0]);
(*flag)=(*flag) +1;
}
if(i>MAX) return NULL;
else{
if(radice==NULL) {aux=creanodo(NULL,NULL,a[i]);return aux;}
else{
if((a[i]>a[i+1])&&((i+1)<MAX)) radice->sx=crea(a,i+1,x,flag);
else if((a[i]<a[i+1])&&((i+1)<MAX)) radice->dx=crea(a,i+1,x,flag);
return radice;
}

}
}

chiamata al main:

radice=crea(a,i+1,&x);

//per la dimensione dell'array ho fatto una define che uso dentro la funzione : MAX.
//L'output e' sbagliato dato che non sono riuscito a fare una funzione giusta
//Grazie in anticipo dell'aiuto.

[infinitejustice]

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.

#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;
}