[C++] Verificare se un albero binario è bilanciato

[adp]

ciao ragazzi, mi occorrerebbe una gentileza, dovrei controllare se un albero binario è bilanciato, qualcuno mi puo' autare???
grazie

[GliderKite]

Puoi provare con una funzione ricorsiva, ogni volta che arrivi ad una foglia verifichi che l'altezza attuale sia pari alla precedente, se non è cosi l'albero non è bilanciato, altrimenti ripeti per tutte le foglie restanti.

[lolide]

Fai un ciclo con il quale scorri il lato destro ed il lato sinistro, tenendo 2 contatori che incrementi ad ogni ciclo e due bool con cui vedi se un lato è finito o no.
Quando il ciclo finisce, se i due contatori sono diversi, l'albero non è bilanciato.

Oltre alla funzione ricorsiva consigliata da GliderKite (un po' + complessa ma + pulita)

[adp]

io avevo fatto in questo modo:

public static <E> boolean bilanciato(BinaryTree<E> T){
	if(T.isEmpty())
		throw new EmptyTreeException("albero vuoto");
	if(isProper(T,T.root())) 
			return true;
	else
		return false;
			}
public static <E> boolean isProper(BinaryTree<E>T, Position<E>nodo){
	if((T.hasLeft(nodo) && T.hasRight(nodo)))
		return true; 
	if(T.isInternal(nodo)){
		for(Position<E> child:T.children(nodo))
			if(isProper(T,child))
				return true;
	}
		return false;	
}
}

ma resituisce sempre e solo true!!

[GliderKite]

Non l'ho testata, quindi non ti posso dare garanzie certe, ma il concetto base di quello che ti proponevo è questo:

bool balanced( const node_t *root, int height, const int h_temp )
{
	if( root == NULL )
	{
		if( !height )
			height = h_temp;
			
		else if( height != h_temp )
			return false;
			
		return true;
	}
	
	if( balanced(root->left, height, h_temp+1) )
		return balanced( root->right, height, h_temp+1 );
		
	return false;
}


// La chiami come:
balanced( root, 0, -1 );

Come vedi la funzione è molto semplice

[gaten]

Scusami, mi fai capire cosa fai qui:


if( balanced(root->left, height, h_temp+1) )

???