Scala - 树形结构扁平化

Question

我从一个Java库中接收到了一棵树形结构。由于我只对树的“key”值感兴趣，因此我正在尝试将其展平。该树由以下零个或多个类组成：

class R(val key: String, val nodes: java.util.List[R]) {}

使用空的节点列表表示分支的结束。可以通过以下代码构建示例：

val sample =  List[R](
  new R("1",  List[R](
    new R("2",  List[R]().asJava),
    new R("3",  List[R](new R("4",  List[R]().asJava))
      .asJava)).asJava)).asJava

我在编写一个正确和高效的方法时遇到了困难。目前我的代码如下：

def flattenTree(tree: List[R]): List[String] = {
  tree.foldLeft(List[String]())((acc, x) => 
             x.key :: flattenTree(x.nodes.asScala.toList))
}

然而，尽管这段代码可能效率低下，但当我运行它时，结果仍然是错误的。我的结果如下：

>>> flattenTree(sample.asScala.toList)
res0: List[String] = List(1, 3, 4)

这意味着由于某种原因，我丢失了键为“2”的节点。

有人能推荐一种正确且更高效的方法来展开这棵树吗？

- Will I Am

Answer 1

您在每次调用时未能添加累积的键。请尝试以下操作：

def flattenTree(tree: List[R]): List[String] = {
  tree.foldLeft(List[String]())((acc, x) =>
             x.key :: flattenTree(x.nodes.asScala.toList) ++ acc)
}

这段代码生成的结果是：List(1, 3, 4, 2)，如果正确的排序很重要：

def flattenTree(tree: List[R]): List[String] = {
  tree.foldLeft(List[String]())((acc, x) =>
             acc ++ (x.key :: flattenTree(x.nodes.asScala.toList)))
}

生成结果为：List(1, 2, 3, 4)

- Shadowlands

---

谢谢，这让我克服了困难。我可以继续下去，希望以后有人能提出更好的做法建议。 - Will I Am

Answer 2

您可以使用flatMap定义一个函数来展平R对象：

// required to be able to use flatMap on java.util.List
import scala.collection.JavaConversions._

def flatten(r: R): Seq[String] = {
  r.key +: r.nodes.flatMap(flatten)
}

还有一个函数可以将这些序列扁平化：

def flattenSeq(l: Seq[R]): Seq[String] = l flatMap flatten

r.nodes.flatMap(flatten) 是一个 Buffer，因此在其前面插入元素不是高效的。这会导致二次复杂度。因此，如果顺序不重要，附加元素更有效:def flatten(r: R): Seq[String] = r.nodes.flatMap(flatten) :+ r.key

- Kolmar

---

我不确定，也许我是某种东西，但是孩子们是java.util.List，它们不支持flatMap。我需要再次进行转换为asJava吗？因此，flatten的主体将变为“r.key +：r.nodes.asScala.toSeq.flatMap（flatten3）”？ - Will I Am

@WillIAm 噢，抱歉，我忘记在我的答案中包含导入。 - Kolmar

谢谢！这JavaConversions._ 与 JavaConverters._ 真的很令人困惑。:) 我用的是后者。 - Will I Am

Answer 3

将每个R转换为Scalaz Tree，并调用flatten进行先序遍历。

import scala.collection.JavaConversions._
import scalaz._

def rTree(r: R): Tree[String] =
  Tree.node(r.key, r.nodes.toStream.map(rTree))

sample.flatMap(r => rTree(r).flatten): Seq[String]
// List(1, 2, 3, 4)

编辑：不幸的是，由于scalaz中的一个错误在7.1.1版本中，这会导致宽树的堆栈溢出。

- Chris Martin

---

嗯，我尝试了你的建议并将我的节点增加到了10000个，但最终出现了堆栈溢出（在1000和10000之间）。与上面的代码唯一的更改是将List[String]更改为Seq[String]以使编译器满意。我本来打算采用这种方法，因为它似乎比Kolmar上面建议的方法快一些。http://pastebin.com/BbCEm4H4 - Will I Am

堆栈溢出似乎是scalaz中的一个错误 :( - Chris Martin

Answer 4

使用像scalaz一样的Stream怎么样：

def flatten(rootElem: R): Stream[String] = {
  def flatten0(elem: R, xs: Stream[String]): Stream[String] =
    Stream.cons(elem.key, elem.nodes.foldLeft(xs)((acc, x) => flatten0(x, acc)))

  flatten0(rootElem, Stream.empty)
}

- Alexandr Nikitin