PDA

Visualizza la versione completa : [C++] Verificare se un albero binario bilanciato


adp
23-02-2011, 23:06
ciao ragazzi, mi occorrerebbe una gentileza, dovrei controllare se un albero binario bilanciato, qualcuno mi puo' autare???
grazie

GliderKite
23-02-2011, 23:14
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
23-02-2011, 23:15
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
23-02-2011, 23:31
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
24-02-2011, 11:00
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
01-07-2011, 16:56
Scusami, mi fai capire cosa fai qui:


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

???

Loading