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

Question

我有以下类型：

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

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

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

如何读取10另一个函数中具有值的叶子？

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) = ...