codice:
#include <stdlib.h>
#include <stdio.h>
typedef struct bt
{
int value;
struct bt *low;
struct bt *high;
} bt_t;
#define MINOR(P) (P)->low
#define MAJOR(P) (P)->high
#define VALUE(P) (P)->value
/* Crea un nuovo nodo assegnandogli il valore v
* e impostando i nodi figli l e v */
static bt_t * bt_alloc(const int v, bt_t *l, bt_t *h)
{
bt_t *b = (bt_t*) malloc(sizeof(bt_t));
MINOR(b) = l;
MAJOR(b) = h;
VALUE(b) = v;
return b;
}
/* Elimina una albero a partire dal nodo `n' */
static void bt_delete(bt_t *n)
{
if(n == NULL)
return;
if(MINOR(n))
bt_delete(MINOR(n));
if(MAJOR(n))
bt_delete(MAJOR(n));
free(n);
}
/* Posiziona il cursore per la stampa del nodo */
#define MOVETO(L, C) printf("\x1b[%d;%dH", L, C)
/* Stampa l'albero */
static void bt_print(bt_t *node, unsigned int sl, unsigned int sc)
{
static char l = 1;
int line[] = {0, 20, 10, 5, 5, 5};
MOVETO(l + sl, sc);
printf("%d", VALUE(node));
l++;
if(MAJOR(node))
{
MOVETO(l + sl, sc);
printf("+>");
bt_print(MAJOR(node), sl, sc + line[l]);
}
if(MINOR(node))
{
MOVETO(l + sl, sc - 1);
printf("<+");
bt_print(MINOR(node), sl, sc - line[l]);
}
l--;
}
/* Effettua una ricerca in maniera ricorsiva
* restituisce il nodo contenente il valore
* ricercato oppure NULL se il nodo non
* è stato trovato. */
static bt_t * bt_search(bt_t *b, const int v)
{
if(b == NULL)
return b;
return (VALUE(b) == v) ? b : bt_search(VALUE(b) > v ? MINOR(b) : MAJOR(b), v);
}
/* Inserisce un valore nell'albero */
static bt_t * bt_insert(bt_t *b, const int v)
{
if(b == NULL)
return bt_alloc(v, NULL, NULL);
if(v != VALUE(b))
{
bt_t **n = VALUE(b) > v ? &MINOR(b) : &MAJOR(b);
*n = bt_insert(*n, v);
}
return b;
}
static char bt_remove(bt_t *b, const int v)
{
static bt_t *up = NULL;
if(b == NULL)
return 0;
else if(VALUE(b) != v)
{
up = b;
return bt_remove(VALUE(b) > v ? MINOR(b) : MAJOR(b), v);
}
else
/* Trovato il nodo da eliminare */
{
/* Nessun figlio. Elimina il nodo e
* il collegamento dal padre */
if(!MINOR(b) && !MAJOR(b))
{
bt_t **f;
if(up)
{
f = MAJOR(up) == b ? &MAJOR(up) : &MINOR(up);
*f = NULL;
}
free(b);
return 1;
}
/* 1 figlio */
else if(!MINOR(b) || !MAJOR(b))
{
bt_t **f;
if(up)
{
f = MAJOR(up) == b ? &MAJOR(up) : &MINOR(up);
*f = MINOR(b) ? MINOR(b) : MAJOR(b);
}
free(b);
return 1;
}
/* 2 figli */
else
{
bt_t *x;
for(x = MAJOR(b); MINOR(x) != NULL; )
x = MINOR(x);
VALUE(b) = VALUE(x);
VALUE(x) = v;
up = b;
return bt_remove(MAJOR(b), v);
}
}
return 0;
}
int main(int argc, char **argv, char **argp)
{
bt_t *top;
bt_t *found;
int val;
unsigned int i;
/* Primo nodo */
top = bt_insert(NULL, 5);
/* Inserimento */
bt_insert(top, 7);
bt_insert(top, 3);
bt_insert(top, 4);
bt_insert(top, 6);
bt_insert(top, 2);
bt_insert(top, 8);
bt_insert(top, 1);
bt_insert(top, 9);
/* Stampa */
printf("\033[2J");
MOVETO(1, 1);
printf("ALBERO:\n");
bt_print(top, 2, 40);
bt_remove(top, 5);
bt_remove(top, 7);
bt_remove(top, 1);
MOVETO(8, 1);
printf("ALBERO DOPO LA RIMOZIONE DI 5, 7 E 1:\n");
bt_print(top, 9, 40);
MOVETO(14, 1);
printf("RICERCA:\n");
/* Ricerca */
for(i = 0; i < 5; i++)
{
val = rand() % 15;
found = bt_search(top, val);
if(found)
printf(" %d è nel nodo: %p.\n", val, found);
else
printf(" %d non esiste\n", val);
}
/* Elimina la lista */
bt_delete(top);
return EXIT_SUCCESS;
}
L'output è corretto, solo che vorrei sapere se ci sono algoritmi migliori di quelli che ho usato io
Rispondi quotando
