[C] Alberi Binari

[LukeSky]

Ho un problema con una procedura di sbilanciamento per alberi binari.

Devo realizzare una funzione che riceve in input un albero binario di ricerca in cui a ciascun nodo è associato un valore intero.
La funzione deve restituire in output un nuovo albero binario di ricerca con lo sbilanciamento massimo; cioè con soli discendenti destri.

Il codice che ho scritto è il seguente:

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

typedef struct btree_tag{
int value;
struct btree_tag *left;
struct btree_tag *right;
}btree;

void sbilancia(btree* *new_root, btree *btp){

if(btp!=NULL){

sbilancia(new_root,btp->left);

if(*new_root){
(*new_root)->right=(btree*)malloc(sizeof(btree));
*new_root=(*new_root)->right;
}else (*new_root)=(btree*)malloc(sizeof(btree));

(*new_root)->value=btp->value;
(*new_root)->left=NULL;
(*new_root)->right=NULL;

sbilancia(new_root,btp->right);
}
}

void insert(btree* *btpp, int x){
while(*btpp!=NULL)
if((*btpp)->value>x)btpp=&((*btpp)->left);
else btpp=&((*btpp)->right);

*btpp=(btree*)malloc(sizeof(btree));
(*btpp)->value=x;
(*btpp)->left=NULL;
(*btpp)->right=NULL;
}

void visita(btree *pnodo){
if(pnodo){
printf("%d ",pnodo->value);
visita(pnodo->left);
visita(pnodo->right);
}
}

void main(){

btree *albero=NULL;
btree *nuovo=NULL;
/* VALORI NODI ALBERO */
int valnodi[9]={35,23,40,10,28,37,48,25,26};
int i;

for(i=0;i<9;i++)insert(&albero,valnodi[i]);

printf("\n\n");
sbilancia(&nuovo,albero);
visita(nuovo);

getch();

}

eseguendo questo codice ottengo solo la visualizzazione del valore 48 mentre dovrei ottenere la visualizzazione della successione:
10 -> 23 -> 25 -> 26 -> 28 -> 35 -> 37 -> 40 -> 48 (cioè tutti i valori dei nodi destri del nuovo albero).

Dove sbaglio?
Io credo ci sia un problema nel valore di ritorno di new_root, ma non sono sicuro.
Forse sbaglio a richiamare la funzione???
Sapete come aiutarmi????

[andr3a]

forse mettendo
visita(nuovo);
dentro l' else di sbilancia, else che non esiste, potresti risolvere, cosi' come e' ora non c'e' alcuna ricorsione o loop per stampare tutti valori

[LukeSky]

ma io non voglio inserire nessuna funzione di stampa dentro sbilancia.
Vorrei che questa funzione ritornasse un albero completamente sbilanciato da poter visitare ed utilizzare a mio piacimento.

ma non riesco a capire come mai non mi riesce.

[LukeSky]

up.

Per favore aiutatemi!!!!!

[pprllo]

Allora. E' sufficiente (ed anche molto più elegante) che fai così:

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

typedef struct btree_tag{ 
int value; 
struct btree_tag *left; 
struct btree_tag *right; 
}btree; 

void insert(btree* *btpp, int x)
{ 
	while(*btpp!=NULL) 
		if((*btpp)->value>x)btpp=&((*btpp)->left); 
		else btpp=&((*btpp)->right); 

	*btpp=(btree*)malloc(sizeof(btree)); 
	(*btpp)->value=x; 
	(*btpp)->left=NULL; 
	(*btpp)->right=NULL; 
} 

void sbilancia(btree* *new_root, btree *btp)
{ 
	if(btp!=NULL)
	{
		sbilancia(new_root,btp->left);
	
		insert(new_root, btp->value); 

		sbilancia(new_root,btp->right); 
	} 
} 

void visita(btree *pnodo)
{ 
	if(pnodo)
	{ 
		printf("%d ",pnodo->value); 
		visita(pnodo->left); 
		visita(pnodo->right); 
	} 
} 

void main(){ 

btree *albero=NULL; 
btree *nuovo=NULL; 
/* VALORI NODI ALBERO */ 
int valnodi[9]={35,23,40,10,28,37,48,25,26};

int i; 

for(i=0;i<9;i++)insert(&albero,valnodi[i]); 

printf("\n\n"); 
sbilancia(&nuovo,albero); 
visita(nuovo); 

getch();
 
}

