Ir al contenido principal

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