Gli esercizi

Testi e soluzioni di alcuni esercizi

Alberi binari di ricerca

/*
**  alberiBinariDiRicerca.c
**
**  Implementazione della struttura dati di Albero Binario di Ricerca
**  e degli algoritmi per operare sull'albero:
**   - inserimento di un elemento
**   - ricerca di un elemento
**   - calcolo del predecessore e del successore di un elemento
**   - calcolo del minimo
**   - calcolo del massimo
**   - ordinamento dell'albero
*/

#include <stdlib.h>
#include <stdio.h>

struct nodo {
  int info;
  struct nodo *padre, *sx, *dx;
};

/*
 *  inserisci(r, x)
 *
 *  inserisce un nuovo nodo con valore v nell'albero binario
 *  di ricerca con radice in r.
 */

struct nodo *inserisci(struct nodo *r, int v) {
  struct nodo *x, *y=NULL, *p;

  x = r;
  while (x != NULL) {
    y = x;
    if (x->info > v)
      x = x->sx;
    else
      x = x->dx;
  }

  p = malloc(sizeof(struct nodo));
  p->info  = v;
  p->sx    = NULL;
  p->dx    = NULL;
  p->padre = y;

  if (y == NULL) {
    r = p;
  } else {
    if (y->info > v)
      y->sx = p;
    else
      y->dx = p;
  }
  return r;
}

/*
 *  search(r, x)
 *
 *  cerca l'elemento con valore x nell'albero con radice in r.
 *  Se lo trova restituisce il puntatore a quell'elemento, 
 *  altrimenti restituisce NULL.
 */

struct nodo *search(struct nodo *r, int x) {
  struct nodo *p;
  p = r;
  while (p != NULL && p->info != x) {
    if (p->info > x)
      p = p->sx;
    else
      p = p->dx;
  }
  return p;
}

/*
 *  min(p)
 *
 *  restituisce il puntatore all'elemento di valore minimo 
 *  presente nel sottoalbero con radice in p.
 */

struct nodo *min(struct nodo *p) {
  while (p->sx != NULL)
    p = p->sx;
  return p;
}

/*
 *  max(p)
 *
 *  restituisce il puntatore all'elemento di valore massimo
 *  presente nel sottoalbero con radice in p.
 */

struct nodo *max(struct nodo *p) {
  while (p->dx != NULL)
    p = p->dx;
  return p;
}

/*
 *  predecessore(p)
 *  
 *  restituisce, se esiste, il puntatore all'elemento che
 *  precede p->info nell'ordine crescente degli elementi
 *  presenti nell'albero.
 */

struct nodo *predecessore(struct nodo *p) {
  struct nodo *q;
  if (p->sx != NULL) {
    q = max(p->sx);
  } else {
    while (p->padre != NULL && p != p->padre->dx)
      p = p->padre;
    q = p->padre;
  }
  return q;
}

/*
 *  successore(p)
 *  
 *  restituisce, se esiste, il puntatore all'elemento che
 *  segue p->info nell'ordine crescente degli elementi
 *  presenti nell'albero.
 */

struct nodo *successore(struct nodo *p) {
  struct nodo *q;
  if (p->dx != NULL) {
    q = min(p->dx);
  } else {
    while (p->padre != NULL && p != p->padre->sx)
      p = p->padre;
    q = p->padre;
  }
  return q;
}

/*
 *  sort(p)
 *
 *  visualizza in output in ordine crescente il valore dei
 *  vertici nel sottoalbero con radice in p.
 */

void sort(struct nodo *p) {
  if (p != NULL) {
    sort(p->sx);
    printf("%d ", p->info);
    sort(p->dx);
  }
  return;
}

/*
 *  Funzione principale
 */

int main(void) {
  struct nodo *r = NULL, *p, *q;
  int i, n, x;
  printf("Numero di elementi da inserire nell'albero: ");
  scanf("%d", &n);
  printf("Inserisci %d numeri interi: ", n);
  for (i=0; i<n; i++) {
    scanf("%d", &x);
    r = inserisci(r, x);
  }
  printf("Elemento da cercare nell'albero: ");
  scanf("%d", &x);
  p = search(r, x);
  if (p != NULL) {
    printf("L'elemento %d e' presente nell'albero.\n", x);
    if (p->padre != NULL)
      printf("Il padre di %d e' %d.\n", x, p->padre->info);
    else
      printf("%d e' la radice dell'albero.\n", x);
    if (p->sx != NULL) 
      printf("Il figlio sinistro di %d e' %d.\n", x, p->sx->info);
    if (p->dx != NULL) 
      printf("Il figlio destro di %d e' %d.\n", x, p->dx->info);
    q = predecessore(p);
    if (q != NULL) 
      printf("Il predecessore di %d e' %d.\n", x, q->info);
    else 
      printf("%d non ha un predecessore.\n", x);
    q = successore(p);
    if (q != NULL) 
      printf("Il successore di %d e' %d.\n", x, q->info);
    else 
      printf("%d non ha un successore.\n", x);
  }
  printf("L'elemento minimo dell'albero e' %d.\n", min(r)->info);
  printf("L'elemento massimo dell'albero e' %d.\n", max(r)->info);
  printf("Elementi in ordine crescente: ");
  sort(r);
  printf("\n\n");
  return 0;
}