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

Question

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

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

希望这会有所帮助！