4

Java ライブラリから受け取ったツリー構造があります。ツリーの「キー」値のみに関心があるため、フラット化しようとしています。ツリーは、次のクラスの 0 個以上で構成されます。

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

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

于 2015-09-06T10:08:01.450 に答える
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 に答える