计数层状结构

Question

我有使用地图树状结构：

val m = Map[Int, (Set[Int], Set[Int])]() 

其中节点ID是通过ID和各组代表分别为节点的家长和孩子。我试图递归计算节点上下的层数。例如，我得到了像（0 - 1 - 2 - （3,4））这样的树，我期待有一些函数返回结果作为集合列表，其中每个集合都是树的图层。我有以下的方法，通过它我正在收集所有的父母

def p(n:Set[Int]):Set[Int] = if(n.isEmpty) Set.empty else n ++ m(n.head)._1 ++ p(n.tail) 

，但我想它通过相应的树的级别进行分组，这样我可以通过它调用尺寸得到期望的结果。

UPD：

m = Map(0 -> (Set(), Set(1), 1 -> (Set(0), Set(2,3)), 2 -> (Set(1), Set(4,5), 3 -> (Set(2), Set(6,7) ....) 

这是怎么了我的地图M可以看起来像树节点填满后，我想从它的另一个地图这可能看起来像：

Map(0 -> (List(Set()), List(Set(1), Set(2,3), Set(4,5,6,7)), 1 -> (List(Set(), Set(0)), List(Set(2,3), Set(4,5,6,7)) ... and so on) 

那是我想要按照每个级别将所有父级图层设置为集合，并将所有子级图层设置为集合。

下面

是简化的例子：

val m = Map(2 -> (Set(1),Set(3, 4)), 4 -> (Set(2),Set()), 1 -> (Set(0),Set(2)), 3 -> (Set(2),Set()), 0 -> (Set(),Set(1))) 

这里是以下结构的树0 - 1 - 2 - 3，4

所以这里0是它有子一个根这在转到有2个孩子3和4的孩子2.在更复杂的情况下，节点可能有多个父母，但所有人都是独特的，这就是为什么我选择了集合，尽管它可以是其他任何东西，但是通过集合，我可以轻松地向上收集所有父节点和所有的孩子向下，我唯一想让他们按居住的层次分组。在这种情况下，节点3应该具有列表（Set（2），Set（1），Set（0），Set（））作为其父节点。

Answer 1

BFS一种穿越

做一个BFS一种穿越的和不断增加nodes到map纠正水平

BFS保持队列（使用List本规范队列）并逐级访问树/图层。这是我们需要的。

重要的一点是要注意的是如何keep track of end of the level。我保持水平导轨端使用EndOfLevel

当你发现EndOfLevel再添EndOfLevel是否有留在队列中，如果不说我们已经完成并返回结果的要素。

sealed trait Node 

    case class ANode(value: Int) extends Node 

    case object EndOfLevel extends Node 


    def bfs(root: Node, map: Map[Node, (Set[Node], Set[Node])]): List[(Int, Set[Node])] = { 

    @tailrec 
    def helper(queue: List[Node], level: Int, result: Map[Int, Set[Node]]): List[(Int, Set[Node])] = { 

     if (queue.nonEmpty) { 

     queue.head match { 
      case anode@ANode(_) => 

      val newQueue = queue.tail ++ getNodes(anode, map) 

      val newResult: Map[Int, Set[Node]] = 
       if (result contains level) { 
       result + (level -> (Set(anode) ++ result(level))) 
       } else { 
       result + (level -> Set(anode)) 
       } 

      helper(newQueue, level, newResult) 

      case EndOfLevel => 

      if (queue.tail.nonEmpty) helper(queue.tail ++ List(EndOfLevel), level + 1, result) else result 

     } 
     } else result 
    } 

    helper(List(root) ++ List(EndOfLevel), 0, Map(0 -> Set.empty[Node])).toList 

    } 

    def getNodes(node: Node, map: Map[Node, (Set[Node], Set[Node])]): Set[Node] = { 
    val (left, right) = map.getOrElse(node, (Set.empty[Node], Set.empty[Node])) 
    left ++ right 
    } 

注意，您可以使用Vector代替List使你的代码更优化..Vectorappend比List

运行代码更好的性能

sealed trait Node 

case class ANode(value: Int) extends Node 

case object EndOfLevel extends Node 

object Main { 

    def bfs(root: Node, map: Map[Node, (Set[Node], Set[Node])]): List[(Int, Set[Node])] = { 
    def helper(queue: List[Node], level: Int, result: Map[Int, Set[Node]]): Map[Int, Set[Node]] = { 
     if (queue.nonEmpty) { 
     queue.head match { 
      case anode@ANode(_) => 
      val newQueue = queue.tail ++ getNodes(anode, map) 
      val newResult: Map[Int, Set[Node]] = 
       if (result contains level) { 
       result + (level -> (Set(anode) ++ result(level))) 
       } else { 
       result + (level -> Set(anode)) 
       } 
      helper(newQueue, level, newResult) 
      case EndOfLevel => 
      if (queue.tail.nonEmpty) helper(queue.tail ++ List(EndOfLevel), level + 1, result) else result 
     } 
     } else result 
    } 
    helper(List(root) ++ List(EndOfLevel), 0, Map(0 -> Set.empty[Node])).toList 
    } 


    def main(args: Array[String]): Unit = { 
    val map: Map[Node, (Set[Node], Set[Node])] = Map(
     ANode(1) -> (Set[Node](ANode(2)) -> Set[Node](ANode(3))), 
     ANode(2) -> (Set[Node](ANode(4)) -> Set[Node](ANode(5))), 
     ANode(3) -> (Set[Node](ANode(6)) -> Set[Node](ANode(7))) 
    ) 
    println(bfs(ANode(1), map)) 

    } 


    def getNodes(node: Node, map: Map[Node, (Set[Node], Set[Node])]): Set[Node] = { 
    val (left, right) = map.getOrElse(node, (Set.empty[Node], Set.empty[Node])) 
    left ++ right 
    } 
} 

输出

List((0,Set(ANode(1))), (1,Set(ANode(3), ANode(2))), (2,Set(ANode(7), ANode(6), ANode(5), ANode(4))))