[C] alberi binari

[ferra03]

Buona sera a tutti devo fare un'esercizio su un'albero binario ed ho un problema con una funzione ricorsiva(almeno credo che il problema sia quello) vi scrivo il testo dell'esercizio e il mio codice:

testo:Scrivete un programma che:
1. generi a caso una sequenza di interi (di lunghezza massima fissata con una opportuna macro) e la memorizzi in un
array;
2. costruisca un albero binario a partire dall’array (come descritto in seguito);
3. stampi l’albero nella reppresentazione a sommario (come descritta in seguito);
4. stampi i nodi dell’albero negli ordini determinati rispettivamente dalle visite in preordine, inordine e postordine.

Nel codice seguente non prendo in considerazione il punto 3:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 10

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

typedef struct bit_node *Bit_node;

/*bit_left restituisce il figlio sinistro di un nodo p*/
Bit_node bit_left(Bit_node p){
	if(p){
		return(p->l);
	}
	return NULL;
}

/*analogamente bit_right*/
Bit_node bit_right(Bit_node p){
	if(p){
		return(p->r);
	}
	return NULL;
}

/*bit_new crea spazio per un nuovo nodo*/
Bit_node bit_new (int item){
	Bit_node new;
	
	new=malloc(sizeof(struct bit_node));
	
	if(new == NULL){
		printf("\nMemoria Esaurita\n");
		exit(EXIT_FAILURE);
	}
	new->item=item;
	new->l= NULL;
	new->r=NULL;
	return new;
}

/*printnode stampa un nodo*/
void printnode(Bit_node p){
	printf("%d ",p->item);
}

/*Attraversamento in ordine anticipato (preorder): prima la radice, poi il
sottoalbero di sinistra, inne il sottoalbero di destra:*/
void bit_preorder(Bit_node p){
	if(p){
		printnode(p);
		bit_preorder(p->l);
		bit_preorder(p->r);
	}
}

/*Attraversamento in ordine simmetrico (inorder): prima il sottoalbero di
sinistra, poi la radice, inne il sottoalbero di destra*/
void bit_inorder(Bit_node p){
	if(p){
		bit_inorder(p->l);
		printnode(p);
		bit_inorder(p->r);
	}
}

/*Attraversamento in ordine dierito (postorder): prima il sottoalbero di
sinistra, poi il sottoalbero di destra, inne la radice*/
void bit_postorder(Bit_node p){
	if(p){
		bit_postorder(p->l);
		bit_postorder(p->r);
		printnode(p);
	}	
}

/*bit_arr2tree(la probabile causa dei miei problemi)dato un array a di lunghezza size ed un indice j, costruisce
ricorsivamente l'albero binario (completo)

- con radice contenente l'Item a[0]
- e tale che valga la seguente proprietà: se un nodo è etichettato con
a[i], allora il suo figlio sinistro è etichettato con a[2*i+1] e il suo
fglio destro è etichettato con a[2*i+2]*/
Bit_node bit_arr2tree(int a[], int size, int j){
Bit_node root=bit_new(a[j]);
	if(j < size){
		root -> l = bit_arr2tree(a, size, 2*j+1);
		root -> r = bit_arr2tree(a, size, 2*j+2);
	}
	return root;
}

/*MAIN*/
int main(void){

	int array[N];
	int i;
	Bit_node root;

	srand(time(NULL));


	/*generazione array di numeri casuali da 1 a 100*/
	for(i=0; i<N; i++) {
		array[i]=rand()%100+1;
	}

	/*stampo l'array*/
	printf("\nARRAY:\n");

	for(i=0; i<N; i++) {
		printf("%d \n", array[i]);
	}

	printf("\n");
	/*creazione albero*/
	root=bit_arr2tree(array, N, 0);

	bit_inorder(root);

	return 0;
}

Il problema è che la chiamata bit_inorder(root) non viene eseguita correttamente, ma vengono stampati numeri a casaccio.

[YuYevon]

È sbagliato in controllo che fai in bit_arr2tree(), non basta scrivere "j < size" perché se ad esempio (nel tuo caso) j fosse 7 e size 10, il controllo risulterebbe vero ma poi con le successive due chiamate ricorsive andresti ad aggiungere inesistenti elementi dell'array di indice 7*2+1 = 15 e 7*2+2 = 16.

Questo dovrebbe andare.

Bit_node bit_arr2tree(int a[], int size, int j)
{
	Bit_node root = bit_new(a[j]);
        int left = 2*j + 1, right = 2*j + 2;

	if( left < size ) {
		root -> l = bit_arr2tree(a, size, left);
	}

	if ( right < size ) {
		root -> r = bit_arr2tree(a, size, right);
	}

	return root;
}

[ferra03]

grazi mille adesso va! !!! però sinceramente non ho ancora capito bene l'errore, potresti rispiegarmelo?

[YuYevon]

Non c'è molto da capire. Segui l'incremento dell'indice j per ogni chiamata ricorsiva nel programma originario e vedrai che, ad un certo punto, arrivi ad avere valori superiori a 9, accedendo quindi a elementi inesistenti dell'array 'a' che ha solo 10 componenti (ammettendo quindi 9 come indice massimo).

Passo-passo: inzialmente j vale 0 ( così lo passi da main() ), risulta minore di size (che è 10) e quindi avviene la prima chiamata ricorsiva con j = 1, questo perché 0*2 + 1 = 1. Nella seconda esecuzione della funzione, j (1) risulta ancora minore di size e quindi avviene un ulteriore chiamata ricorsiva, stavolta passando alla funzione il valore 3 (1*2 + 1). Con j = 3 il predicato del controllo if risulta ancora vero (essendo 3 minore di 10) e avviene un'altra chiamata ricorsiva con 7. 7 è ancora minore di 10, quindi ennesima chiamata ricorsiva con valore di j pari a 15, e qui sta il problema perché con 15 nella funzione vai a creare un nodo che abbia come valore appunto il 15° elemento dell'array di input, che non esiste in quanto questi ha solo 10 elementi. Ovviamente in memoria c'è comunque qualcosa, ma quel qualcosa non rientra nei limiti del tuo array e appare quindi come "valore sporco" quando vai a stampare l'albero (in realtà se avessi sforato di molto con ogni probabilità avresti ottenuto anche un accesso illegale alla memoria con conseguente crash del programma).
Ragionamento analogo vale per le chiamate ricorsive per i nodi figli di destra, alla fine ottieni un overflow di indice in quanto j arriva a 16 su un massimo di 9.

Impostando quei controlli, invece, hai la garanzia che il valore limite 9 non sarà mai superato.

[ferra03]

ok grazie mille ho capito!