如何读取 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

是什么？基本上还有两个

Tree

。

考虑一个非常简单的

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

请注意，如果我们不只是谈论二叉树，而是具有严格排序不变性的二叉 search 树，那么所有这一切都会变得容易得多。