se magari vuoi darci un'okkiata... questo è quello che scrissi al tempo dell'esame di Algoritmi.
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;
}
edit: il disegno dell'albero fa un po skifo