計數層狀結構

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