斯卡拉 - 扁平化树状结构

问题描述：

我从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”。

有人可以推荐一种正确和更有效的扁平化树的方法吗？

答

您可以定义一个函数扁平化的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)是Buffer，所以前面加上它效率不高。它变成二次复杂。所以，如果顺序并不重要的是更有效的方法追加：def flatten(r: R): Seq[String] = r.nodes.flatMap(flatten) :+ r.key

我不确定，也许我是东西，但是孩子们是不支持flatMap的java.util.List。我必须再次转换成Java，所以平坦的身体会变成“r.key +：r.nodes.asScala.toSeq.flatMap（flatten3）”？ –

@WillIAm哦，对不起，我忘记了包括导入到我的回答 – Kolmar

Thanks！这个JavaConversions._ vs JavaConverters._非常混乱。:)我有后者。 –

答

您无法在每次连续呼叫中添加累计密钥。请尝试以下操作：

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)

谢谢，让我渡过了难关。我可以继续，希望稍后有人会提出一个更好的方法来提出这个建议。 –

答

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

编辑：不幸的是，由于a bug in scalaz为7.1.1版本，这将导致宽树木堆栈溢出。

嗯，我尝试了你的建议，并增加了我的节点10000个项目，但我最后堆栈溢出（介于1000和10000之间）。上述代码唯一的变化是将List [String]更改为Seq [String]以使编译器感到满意。我打算采用这种方法，因为它似乎比Kolmar上面提出的方法要快一些。 http://pastebin.com/BbCEm4H4 –

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

答

怎么样使用Stream就像scalaz作用：

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) 
}

斯卡拉 - 扁平化树状结构

相关推荐