Árboles con igual estructura

PorJosé A. Alonso 29-diciembre-202226-diciembre-2022

Los árboles binarios con valores en las hojas y en los nodos se definen por

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
     deriving Show

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

Por ejemplo, los árboles

        5              8             5           5
       / \            / \           / \         / \
      /   \          /   \         /   \       /   \
     9     7        9     3       9     2     4     7
    / \   / \      / \   / \     / \               / \
   1   4 6   8    1   4 6   2   1   4             6   2

5 8 5 5

/ \ / \ / \ / \

9 7 9 3 9 2 4 7

/ \ / \ / \ / \ / \ / \

1 4 6 8 1 4 6 2 1 4 6 2

se pueden representar por

   ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol Int
   ej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))
   ej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N3 3 (H 6) (H 2))
   ej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2)
   ej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2))

ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol Int

ej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))

ej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N3 3 (H 6) (H 2))

ej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2)

ej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2))

Definir la función

   igualEstructura :: Arbol -> Arbol -> Bool

1	igualEstructura :: Arbol -> Arbol -> Bool

tal que igualEstructura a1 a2 se verifica si los árboles a1 y a2 tienen la misma estructura. Por ejemplo,

   igualEstructura ej3arbol1 ej3arbol2 == True
   igualEstructura ej3arbol1 ej3arbol3 == False
   igualEstructura ej3arbol1 ej3arbol4 == False

igualEstructura ej3arbol1 ej3arbol2 == True

igualEstructura ej3arbol1 ej3arbol3 == False

igualEstructura ej3arbol1 ej3arbol4 == False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
  deriving (Show, Eq)

ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol Int
ej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))
ej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N 3 (H 6) (H 2))
ej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2)
ej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2))

igualEstructura :: Arbol a -> Arbol a -> Bool
igualEstructura (H _) (H _)             = True
igualEstructura (N _ i1 d1) (N _ i2 d2) =
  igualEstructura i1 i2 &&
  igualEstructura d1 d2
igualEstructura _ _                       = False

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol Int

ej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))

ej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N 3 (H 6) (H 2))

ej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2)

ej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2))

igualEstructura :: Arbol a -> Arbol a -> Bool

igualEstructura (H _) (H _) = True

igualEstructura (N _ i1 d1) (N _ i2 d2) =

igualEstructura i1 i2 &&

igualEstructura d1 d2

igualEstructura _ _ = False

Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass
class Arbol(Generic[A]):
    pass

@dataclass
class H(Arbol[A]):
    x: A

@dataclass
class N(Arbol[A]):
    x: A
    i: Arbol[A]
    d: Arbol[A]

ej3arbol1: Arbol[int] = N(5, N(9, H(1), H(4)), N(7, H(6), H(8)))
ej3arbol2: Arbol[int] = N(8, N(9, H(1), H(4)), N(3, H(6), H(2)))
ej3arbol3: Arbol[int] = N(5, N(9, H(1), H(4)), H(2))
ej3arbol4: Arbol[int] = N(5, H(4), N(7, H(6), H(2)))

def igualEstructura(a: Arbol[A], b: Arbol[A]) -> bool:
    match (a, b):
        case (H(_), H(_)):
            return True
        case (N(_, i1, d1), N(_, i2, d2)):
            return igualEstructura(i1, i2) and igualEstructura(d1, d2)
        case (_, _):
            return False
    assert False

from dataclasses import dataclass

from typing import Generic, TypeVar

A = TypeVar("A")

@dataclass

class Arbol(Generic[A]):

pass

@dataclass

class H(Arbol[A]):

x: A

@dataclass

class N(Arbol[A]):

x: A

i: Arbol[A]

d: Arbol[A]

ej3arbol1: Arbol[int] = N(5, N(9, H(1), H(4)), N(7, H(6), H(8)))

ej3arbol2: Arbol[int] = N(8, N(9, H(1), H(4)), N(3, H(6), H(2)))

ej3arbol3: Arbol[int] = N(5, N(9, H(1), H(4)), H(2))

ej3arbol4: Arbol[int] = N(5, H(4), N(7, H(6), H(2)))

def igualEstructura(a: Arbol[A], b: Arbol[A]) -> bool:

match (a, b):

case (H(_), H(_)):

return True

