Altura de un árbol binario
El árbol binario
|
1 2 3 4 5 6 |
· / \ / \ · · / \ / \ 1 4 6 9 |
se puede representar por
|
1 2 |
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
|
1 |
altura :: Arbol a -> Int |
tal que altura t es la altura del árbol t. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
λ> 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.
|
1 2 3 4 5 6 |
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) |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
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 |