2

我试图弄清楚如何获得以这种方式定义的自定义树状数据结构的大小（“级别”数）：

case class PrefixTreeImpl[K, +V](value: Option[V], prefixTree: Map[K, PrefixTree[K, V]]) extends PrefixTree[K, V]

如您所见，它实现了PrefixTree接口（实际上是特征），其中包含一个size()方法：

def size: Int

我正在尝试使用 foldLeft() Scala 方法来实现它，但我真的不明白它如何与这种复杂的数据结构一起工作到目前为止，我想出了这个并卡住了：

override def size: Int = {
  if (prefixTree.isEmpty) 0
  else
    prefixTree.foldLeft(0) {(z, Map[K, PrefixTree[K, V]]()) => z + 1}

}

显然它没有编译，但我还想不出别的东西。

DS 的工作方式是：

在：scala>val tree2 = tree1.put(List("one", "two"), 12)

出去：PrefixTreeImpl(None,Map(one -> PrefixTreeImpl(None,Map(two -> PrefixTreeImpl(Some(12),Map(tree -> PrefixTreeImpl(Some(123),Map())))))))

4

1 回答 1

1

它可以通过以下方式递归完成：

override def size: Int = {
  if(prefixTree.nonEmpty) prefixTree.values.map(_.size + 1).max else 0
}

所以接下来的测试：

val tree = PrefixTreeImpl(None ,Map("one" -> PrefixTreeImpl(None, Map("two" -> PrefixTreeImpl(Some(12),Map("tree" -> PrefixTreeImpl(Some(123), Map.empty[String, PrefixTree[String, Int]])))))))
    println(tree.size)

产生结果：3

希望这可以帮助！

于 2020-03-28T18:33:44.590 回答