Scrivete un programma che:
n1
e n2
, con n1 < n2
;n1
e n2
inclusi 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.
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
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
#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;
}