在树数据结构中逐级获取每个根的索引

Question

嘿，我正在研究树数据结构。我想知道我们能否按级别获取每个节点的索引。我下图表示我想要值+索引的方式。 A级或B级代表节点值，索引值代表索引值

                                     Node
                     |                 |                 |
Level A ->           1                 2                 3
index value->        0                 1                 2
                 |       |          |      |          |     |
                 |       |          |      |          |     |
Leve B->         4       5          6      7          8     9
index value->    0       1          2      3          4     5

....// more level

我们如何才能在每个级别上达到指标。我正在添加我的逻辑，我如何在每个级别明智地增加价值。有人可以建议我如何实现吗？

var baseNode: LevelIndex = LevelIndex()
var defaultId = "1234"
fun main() {
    val list = getUnSortedDataListForLevel()
    val tempHashMap: MutableMap<String, LevelIndex> = mutableMapOf()
    list.forEach { levelClass ->
        levelClass.levelA?.let { levelA ->
            val levelOneTempHashMapNode = tempHashMap["level_a${levelA}"]
            if (levelOneTempHashMapNode != null) {
                if (defaultId == levelClass.id && levelOneTempHashMapNode is LevelOne) {
                    levelOneTempHashMapNode.defaultValue = true
                }
                return@let
            }
            val tempNode = LevelOne().apply {
                value = levelA
                if (defaultId == levelClass.id) {
                    defaultValue = true
                }
            }
            baseNode.children.add(tempNode)
            tempHashMap["level_a${levelA}"] = tempNode
        }

        levelClass.levelB?.let { levelB ->
            val levelTwoTempHashMapNode = tempHashMap["level_a${levelClass.levelA}_level_b${levelB}"]
            if (levelTwoTempHashMapNode != null) {
                if (defaultId == levelClass.id && levelOneTempHashMapNode is LevelTwo) {
                    levelTwoTempHashMapNode.defaultValue = true
                }
                return@let
            }
            val tempNode = LevelTwo().apply {
                value = levelB
                if (defaultId == levelClass.id) {
                    defaultValue = true
                }
            }
            val parent =
                tempHashMap["level_a${levelClass.levelA}"] ?: baseNode
            parent.children.add(tempNode)
            tempHashMap["level_a${levelClass.levelA}_level_b${levelB}"] =
                tempNode
        }

        levelClass.levelC?.let { levelC ->
            val tempNode = LevelThree().apply {
                value = levelC
                if (defaultId == levelClass.id) {
                    defaultValue = true
                }
            }
            val parent =
                tempHashMap["level_a${levelClass.levelA}_level_b${levelClass.levelB}"]
                    ?: baseNode
            parent.children.add(tempNode)
        }
    }
}

open class LevelIndex(
    var value: String? = null,
    var children: MutableList<LevelIndex> = arrayListOf()
)

class LevelOne : LevelIndex() {
    var defaultValue: Boolean? = false
}

class LevelTwo : LevelIndex() {
    var defaultValue: Boolean? = false
}

class LevelThree : LevelIndex() {
    var defaultValue: Boolean = false
}

更新

我想要根级别的索引值，因为我有一个 ID，我想将该组合与该 ID 匹配，如果存在该值，那么我将存储该值 b true，需要找到那个索引值。

                                 Node
                     |                 |                 |
Level A ->           1                 2                 3
index value->        0                 1                 2
default value->     false             true             false
                 |       |          |      |          |     |
                 |       |          |      |          |     |
Leve B->         4       5          6      7          8     9
index value->    0       1          2      3          4     5
default value->false   false       true   false     false  false
....// more level

所以，A 级我会得到 索引 1。

对于 B 级，我将得到 索引 2

Answer 1

我会创建一个列表来按顺序排列每个级别的节点。您可以从树中递归地收集它们。

val nodesByLevel = List(3) { mutableListOf<LevelIndex>() }

fun collectNodes(parent: LevelIndex) {
    for (child in parent.children) {
        val listIndex = when (child) {
            is LevelOne -> 0
            is LevelTwo -> 1
            is LevelThree -> 2
            // I made LevelIndex a sealed class. Otherwise you would need an else branch here.
        }
        nodesByLevel[listIndex] += child
        collectNodes(child)
    }
}

collectNodes(baseNode)

现在nodesByLevel包含三个列表，其中按顺序包含每一层中的所有节点。

如果您只需要字符串值，您可以将 mutableList 更改为使用字符串类型并使用 += child.value ?: "" 代替，尽管我会 value non-nullable （所以你不需要?: ""），因为没有价值的节点有什么用？

编辑我会将 defaultValue 向上移动到父 class 中，这样您就不必转换节点就可以读取它。我要将其视为 non-nullable.

sealed class LevelIndex(
    var value: String = "",
    val children: MutableList<LevelIndex> = arrayListOf()
    var isDefault: Boolean = false
)

然后，如果您想根据项目的索引对项目执行某些操作：

for ((layerNumber, layerList) in nodesByLevel.withIndex()) {
    for((nodeIndexInLayer, node) in layerList) {
        val selectedIndexForThisLayer = TODO() //with layerNumber
        node.isDefault = nodeIndexInLayer == selectedIndexForThisLayer
    }
}

在树数据结构中逐级获取每个根的索引

Get index of each root on level wise in tree data structure

tree

data-structures

kotlin