像树结构一样计算树中的图层
我有一个使用Map的树形结构：
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又有2个孩子3和4.在更复杂的情况下，节点可以有多个父母，但所有这些都是独特的，这就是为什么我选择了集合，尽管它可能是任何东西其他，但随着集我很容易地收集所有的父节点向上和所有的孩子向下，我唯一想让他们按居住的级别分组。 在这种情况下，节点3应该具有列表（Set（2），Set（1），Set（0），Set（））作为其父节点。
BFS类遍历
做一个BFS类型的遍历并不断添加nodes到map以纠正水平
BFS保留一个队列（在此代码中使用List作为队列）并逐级访问树/图。 这是我们需要的。
需要注意的一点是如何keep track of end of the level 。 我使用EndOfLevel跟踪关卡的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可以使代码更优化。 Vector append比List更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))))