从列表中重建N元树

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

我有以下三个值（按照外观顺序）的有序列表：ID，名称和深度。

 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 

使用这个数据集，我希望将原始的N- tree树重建为一个Map<Node, Set<Node>> ，可视化如下：

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

什么是最好的（最高性能和/或最可读）的方式来完成这项任务？

Answer 1

给定一个orderedList: List<Triple<Long, String, Int>>您可以遍历三元组并在每个深度跟踪当前父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 ，你可以使用下面的代码（假设字符串可以作为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)