Восстановить N-арное дерево из списка

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

У меня есть упорядоченный список из следующих трех значений (в порядке появления): ID, Name и Depth.

 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- car как Map<Node, Set<Node>> , визуализированное ниже:

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

Каков наилучший (наиболее эффективный и / или наиболее читаемый) способ выполнения этой задачи?

Учитывая 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) } 

Основная идея состоит в том, чтобы использовать стек для отслеживания родителей на пути от корневого до текущего обработанного узла:

  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) 
Intereting Posts
автономный сценарист, чтобы получить intellij проект В Котлине я могу переопределить некоторые существующие операторы, но как насчет создания новых операторов? Функция инициализации массива Котлина делегировать вложенную закрытую закрытие соответствующего класса Как обновить виджет Android Studio Kotlin Утечка памяти в Java, но не в Котлине (той же базы кода) … почему? Установить LayoutManager на фрагменте Почему этот ChildEventListener не считывает данные с узла firebase? Kotlin: Может ли абстрактный суперкласс иметь абстрактный конструктор? MutableLiveData с многократным укладом Kotlin Generic не работает Сигнал / событие AboutToQuit в Android Objectbox: Как инициализировать ToMany <> отношение в kotlin «Ошибка неоднозначности разрешения перегрузки» разрешена с другой перегрузкой Как «продолжить» или «ломать» в выражении `when` внутри цикла while, используя Kotlin Котлин: пропуская коротины