Menu Close

Altura de un árbol binario

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4))
                  (Nodo (Hoja 6) (Hoja 9))

El tipo de los árboles binarios se puede definir por

data Arbol a = Hoja a
| Nodo (Arbol a) (Arbol a)

Definir la función

   altura :: Arbol a -> Int

tal que altura t es la altura del árbol t. Por ejemplo,

   λ> altura (Hoja 1)
   0
   λ> altura (Nodo (Hoja 1) (Hoja 6))
   1
   λ> altura (Nodo (Nodo (Hoja 1) (Hoja 6)) (Hoja 2))
   2
   λ> altura (Nodo (Nodo (Hoja 1) (Hoja 6)) (Nodo (Hoja 2) (Hoja 7)))
   2

Soluciones

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


Soluciones en Haskell

data Arbol a = Hoja a
             | Nodo (Arbol a) (Arbol a)
 
altura :: Arbol a -> Int
altura (Hoja _)   = 0
altura (Nodo i d) = 1 + max (altura i) (altura d)


Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar
 
A = TypeVar("A")
 
@dataclass
class Arbol(Generic[A]):
    pass
 
@dataclass
class Hoja(Arbol[A]):
    x: A
 
@dataclass
class Nodo(Arbol[A]):
    i: Arbol[A]
    d: Arbol[A]
 
def altura(a: Arbol[A]) -> int:
    match a:
        case Hoja(_):
            return 0
        case Nodo(i, d):
            return 1 + max(altura(i), altura(d))
    assert False
Haskell y Python

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.