scala - 如何递归解析这种树状结构？

Question

考虑具有以下节点定义的树状数据结构 -

Node(id:Int, parent: Int, name:Option[String])

我有一个列表[Node]，其中具有相同父节点的节点 n 可以具有相同的 id。我想创建一个新的 List[Node]，以便每个 Node 都有一个唯一的 id。把每个节点的id和parent重写一下，形成输出列表就可以了。我不需要确切的代码，只需要一些提示来编写递归解决方案

示例 -

输入 - 列表(节点(5, 0, "a"), 节点(2, 5,"b"), 节点(2, 5, "c"), 节点(3,5, "d"), 节点(4, 3,"e"))

输出 - List(Node(1, 0, "a"), Node(2, 1, "b"), Node(3, 1, "c"), Node(4, 1, "d"), 节点(5, 4, "e"))

Answer 1

因此，在知道父节点的新 id 之前，我们无法对任何子节点重新编号。这不是一项简单的任务。

case class Node(id:Int, parent: Int, name:String)

def renum(in   :List[Node]
         ,seen :Map[Int,Int] = Map(0 -> 0)
         ,acc  :List[Node]   = Nil
         ,hold :List[Node]   = Nil) :List[Node] = in match {
  case Nil =>                                            //are we done?
    if (hold.isEmpty) acc.reverse else renum(hold, seen, acc)
  case Node(id,par,nm) :: ns if seen.isDefinedAt(par) => //parent was processed
    val newId = acc.size + 1
    renum(ns, seen+(id->newId), Node(newId,seen(par),nm)::acc, hold)
  case n :: ns =>                                        //put node on hold
    renum(ns, seen, acc, n::hold)
}

测试:

/*
     a 
   / | \
   b c d
       |
       e
*/
val input = List(Node(5,0,"a"),Node(2,5,"b"),Node(2,5,"c"), Node(3,5,"d"),Node(4,3,"e"))

renum(util.Random.shuffle(input))
renum(util.Random.shuffle(input))
renum(util.Random.shuffle(input))
renum(util.Random.shuffle(input))
renum(util.Random.shuffle(input))
//res0: List[Node] = List(Node(1,0,a), Node(2,1,c), Node(3,1,b), Node(4,1,d), Node(5,4,e))
//res1: List[Node] = List(Node(1,0,a), Node(2,1,b), Node(3,1,d), Node(4,1,c), Node(5,3,e))
//res2: List[Node] = List(Node(1,0,a), Node(2,1,b), Node(3,1,d), Node(4,3,e), Node(5,1,c))
//res3: List[Node] = List(Node(1,0,a), Node(2,1,b), Node(3,1,c), Node(4,1,d), Node(5,4,e))
//res4: List[Node] = List(Node(1,0,a), Node(2,1,b), Node(3,1,c), Node(4,1,d), Node(5,4,e))