如何获取树状自定义对象的大小

Question

我正在尝试弄清楚如何获取以这种方式定义的自定义树状数据结构的大小（"levels" 的数量）：

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

Answer 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

希望对您有所帮助！

如何获取树状自定义对象的大小

How to get a size of a tree-like custom object

size

scala

foldleft