以功能方式遍历树

Question

我已经在 Scala 中实现了一个基本的可变树，我想以一种函数式的方式遍历它来搜索一个元素，但我不知道如何实现它。如果可能的话，我还希望算法是尾递归的。

树是一个结构，它有一个值和一个也是树的叶子列表。

如有任何帮助，我们将不胜感激。

这是我的代码（关注 getOpt 方法）：

package main

import scala.collection.mutable.ListBuffer

sealed trait Tree[Node] {

  val node: Node

  val parent: Option[Tree[Node]]

  val children: ListBuffer[Tree[Node]]

  def add(n: Node): Tree[Node]

  def size: Int

  def getOpt(p: (Node) => Boolean): Option[Tree[Node]]

  override def toString = {
    s"""[$node${if (children.isEmpty) "" else s", Children: $children"}]"""
  }
}

case class ConcreteTree(override val node: Int) extends Tree[Int] {

  override val children = ListBuffer[Tree[Int]]()

  override val parent: Option[Tree[Int]] = None

  override def add(n: Int): ConcreteTree = {
    val newNode = new ConcreteTree(n) {override val parent: Option[Tree[Int]] = Some(this)}
    children += newNode
    newNode
  }

  override def size: Int = {
    def _size(t: Tree[Int]): Int = {
      1 + t.children.foldLeft(0)((sum, tree) => sum + _size(tree))
    }
    _size(this)
  }

  // This method is not correct
  override def getOpt(p: (Int) => Boolean): Option[Tree[Int]] = {
    def _getOpt(tree: Tree[Int], p: (Int) => Boolean): Option[Tree[Int]] = {
      tree.children.map {
        t =>
          if(p(t.node)) Some(t) else t.children.map(_getOpt(_, p))
      }
    }
  }
}

object Main {

  def main(args: Array[String]) {
    val tree1 = ConcreteTree(1)
    val tree2 = tree1.add(2)
    val tree3 = tree1.add(3)

    println(tree1.getOpt(_ == 2))
  }
}

@doertsch 的回答是我目前最好的方法。

Answer 1

使用方法 exists 和 find（每个 List 提供），您可以实现 "finish when a result is found" 行为。（尽管在内部可能会争论，这些并没有以完全实用的方式实现：https://github.com/scala/scala/blob/5adc400f5ece336f3f5ff19691204975d41e652e/src/library/scala/collection/LinearSeqOptimized.scala#L88）

您的代码可能如下所示：

case class Tree(nodeValue: Long, children: List[Tree]) {

  def containsValue(search: Long): Boolean =
    search == nodeValue || children.exists(_.containsValue(search))

  def findSubTreeWithNodeValue(search: Long): Option[Tree] =
    if (search == nodeValue)
      Some(this)
    else
      children.find(_.containsValue(search)).
        flatMap(_.findSubTreeWithNodeValue(search))
}

在最后两行，find应用程序将return当前节点的正确子树，如果存在的话，flatMap部分将提取正确的子树从中递归，或者如果未找到该值，则保留 None 结果不变。

然而，这个有一个不可爱的特征，即遍历的一部分进行两次，一次用于确定结果是否存在，一次用于从包含它的树中提取它。可能有一种更有效的方法来解决这个问题，但我现在想不出来...

Answer 2

将集合转换为 view 时，所有转换器如 map 都是惰性实现的。这意味着仅根据需要处理元素。这应该可以解决您的问题：

override def getOpt(p: (Int) => Boolean): Option[Tree[Int]] = {
  if (p(node)) Some(this)
  else children.view.map(_.getOpt(p)).find(_.isDefined).getOrElse(None)
}

所以我们正在（懒惰地）映射子节点，将它们变成搜索节点的 Options。随后我们发现第一个这样的 Option 不是 None。 getOrElse(None) 需要 "flatten" 嵌套选项，因为 find returns 是 Option 本身。

我实际上没有运行代码，所以请原谅小错误。但是，一般方法应该已经很清楚了。

Answer 3

我想，您正在寻找这样的东西：

@tailrec
def findInTree[T](value: T, stack: List[Node[T]]): Option[Node[T]] = stack match {
   case Nil => None
   case Node(value) :: _ => stack.headOption
   case head :: tail => findInTree(value, head.children ++ tail)
}

这并没有遍历部分树两次，也是tail-recursive。为了清楚起见，我稍微更改了您的 class 定义，但这是相同的想法。你可以这样称呼它：findInTree(valueToFind, List(root))

Answer 4

我实际上会寻求更灵活的方法并实现一个通用函数来生成扁平化树的惰性流，这样您以后的许多工作就会变得容易得多。像这样：

def traverse[Node](tree: Tree[Node]): Stream[Tree[Node]] = 
  tree #:: (tree.children map traverse).fold(Stream.Empty)(_ ++ _)

然后你的 getOpt 减少到这个：

override def getOpt(p: (Int) => Boolean): Option[Tree[Int]] =
  traverse(tree) find {x => p(x.node)}

进一步简化，如果您只对没有 Tree 结构的数据感兴趣，您可以获得节点流，从而得到：

def nodes[Node](tree: Tree[Node]): Stream[Node] = traverse(tree) map (_.node)

def getNode(p: (Int) => Boolean): Option[Int] = nodes(tree) find p

这为非常简洁和可读的代码打开了其他可能性，例如 nodes(tree) filter (_ > 3)、nodes(tree).sum、nodes(tree) contains 12 和类似的表达式。

以功能方式遍历树

Traverse tree in a functional way

algorithm

tree

functional-programming

scala

data-structures