리스트에서 N-ary 트리를 다시 구성하십시오.

Question

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

ID, 이름 및 깊이의 세 가지 값 (표시 순서대로)의 정렬 된 목록이 있습니다. 나는 Map<Node, Set<Node>>로 원래 N -ary 트리를 재구성 할이 데이터 세트를 사용

는

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

는 orderedList: List<Triple<Long, String, Int>> 당신이 트리플을 반복하고 각각의 깊이에 현재의 부모를 추적 할 수 감안할 때 당신은 나무 재 구축 할 수 있습니다 :

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

기본 아이디어는 뿌리에서 트랙에 부모를 추적하기 위해 스택을 사용하는 것입니다 현재 처리하는 노드 :

 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)