0

estoy con un ejercicio en python donde pide averiguar si dos arboles binarios son isomorfos (estructuras iguales). La verdad que estoy confundido y no tengo idea como averiguar la estructura de cada árbol. Osea, cuantos nodos padres, cuantos hijos, etc, para realizar la comparación. Muchas gracias!!

class Arbol:  
   def __init__(self, valor = None):
        if valor != None:
            self.valor = valor
        else: 
            self.valor = None
        self.derecho = None
        self.izquierdo = None
        
        
    def Agregar(self, carga):
        if self.valor:
            if carga < self.valor:
                if self.izquierdo is None:
                    self.izquierdo = Arbol(carga)
                else:
                    self.izquierdo.Agregar(carga)
                
            elif carga > self.valor:
                if self.derecho is None:
                    self.derecho = Arbol(carga)
                else:
                    self.derecho.Agregar(carga)        
        else:
            self.valor = carga
            
    
    def Imprimir(self):
        if self.izquierdo:
            self.izquierdo.Imprimir()
        
        print(self.valor)

        if self.derecho: 
            self.derecho.Imprimir()

arbol1 = Arbol(12)
for i in range(7):
    num = random.randint(0,25)
    print("numero: ",num)
    arbol1.Agregar(num)
print("Ascendente:")
arbol1.Imprimir()

arbol2 = Arbol('k')
lstAbecedario = [
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 
    'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
    'w', 'x', 'y', 'z']
for x in range(7):
    letra = lstAbecedario[random.randint(0,25)]
    print("letra: ", letra)
    arbol2.Agregar(letra)
print("Ascendente:")
arbol2.Imprimir()

arbol1 contiene numero cargados de manera aleatoria y arbol2 letras cargadas aleatoria de acuerdo a la lista lstAbecedario. Necesito saber si ambos tienen la misma estructura.

3
  • no podemos ayudarte si no muestras lo que has intentado
    – Christian
    Commented el 21 nov. 2021 a las 23:35
  • Creo que a tu pregunta le falta algo mas de desarrollo consulta Como preguntar
    – rpaillao
    Commented el 21 nov. 2021 a las 23:41
  • Gracias por responde. Ahí agregue el código, a ver si se entiende un poco mejor. Commented el 22 nov. 2021 a las 0:21

1 respuesta 1

0

Python tiene métodos mágicos. Cuando quieres ejecutar una acción con un objeto, Python busca métodos especiales (mágicos) en la definición de la clase.

Por ejemplo, cuando Python necesita la representación en caracteres de una objeto, internamente llama al método __str__ del objeto.

Si lo deseas, puedes implementar estos métodos en tu clase, reemplazando la implementación por default de cada uno.

Si queremos comparar un objeto de clase Arbol con otro de igual clase y ver si son iguales, sólo necesitas agregar la función __eq__(self, other), que será llamada cada vez comparemos un objeto Arbol contra cualquiera otra cosa.

Como se haga la comparación es cosa nuestra, y para estos propósito voy a definir que dos árboles son iguales si tienen la misma estructura (no mismo contenido necesariamente).

Mi comparación será recursiva. En cada invocación examinare:

  1. Ambos derechos contienen algo o None.
  2. Ambos izquierdos contienen algo o None.
  3. Los sub-árboles derecho son iguales (vía llamada recursiva).
  4. Los sub-árboles izquierdos son iguales (vía llamada recursiva).

Si falla cualquiera de estas condiciones, los árboles no tienen la misma estructura.

El nuevo método de la clase es:

def __eq__(self, other):        
    iguales = False
    if self.derecho:
        if other.derecho:
            if self.izquierdo:
                if other.izquierdo:
                    iguales = True
            elif not other.izquierdo:
                iguales = True
    elif not other.derecho:
        iguales = True

    if iguales:
        iguales = self.derecho == other.derecho and self.izquierdo == other.izquierdo

    return iguales

Demo

arbolA = Arbol(1)
arbolA.derecho = Arbol(2)
arbolA.izquierdo = Arbol(3)

arbolB = Arbol(4)
arbolB.derecho = Arbol(5)
arbolB.izquierdo = Arbol(6)

if arbolA == arbolB:
    print("1. iguales")
else:
    print("2. distintos")

arbolA.derecho.derecho = Arbol(7)

if arbolA == arbolB:
    print("3. iguales")
else:
    print("4. distintos")

produce:

1. iguales
4. distintos

Process finished with exit code 0
1
  • Muchísimas gracias por tu repuesta! En realidad, como el ejercicio corresponde a un curso de aprendizaje, consiste en no aplicar ningún método especial. Me imagino que habrá que descifrar si son iguales o no por medio del recorrido. Investigue algo sobre el recorrido por niveles y guardar el contenido de los nodos en un vector, pero no lo tengo muy en claro. Abrazo! Commented el 22 nov. 2021 a las 14:36

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.