Как получить размер древовидного объекта - PullRequest
Новая
       27

Как получить размер древовидного объекта

2 голосов
/ 28 марта 2020

Я пытаюсь выяснить, как получить размер (число «уровней») пользовательской древовидной структуры данных, определенной следующим образом: 

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

Как вы можете видеть, она реализует * Интерфейс 1004 * (черта на самом деле), который имеет метод 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:

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

out: PrefixTreeImpl(None,Map(one -> PrefixTreeImpl(None,Map(two -> PrefixTreeImpl(Some(12),Map(tree -> PrefixTreeImpl(Some(123),Map())))))))

1 Ответ

1 голос
/ 28 марта 2020

Это можно сделать рекурсивно следующим образом: 

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

Надеюсь, это поможет !

...