Salve, come bravo appassionato mi sto studiando gli alberi binari. Dopo un pò di casini
con l'algoritmo per la rimozione di un nodo in un albero binario ordinato ho scritto il mio primo
programma di prova, potete darci un'occhiata tanto per dirmi se c'è qualcosa che non
so?

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
e che ho imparato da wiky...

L'output:
codice:
ALBERO:

                                       5
                             3        <+>        7
                        2   <+>   4         6   <+>   8
                   1   <+                             +>   9

ALBERO DOPO LA RIMOZIONE DI 5, 7 E 1:

                                       6
                             3        <+>        8
                        2   <+>   4              +>   9

RICERCA:
  13 non esiste
  1 non esiste
  12 non esiste
  10 non esiste
  8 è nel nodo: 0x804a0b0.

bash-3.00$