如何隱蔽清單樹沒有堆棧溢出

Question

我有一個問題，列表[（節點ID，的parentID）] - >樹結構

val tree: List[(Int, Int)] = List((1,0),(2,0),(3,0),(4,1),(5,4),(6,2),(7,6)) 

我的樹案例類

case class Tree(value: Int, subTree: List[Tree]) 

我代碼

def DFS(tree: List[(Int, Int)], id: Int): List[Tree] = { 
    if(tree.isEmpty) Nil 
    else List(Tree(id, tree.filter(x => x._2 == id).flatMap(x => DFS(tree, x._1))))} 

結果

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

，我發現在名單

大數據堆棧溢出，所以我想將其更改爲尾遞歸，映射或摺疊

Answer 1

有很多從性能的角度來看，提高，但它似乎工作：

val tree: List[(Int, Int)] = List((1,0),(2,0),(3,0),(4,1),(5,4),(6,2),(7,6)) 
case class Tree(value: Int, subTree: List[Tree]) 

// Sort in reverse BFS order 
@annotation.tailrec 
def BFS(tree: List[(Int, Int)], ids: List[(Int, Int)], acc: List[(Int, Int)]): List[(Int, Int)] = { 
    ids match { 
    case Nil => acc 
    case head::tail => 
     BFS(tree, tail ++ tree.filter(_._2 == head._1), head::acc) 
    } 
} 

// acc: List of (parent, Tree) 
@annotation.tailrec 
def fold(bfs: List[(Int, Int)], acc: List[(Int, Tree)]): List[(Int, Tree)] = { 
    bfs match { 
    case Nil => acc 
    case head::tail => 
     val (l, r) = acc.partition(_._1 == head._1) 
     fold(tail, (head._2, Tree(head._1, l.map(_._2))) :: r) 
    } 
} 

fold(BFS(tree, List((0, 0)), Nil), Nil).map(_._2) 

Answer 2

你tree參數DFS是永遠不會變小。因此，您將永遠不會觸及基本案例。

應該打電話給這個：DFS(tree.tail, x._1)？

Answer 3

儘管尾部遞歸可能需要一些時間，但您可以像下面那樣使用它。

val tree: List[(Int, Int)] = List((1,0),(2,0),(3,0),(4,1),(5,4),(6,2),(7,6)) 

def DFS(tree: List[(Int, Int)], id: Int): List[Tree] = tree match { 
    case Nil => List[Tree]() 
    case list => 
    val (children, others) => list.partition(x => x._2 == id) 
    List(Tree(id, children.flatMap(x => DFS(others, x._1)))) 
}