Foro de elhacker.net

Hola, estoy con problemas para comparar 2 arboles binarios, al intentar compararlos, deberia devolverme 0 si son iguales, 1 si son distintos, pero el programa solo me devuelve el lado de la derecha y no compara la izq, espero puedan ayudarme

int iguales(arbol *a, arbol *b){
        if(a == NULL && b ==NULL){
		return 0;
	} else {
		if(a == NULL || b == NULL){
			return 1;
		} else {
			if(a->dato == b->dato){
				iguales(a->izq, b->izq);
				iguales(a->der, b->der);
			} else {
				return 1;
			}
		}
	}
}
 

Cuando tengas una duda o problema con alguno de tus programas por favor indica el lenguaje de programación. En el caso de C ...

Lo usual es devolver verdadero (un valor distinto de cero, usualmente uno) si se cumple la condición y falso (cero) en caso contrario.

Eso sucede porque falta retornar el valor en el caso de que ambos nodos sean diferentes de NULL y con igual valor:

if (a->dato == b->dato){ /* <== No hay valor de retorno en esta rama de ejecucion */
   iguales(a->izq, b->izq);
   iguales(a->der, b->der);
} else {
   return 1;
}

Por ultimo se pueden ahorrar algunas comparaciones. Por ejemplo (retornando verdadero si son iguales):

struct nodo {
   int valor;
 
   struct nodo *izq;
   struct nodo *der;
};
 
/* ... */
 
int equ(struct nodo *p, struct nodo *q)
{
   if (p != NULL && q != NULL && p->valor == q->valor)
      return equ(p->izq, q->izq) && equ(p->der, q->der);
   else 
      return p == q;
}

Un saludo

Muchas Gracias (por todas las las aclaraciones) :)

Los valores de retorno de cada "iguales" no se guardan en ningún lugar.

if(!iguales(...) && !iguales(...)) ...

¡Buenas!

Si por iguales te refieres a que tienen la misma estructura y los mismos datos en los mismos nodos solo te falta comprobar, como ya te han dicho, si las comparaciones en las distintas ramas te devuelven 0 o 1, y si alguna devuelve 1 ya no tienes que seguir comparando, solo tienes que devolver este valor.

En cambio, si por iguales entendemos que aunque la estructura es distinta tienen los mismos datos, tu código no es correcto. Imagina el nodo raíz con valores distintos, de dos árboles con los mismos datos pero con distinta estructura. Cuando llegues a

    if (a->dato == b->dato){ /* <== No hay valor de retorno en esta rama de ejecucion */
      iguales(a->izq, b->izq);
      iguales(a->der, b->der);
    } else {
      return 1;
    }
 

a->dato != b->dato, ya que aunque los valores almacenados son los mismos, los valores de los nodos raíz son distintos. Por lo tanto la función devolverá 1 a pesar de que debería devolver 0.

Tampoco puedes asegurar que los nodos hoja sean los mismos, ya que has podido introducir los datos en distinto orden y por lo tanto ocuparán posiciones distintas dentro del árbol.

Lo que tienes que hacer es un recorrido inorden de cada uno de los dos árboles e ir comparando los valores de los nodos.

¡Saludos!