树中的最大元素

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

完全公开，我自己仍在学习 Scala，但这是我想出的两个版本（模式匹配看起来像是 Haskell 代码的公平翻译）

sealed trait Tree {
  def max: Int
  def maxMatch: Int
}
case object EmptyTree extends Tree {
  def max = 0
  def maxMatch = 0
}
case class Node(data:Int,
                left:Tree = EmptyTree,
                right:Tree = EmptyTree) extends Tree {

  def max:Int = {
    data
      .max(left.max)
      .max(right.max)
  }

  def maxMatch: Int = {
    this match {
      case Node(x,EmptyTree,EmptyTree) => x
      case Node(x,l:Node,EmptyTree) => x max l.maxMatch
      case Node(x,EmptyTree,r:Node) => x max r.maxMatch
      case Node(x,l:Node,r:Node) => x max (l.maxMatch max r.maxMatch)
    }
  }
}

测试（全部通过）

val simpleNode = Node(3)
assert(simpleNode.max == 3)
assert(simpleNode.maxMatch == 3)

val leftLeaf = Node(1, Node(5))
assert(leftLeaf.max == 5)
assert(leftLeaf.maxMatch == 5)


val leftLeafMaxRoot = Node(5, 
                        EmptyTree, Node(2))
assert(leftLeafMaxRoot.max == 5)
assert(leftLeafMaxRoot.maxMatch == 5)

val nestedRightTree = Node(1, 
                         EmptyTree, 
                         Node(2, 
                             EmptyTree, Node(3)))
assert(nestedRightTree.max == 3)
assert(nestedRightTree.maxMatch == 3)

val partialFullTree = Node(1, 
                         Node(2, 
                             Node(4)),
                         Node(3, 
                              Node(6, Node(7))))
assert(partialFullTree.max == 7)
assert(partialFullTree.maxMatch == 7)

Answer 2

如果您不想使用模式匹配，则需要实施 isEmpty 操作或等效操作，以避免在空集上调用 max。

重要的是树的组织方式。基于 contains 的实现，看起来您有一个有序树（"binary search tree"），其中左侧部分中的每个元素都小于或等于右侧部分中的每个元素。如果是这样，你的问题就很简单了。要么右子树为空且当前元素为max，要么树的max元素为右子树的max。这应该是一个简单的递归实现，不需要任何花哨的东西。

Answer 3

您的树是异构的，这意味着每个节点可以是具有值的完整节点，也可以是空叶。因此你需要区分哪个是哪个，否则你可以在空节点上调用 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 在运行时有 class 信息你可以跳过 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)
}

树中的最大元素

Maximum element in a tree

algorithm

scala

recursion

recursive-datastructures