4

我有一个从 Java 库接收的树结构。我试图将其展平，因为我只对树的“关键”值感兴趣。树由以下零个或多个类组成：

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”的节点。

有人可以推荐一种正确且更有效的方法来展平这棵树吗？

4

4 回答 4

4

您无法在每次连续调用中添加累积的密钥。尝试以下操作：

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)

于 2015-09-06T08:21:22.023 回答
4

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

// 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)是 a Buffer，所以在它前面添加是无效的。它变成了二次复杂度。因此，如果顺序不重要，附加更有效：def flatten(r: R): Seq[String] = r.nodes.flatMap(flatten) :+ r.key

于 2015-09-06T10:08:01.450 回答
1

将每个转换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)

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

于 2015-09-06T09:19:42.570 回答
1

使用Streams likescalaz会怎样：

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)
}
于 2015-09-06T13:34:49.687 回答