Tra a e b

Scrivete un programma che:

• legga una sequenza di interi non nulli terminata da 0 (lo 0 non fa parte della sequenza) e li memorizzi in un albero binario di ricerca;
• legga successivamente due interi n1 e n2, con n1 < n2;
• infine sfrutti l'albero binario di ricerca per individuare tutti gli interi della sequenza compresi tra n1 e n2inclusi e stamparli in ordine crescente; questa operazione deve essere svolta in tempo lineare nel numero di interi presenti nell'albero.

Potete partire dal programma riportato in calce, che contiene alcune funzioni per la manipolazione di alberi binari di ricerca contenenti numeri interi. Sarà sufficiente completare la funzione main ed eventualmente scrivere nuove funzioni aggiuntive.

Non potete fare assunzioni sulla lunghezza della sequenza. Potete però assumere che i numeri nella sequenza siano tutti distinti.

Esempio

Eseguendo

./soluzione

avendo nel flusso di ingresso le righe:

1 4 2 5 6 10 20 -5 -1 0
2 6

il programma emette sul flusso di uscita:

2 4 5 6

Esempio

Eseguendo

./soluzione

avendo nel flusso di ingresso le righe:

1 4 2 5 60 10 21 -5 -1 8 7 9 0
-2 20

il programma emette sul flusso di uscita:

-1 1 2 4 5 7 8 9 10

Programma da completare

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


struct bit_node {
  int item;
  struct bit_node *l, *r;
};

typedef struct bit_node *Bit_node;

// prototipi delle funzioni generali su alberi binari
Bit_node bit_new( int item );
void bit_printassummary( Bit_node p, int spaces );

// prototipi delle funzioni su alberi binari di ricerca
int bist_search( Bit_node p, int k );
void bist_insert( Bit_node *r, int item );



/***********************************************************************
INSERIRE QUI LA FUNZIONE MAIN E EVENTUALI ALTRE FUNZIONI AGGIUNTIVE
**********************************************************************/

...

int main( void ){
  ...
  return 0;
}



/*************************************************************
Implementazione delle funzioni generali su alberi binari
***************************************************************/

Bit_node bit_new( int item ) {
  Bit_node new = malloc( sizeof( struct bit_node ) );

  if ( new == NULL ) {
    printf( "err malloc\n" );
    exit(-1);
  }

  new -> l = new -> r = NULL;
  new -> item = item;
  return new;
}


void bit_printassummary( Bit_node p, int spaces ){
  int i;
  for ( i = 0; i < spaces; i++ )
    printf( "  " );
  printf( "*" );
  if (!p)
    printf( "\n" );

  else {
    printf( "%d\n", p -> item );
    if ( p -> l || p -> r ) {
      bit_printassummary( p -> l, spaces + 1 );
      bit_printassummary( p -> r, spaces + 1 );
    }
  }
}


/**************************************************************************
* Implementazione delle funzioni specifiche su alberi binari di ricerca
*************************************************************************/

int bist_search( Bit_node p, int k ) {
  if ( p ) {
    while ( p && ( k != p -> item ) )
      p = k < p -> item ? p -> l : p -> r;
  }
  if ( p == NULL ) return 0; // 0 e' usato come valore speciale (item NULL)
  else return p -> item;
}

// assumo che item non sia già nell'albero
void bist_insert( Bit_node *r, int item ) {
  Bit_node f, p = *r, new = bit_new( item );

  if ( p == NULL ) {
    /* inserisco nell'albero vuoto */
    *r = new;
    return;
  }

  while ( p != NULL ) {
    if ( item < p -> item ) {
      f = p;
      p = p -> l;
    }

    else { // quindi  item > p -> item
      f = p;
      p = p -> r;
    }
  }

/* f e' il padre del nuovo nodo */
  if ( item < f -> item ) {
    f -> l = new;
   }
  else
    f -> r = new;
}