case (N(_, i1, d1), N(_, i2, d2)):

return igualEstructura(i1, i2) and igualEstructura(d1, d2)

case (_, _):

return False

assert False

4 Comentarios

Para comparar si dos árboles tienen la misma estructura, podemos definir la función igualEstructura de la siguiente manera:

igualEstructura :: Arbol a -> Arbol a -> Bool
igualEstructura (H _) (H _) = True
igualEstructura (N _ l1 r1) (N _ l2 r2) = igualEstructura l1 l2 && igualEstructura r1 r2
igualEstructura _ _ = False

igualEstructura :: Arbol a -> Arbol a -> Bool

igualEstructura (H _) (H _) = True

igualEstructura (N _ l1 r1) (N _ l2 r2) = igualEstructura l1 l2 && igualEstructura r1 r2

igualEstructura _ _ = False

La función compara si dos árboles son hojas y, en caso contrario, si ambos tienen la misma estructura en sus ramas izquierdas y derechas. Si alguno de los árboles no cumple con alguna de estas condiciones, entonces devuelve False.

Por ejemplo:

igualEstructura ej3arbol1 ej3arbol2
= igualEstructura (N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))) (N 8 (N 9 (H 1) (H 4)) (N3 3 (H 6) (H 2)))
= igualEstructura (N 9 (H 1) (H 4)) (N 9 (H 1) (H 4)) && igualEstructura (N 7 (H 6) (H 8)) (N3 3 (H 6) (H 2))
= True && igualEstructura (N 7 (H 6) (H 8)) (N3 3 (H 6) (H 2))
= True && igualEstructura (H 6) (H 6) && igualEstructura (H 8) (H 2)
= True && True && igualEstructura (H 8) (H 2)
= True && True && True
= True

igualEstructura ej3arbol1 ej3arbol3
= igualEstructura (N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))) (N 5 (N 9 (H 1) (H 4)) (H 2))
= igualEstructura (N 9 (H 1) (H 4)) (N 9 (H 1) (H 4)) && igualEstructura (N 7 (H 6) (H 8)) (H 2)
= True && igualEstructura (N 7 (H 6) (H 8)) (H 2)
= True && False
= False

igualEstructura ej3arbol1 ej3arbol2

= igualEstructura (N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))) (N 8 (N 9 (H 1) (H 4)) (N3 3 (H 6) (H 2)))

= igualEstructura (N 9 (H 1) (H 4)) (N 9 (H 1) (H 4)) && igualEstructura (N 7 (H 6) (H 8)) (N3 3 (H 6) (H 2))

= True && igualEstructura (N 7 (H 6) (H 8)) (N3 3 (H 6) (H 2))

= True && igualEstructura (H 6) (H 6) && igualEstructura (H 8) (H 2)

= True && True && igualEstructura (H 8) (H 2)

= True && True && True

= True

igualEstructura ej3arbol1 ej3arbol3

= igualEstructura (N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))) (N 5 (N 9 (H 1) (H 4)) (H 2))

= igualEstructura (N 9 (H 1) (H 4)) (N 9 (H 1) (H 4)) && igualEstructura (N 7 (H 6) (H 8)) (H 2)

= True && igualEstructura (N 7 (H 6) (H 8)) (H 2)

= True && False

= False

Responder

Here is the same code in Lean:

inductive Arbol (α : Type)
| H : α -> Arbol
| N : α -> Arbol -> Arbol -> Arbol

open Arbol

def ej3arbol1 : Arbol ℤ := N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))
def ej3arbol2 : Arbol ℤ := N 8 (N 9 (H 1) (H 4)) (N 3 (H 6) (H 2))
def ej3arbol3 : Arbol ℤ := N 5 (N 9 (H 1) (H 4)) (H 2)
def ej3arbol4 : Arbol ℤ := N 5 (H 4) (N 7 (H 6) (H 2))

def igualEstructura {α : Type} : Arbol α -> Arbol α -> bool
| (H _) (H _)             := true
| (N _ i1 d1) (N _ i2 d2) := igualEstructura i1 i2 && igualEstructura d1 d2
| _ _                       := false

inductive Arbol (α : Type)

| H : α -> Arbol

| N : α -> Arbol -> Arbol -> Arbol

open Arbol

def ej3arbol1 : Arbol ℤ := N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))

