[C con Clase] Método recursivo en árbol que retorna valor de verdad

Steven Davidson srd4121 en njit.edu
Mar Sep 11 18:36:28 CEST 2012


Hola User,

On 9/11/2012 11:32 AM, User wrote:
> Hola,
>
> Estoy tratando de hacer un método recursivo que recorra un árbol y
> retorne el valor de verdad 'true' si al menos hay un nodo en ese
> árbol que tenga la propiedad azul (blue). No he sido capaz de hacerlo
> de otra manera que no fuera utilizando un miembro de clase, el
> m_hasBlue. Me gustaría poder implementar este método sin necesidad de
> recurir a un miembro de clase. ¿Me echáis una mano?
>
> Este es mi código:
>
> bool myClass::existsBlue()
> {
>    myClass *object = 0;
>    while(m_children.next())
> {
> object =  m_children.first();
> if (object && object->isBlue())
> {
> m_hasBlue = true;
> break;
> }
> else
> {
> m_hasBlue = object->existsBlue();
> }
> }
> return m_hasBlue;
> }
>

La verdad es que vas por buen camino. Si no quieres usar un dato 
miembro, entonces pásalo a este ámbito local de la función recursiva. 
Por ejemplo,

bool myClass::existsBlue()
{
   bool bEsAzul = false;

   myClass *object = 0;
   while( m_children.next() )
   ...
}

Aquí usaríamos 'bEsAzul' en lugar de 'm_hasBlue'.

El único problema que veo es que no terminas el bucle 'while' en cuanto 
hayas encontrado "azul". Esto se puede corregir en la condición del 
bucle así,

bool myClass::existsBlue()
{
   bool bEsAzul = false;

   myClass *object = 0;
   while( !bEsAzul && m_children.next() )
   ...
}

que se leería: "mientras que no sea azul y el siguiente hijo exista, haz 
...".

Podríamos optimizar un poco más el código eliminando el uso de 'break', 
que no lo recomiendo para salir de los bucles. De hecho, podemos 
eliminar el uso de 'bEsAzul' y retornar de inmediato en cuanto sepamos 
si es azul o no.

Otra alternativa es tratando la información en el árbol como una lista 
(o array), para recorrerla linealmente en busca de "azul". El recorrido 
puede ser iterativa o recursiva.


Espero que esto te ayude.

Steven






Más información sobre la lista de distribución Cconclase