如何读取 Haskell 中的二叉树中的内容？

Question

我有以下类型：

data Tree = Branch (Tree) (Tree) | Leaf Int deriving(Show)

现在我想创建一个函数来给出树中最高值的叶子。但是我被卡住了，因为我不知道如何获得给定树的后两棵树。

例如我有一棵树 a 看起来像这样：let a = Branch (Leaf 10) (Leaf 2)

如何在另一个函数中读取值为 10 的 Leaf？

Answer 1

一个典型的骨架是这样的：

maxTree :: Tree -> Int
maxTree (Branch x y) = {- TODO -}
maxTree (Leaf n) = {- TODO -}

Answer 2

处理递归时，您需要记住一个基本情况。

对于：

data Tree = Branch (Tree) (Tree) | Leaf Int deriving(Show)

您的基本情况是 Leaf Int。一片叶子的最大值是……那片叶子持有的价值。

maxTree :: Tree -> Int
maxTree (Leaf n) = n

现在，你如何处理Branch？什么是和 Branch？基本上是两个 Trees.

考虑一个非常简单的Tree:

   Branch
    /  \
   /    \
  /      \
Leaf 1   Leaf 4

最大值显然是4。为什么？因为右分支的 maxTree 计算量大于左分支的 maxTree 计算量。

考虑一个更复杂的问题 Tree:

   Branch
    /  \
   /    \
  /      \
Leaf 1   Branch
          / \
         /   \
        /     \
     Branch   Leaf 8
      / \
     /   \
    /     \
  Leaf 3  Leaf 9

答案显然是9。我们怎么知道呢？那么，maxTree 告诉我们 Leaf 1 的最大值是 1。每个Branch的最大值是通过求出左右分支的最大值来计算的。如果我们在每个 Branch 上递归调用 maxTree，最终我们会将 3 与 9 进行比较。显然 9 更大。现在我们比较 9 和 8。 9 又变大了。然后9到1，9又赢了。

现在您只需要将其转换为代码。

maxTree :: Tree -> Int
maxTree (Leaf n) = n
maxTree (Branch left right) = ...

如何读取 Haskell 中的二叉树中的内容？

How do I read what's in a binaryTree in Haskell?

recursion

haskell

pattern-matching