リストからN-aryツリーを再構成する

Question

data class Node(val ID : Long, val name : String) 

ID、名前、深度の3つの値（表示順）の順序付きリストがあります。私はMap<Node, Set<Node>>として、元N進ツリーを再構築したい、このデータセットを使用して

は

0000 : A : 0 
0001 : B : 1 
0002 : C : 2 
0003 : D : 2 
0004 : E : 1 
0005 : F : 2 
0006 : G : 1 
0007 : H : 1 
0008 : I : 2 

、以下の可視化：

は何ですか

A - B - C 
     - D 
    - E - F 
    - G 
    - H - I 

最高（最もパフォーマンスおよび/または最も読みやすいです）この仕事を達成する方法は？

Answer 1

あなたは、ツリー再構築することができます：

val tree = mutableMapOf<Node, MutableSet<Node>>() 
val parents = ArrayDeque<Node>() 
for ((id, name, depth) in orderedList) { 
    val node = Node(id, name) 
    // pop any parents from this deque as deep or deeper than this node 
    while (parents.size > depth) parents.pop() 
    // add node to tree 
    tree[node] = mutableSetOf() 
    // add node to parent's children if applicable 
    tree[parents.peek()]?.add(node) 
    // add node to parents stack 
    parents.push(node) 
} 

をそして、あなたはあなたが以下の（と仮定すると、文字列を使用することができます持っている文字列からorderedListを構築する必要がある場合に使用可能ですs input: String）：

val orderedList = input.trim().lines().map { line -> 
    val components = line.split(" : ") 
    val id = components.component1().toLong() 
    val name = components.component2() 
    val depth = components.component3().toInt() 
    Triple(id, name, depth) 
} 

Answer 2

基本的な考え方は、現在のノードに処理するために、ルートからトラックに両親を追跡するためにスタックを使用することです：

あなたはトリプルを反復処理となるように、各深さで現在の親を追跡することができ orderedList: List<Triple<Long, String, Int>>考える

 val input = """ 
0000 : A : 0 
0001 : B : 1 
0002 : C : 2 
0003 : D : 2 
0004 : E : 1 
0005 : F : 2 
0006 : G : 1 
0007 : H : 1 
0008 : I : 2 
""" 
     val parsedLines = input.split("\n") 
       .map { it.trim() } 
       .filter { it.isNotEmpty() } 
       .map { line -> 
        val parsedLine = line 
          .split(":") 
          .map { it.trim() } 

        object { 
         val preOrderIndex = parsedLine[0].toInt() 
         val name = parsedLine[1] 
         val height = parsedLine[2].toInt() 
        } 
       } 
       .sortedBy { it.preOrderIndex } 

     parsedLines.forEach { println("${it.preOrderIndex} ${it.name} ${it.height}") } 

     val map = HashMap<Node,HashSet<Node>>() 
     val parents = Stack<Node>() 

     for (nodeDesc in parsedLines) { 
      val newNode = Node(nodeDesc.preOrderIndex.toLong(), nodeDesc.name) 
      map[newNode] = HashSet<Node>() 

      while (parents.size > nodeDesc.height) 
       parents.pop() 

      if (!parents.empty()) { 
       val tmp: HashSet<Node>? = map[parents.peek()] 
       tmp!!.add(newNode) 
      } 

      parents.push(newNode) 
     } 

     println(map)