algorithm - 树中的最大元素

Question

我在 Scala 中有以下 ADT 实现。

如何找到树中的最大元素？我可以引入一些辅助函数吗？如果可以，那么如何引入？

abstract class MySet {
  def max: Int

  def contains(tweet: Tweet): Boolean = false
}

class Empty extends MySet {
  def max: throw new NoSuchElementExeption("max called on empty tree")

  def contains(x: Int): Boolean =
    if (x < elem) left.contains(x)
    else if (elem < x) right.contains(x)
    else true
}

class Node(elem: Int, left: MySet, right: MySet) extends Set {
  def max: { ... }

  def contains(x: Int): Boolean =
    if (x < elem) left.contains(x)
    else if (elem < x) right.contains(x)
    else true
}

我在 Haskell 中找到了一个感觉非常直观的解决方案，我能以某种方式将它转换为 Scala 吗？

data Tree a = Nil | Node a (Tree a) (Tree a)
maxElement Nil = error "maxElement called on empty tree"
maxElement (Node x Nil Nil) = x
maxElement (Node x Nil r) = max x (maxElement r)
maxElement (Node x l Nil) = max x (maxElement l)
maxElement (Node x l r) = maximum [x, maxElement l, maxElement r]

更新

我对在 Scala 中复制 Haskell 代码不感兴趣，相反我认为 Haskell 版本更直观，但因为 this 关键字和面向对象语言中的其他内容。如何在没有模式匹配的情况下以面向对象的风格编写等效代码？

Answer 1

您的树是异构的，这意味着每个节点可以是具有值的完整节点，也可以是空叶。因此你需要区分哪个是哪个，否则你可以在空节点上调用 max。有很多方法:

经典 OOP:

abstract class MySet {
  def isEmpty: Boolean
  ...
}

class Empty extends MySet {
  def isEmpty = true
  ...
}

class Node(...) extends MySet {
  def isEmpty = false
  ...
}

所以你做这样的事情:

var maxElem = elem
if(!left.isEmpty)
  maxElem = maxElem.max(left.max)
end
if(!right.isEmpty)
  maxElem = maxElem.max(right.max)
end

由于 JVM 在运行时有类信息，因此您可以跳过 isEmpty 的定义:

var maxElem = elem
if(left.isInstanceOf[Node])
  maxElem = maxElem.max(left.asInstanceOf[Node].max)
end
if(left.isInstanceOf[Node])
  maxElem = maxElem.max(right.asInstanceOf[Node].max)
end

(如果您在 MySet 中定义了 max，则不需要 asInstanceOf，但此模式涵盖了您没有定义的情况)

好吧，Scala 为后者提供了一个语法糖，毫不奇怪，它就是模式匹配:

var maxElem = elem
left match {
  case node: Node =>
    maxElem = maxElem.max(node.max)
  case _ =>
}
right match {
  case node: Node =>
    maxElem = maxElem.max(node.max)
  case _ =>
}
maxElem

你可以更进一步，写这样的东西:

def max = (left, right) match {
  case (_: Empty, _: Empty) => elem
  case (_: Empty, node: Node)  => elem.max(node.max)
  case (node: Node, _: Empty)  => elem.max(node.max)
  case (leftNode: Node, rightNode: Node)  =>
    elem.max(leftNode.max).max(rightNode.max)
}