Riutilizzi la funzione insert(). Infatti poichè i valori che tu gli passi sono, per la natura stessa dell'albero, crescenti, il risultato sarà un albero sbilanciato a destra.

In alternativa:

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

typedef struct btree_tag{ 
int value; 
struct btree_tag *left; 
struct btree_tag *right; 
}btree; 

void sbilancia(btree* *new_root, btree *btp)
{ 
	if(btp!=NULL)
	{ 
		sbilancia(new_root,btp->left); 

		while(*new_root) new_root=&((*new_root)->right);
		(*new_root)=(btree*)malloc(sizeof(btree));

		(*new_root)->value=btp->value; 
		(*new_root)->left=NULL; 
		(*new_root)->right=NULL; 

		sbilancia(new_root,btp->right); 
	} 
} 

void insert(btree* *btpp, int x)
{ 
	while(*btpp!=NULL) 
		if((*btpp)->value>x)btpp=&((*btpp)->left); 
		else btpp=&((*btpp)->right); 

	*btpp=(btree*)malloc(sizeof(btree)); 
	(*btpp)->value=x; 
	(*btpp)->left=NULL; 
	(*btpp)->right=NULL; 
} 

void visita(btree *pnodo)
{ 
	if(pnodo)
	{ 
		printf("%d ",pnodo->value); 
		visita(pnodo->left); 
		visita(pnodo->right); 
	} 
} 

void main()
{ 
	btree *albero=NULL; 
	btree *nuovo=NULL; 
	/* VALORI NODI ALBERO */ 
	int valnodi[9]={35,23,40,10,28,37,48,25,26};

	int i; 

	for(i=0;i<9;i++)insert(&albero,valnodi[i]); 

	printf("\n\n"); 
	sbilancia(&nuovo,albero); 
	visita(nuovo); 

	getch(); 
}

Questo qui invece non usa la funzione insert().
Comunque l'errore consisteva nel fatto che, poichè nella ricorsione dereferenziavi il puntatore new_root, praticamente ti spostavi lungo l'albero (andando sempre verso destra) mentre immettevi i valori, per cui alla fine la tua "root" puntava all'ultimo elemento dell'albero.

[LukeSky]

ti ringrazio ma io volevo sapere come mai quel codice non andava.
Mi spiego meglio, a scuola hanno dato questa esercitazione ed il professore ha proiettato la soluzione che io ho utilizzato nel codice che ho riportato.
In verità il prof ha proiettato solamente la funzione sbilancia; ma probabilemente nella sua soluzione c'è qualcosa che non và e volevo capire cos'era in modo da farglielo notare.
E poi volevo correggere l'errore senza stravolgere troppo il codice.

[pprllo]

Originariamente inviato da LukeSky
ti ringrazio ma io volevo sapere come mai quel codice non andava.
Mi spiego meglio, a scuola hanno dato questa esercitazione ed il professore ha proiettato la soluzione che io ho utilizzato nel codice che ho riportato.
In verità il prof ha proiettato solamente la funzione sbilancia; ma probabilemente nella sua soluzione c'è qualcosa che non và e volevo capire cos'era in modo da farglielo notare.
E poi volevo correggere l'errore senza stravolgere troppo il codice.

Ho modificato.
Comunque per capire meglio ti invito a notare questa differenza:

Qui, nella funzione insert, è fatto bene, il puntatore non viene dereferenziato:

btpp=&((*btpp)->right)

Qui invece il puntatore viene dereferenziato e quindi si sposta lungo l'albero:

*new_root=(*new_root)->right;

Comunque tieni presente che il codice che hai postato tu lo CREA l'albero, solo che altera il puntatore che gli passi tra i parametri. Ma se potessi leggere la "root" dell'albero, l'albero c'è.

[LukeSky]

e come faccio a risalire all'indirizzo di root???

[pprllo]

Mmm ... Per come è scritta quella funzione (dico quella che hai scritto in origine) si basa proprio sul fatto che il puntatore viene alterato durante la ricorsione. Dovresti avere un modo per "risalire" l'albero. Magari includere un puntatore *parent nella struct btree (che tra l'altro è utile in generale, quando si usano gli alberi).

[LukeSky]

ok grazie.

cmq il codice che mi hai mandato tu funziona, userò quello.