scala - 在 Scala 中这个演员表是必要的吗？

Question

假设我有一个简单abstract BinaryTree的子类Node，Leaf并且我想编写一个生成List[Leaf].

def getLeaves(tree: BinaryTree): List[Leaf] =
    tree match {
      case Leaf(v) => List(tree.asInstanceOf[Leaf])
      case Node(left, right) => getLeaves(left) ++ getLeaves(right)
    }

有没有办法避免这种情况下asInstanceOf[Leaf]的显式演员表？如果我忽略它，我会得到一个诊断结果：找到：BinaryTree；需要叶子。Leaf

Answer 1

我在其他地方看到了这个结构。它似乎完成了这项工作。

def getLeaves(tree: BinaryTree): List[Leaf] =
    tree match {
      case leaf: Leaf => List(leaf)
      case Node(left, right) => getLeaves(left) ++ getLeaves(right)
    }

Answer 2

试试这个方法

def getLeaves(tree: BinaryTree): List[Leaf] =
    tree match {
      case x@Leaf(v) => List(x)
      case Node(left, right) => getLeaves(left) ++ getLeaves(right)
    }

另请注意，您的实现在性能方面很糟糕，因为您正在每个 Node.js 中创建一个新列表。

可以这样修复

def genLeaves(tree:BinaryTree) = {
  def getLeaves0(tree: BinaryTree, acc:List[Leaf]): List[Leaf] =
    tree match {
      case x@Leaf(v) => x::acc
      case Node(left, right) => {
         val leftLeaves = getLeaves(left, acc)
         getLeaves(right, leftLeaves)
         }
    }
  getLeaves0(tree).reverse
}

在这里，您将重用所有已收集的项目，并且在遍历期间您将只分配一个列表。您在遍历它们时正在收集其中的元素，因此您最终会以相反的顺序得到叶子（列表作为 LIFO 工作），因此要按照您访问它的顺序获取元素，我们需要反转结果列表。

Answer 3

您可以利用您已经解构tree到的事实Leaf(v)，并重建叶子：

def getLeaves(tree: BinaryTree): List[Leaf] =
    tree match {
        case Leaf(v) => List(Leav(v))
        case Node(left, right) => getLeaves(left) ++ getLeaves(right)
    }