def ej3arbol2 : Arbol ℤ := N 8 (N 9 (H 1) (H 4)) (N 3 (H 6) (H 2))

def ej3arbol3 : Arbol ℤ := N 5 (N 9 (H 1) (H 4)) (H 2)

def ej3arbol4 : Arbol ℤ := N 5 (H 4) (N 7 (H 6) (H 2))

def igualEstructura {α : Type} : Arbol α -> Arbol α -> bool

| (H _) (H _) := true

| (N _ i1 d1) (N _ i2 d2) := igualEstructura i1 i2 && igualEstructura d1 d2

| _ _ := false

Responder

En Isabelle/HOL, podemos definir el tipo Arbol y la función igualEstructura de la siguiente manera:

datatype Arbol = H nat | N nat Arbol Arbol

fun igualEstructura :: "Arbol => Arbol => bool" where
  "igualEstructura (H _) (H _) = True" |
  "igualEstructura (N _ l1 r1) (N _ l2 r2) = igualEstructura l1 l2 && igualEstructura r1 r2" |
  "igualEstructura _ _ = False"

datatype Arbol = H nat | N nat Arbol Arbol

fun igualEstructura :: "Arbol => Arbol => bool" where

"igualEstructura (H _) (H _) = True" |

"igualEstructura (N _ l1 r1) (N _ l2 r2) = igualEstructura l1 l2 && igualEstructura r1 r2" |

"igualEstructura _ _ = False"

Podemos probar la función con los ejemplos que se nos dan:

value "igualEstructura (N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))) (N 8 (N 9 (H 1) (H 4)) (N 3 (H 6) (H 2)))"
value "igualEstructura (N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))) (N 5 (N 9 (H 1) (H 4)) (H 2))"
value "igualEstructura (N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))) (N 5 (H 4) (N 7 (H 6) (H 2)))"

value "igualEstructura (N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))) (N 8 (N 9 (H 1) (H 4)) (N 3 (H 6) (H 2)))"

value "igualEstructura (N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))) (N 5 (N 9 (H 1) (H 4)) (H 2))"

value "igualEstructura (N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))) (N 5 (H 4) (N 7 (H 6) (H 2)))"

Responder

Para escribir la solución en Coq, primero debemos definir el tipo de los árboles binarios con valores en las hojas y en los nodos, tal como se nos proporciona:

Inductive Arbol (A:Type) : Type :=
| H : A -> Arbol A
| N : A -> Arbol A -> Arbol A -> Arbol A.

Inductive Arbol (A:Type) : Type :=

| H : A -> Arbol A

| N : A -> Arbol A -> Arbol A -> Arbol A.

Luego podemos definir la función igualEstructura de la siguiente manera:

Fixpoint igualEstructura (A:Type) (a1 a2 : Arbol A) : bool :=
  match a1, a2 with
  | H _, H _ => true
  | N _ l1 r1, N _ l2 r2 => igualEstructura l1 l2 && igualEstructura r1 r2
  | _, _ => false
  end.

Fixpoint igualEstructura (A:Type) (a1 a2 : Arbol A) : bool :=

match a1, a2 with

| H _, H _ => true

| N _ l1 r1, N _ l2 r2 => igualEstructura l1 l2 && igualEstructura r1 r2

| _, _ => false

end.

Podemos probar la función con los ejemplos que se nos dan, siguiendo la sintaxis de Coq:

Example test_igualEstructura_1 : igualEstructura ej3arbol1 ej3arbol2 = true.
Proof. reflexivity. Qed.

Example test_igualEstructura_2 : igualEstructura ej3arbol1 ej3arbol3 = false.
Proof. reflexivity. Qed.

Example test_igualEstructura_3 : igualEstructura ej3arbol1 ej3arbol4 = false.
Proof. reflexivity. Qed.

Example test_igualEstructura_1 : igualEstructura ej3arbol1 ej3arbol2 = true.

Proof. reflexivity. Qed.

Example test_igualEstructura_2 : igualEstructura ej3arbol1 ej3arbol3 = false.

Proof. reflexivity. Qed.

Example test_igualEstructura_3 : igualEstructura ej3arbol1 ej3arbol4 = false.

Proof. reflexivity. Qed.

Responder

Árboles con igual estructura

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Se puede imprimir o compartir con

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico