Kotlin:N木における葉節経路の探索

定義
ツリーは、ノードが0個以上の子を持つことができるデータ構造体です.各ノードは値を含み、一番上のノードはルートと呼ばれます.子ノードを持たないノードをリーフノードと呼ぶ.
The N-ary tree あなたがN(N)を持つことができる木です≥ 0 )特定のノードの子の数は、特定のノードのほとんどの子を持つバイナリツリーとは対照的です.
ここでは、葉ノードへのパスを得るために使うサンプルツリーを示します.

上のツリーでは、1がルートノード、2、3、4がルートノードの子です.ノード5 , 6 , 7 , 8 , 9 , 10 , 11はすべての葉ノードです.

タスク
上記のn - aryツリーを考えて、葉ノードへの経路を得るために解決策を書いてください.解決策は以下のように葉節へのパスのリストを返すべきです.

    [1,2,5]
    [1,2,6]
    [1,2,7]
    [1,3,8]
    [1,4,9]
    [1,4,10]
    [1,4,11]

解決策
まず、N - aryツリーデータクラスを定義します.

data class Node<T>(var value: T) {
    var parent: Node<T>? = null
    var children: MutableList<Node<T>> = mutableListOf()

     fun addChild(node: Node<T>) {
         children.add(node)
         node.parent = this
     }
    fun hasChildren(): Boolean =
        children.size >= 1
}

次に関数を作成しますmakeTree() これは上記のn - aryツリーを構築します.

fun makeTree(): Node<Int> {
    val root =  Node(1)
    val node2 = Node(2)
    root.addChild(node2)
    val node3 = Node(3)
    root.addChild(node3)
    val node4 = Node(4)
    root.addChild(node4)
    val node5 = Node(5)
    node2.addChild(node5)
    val node6 = Node(6)
    node2.addChild(node6)
    val node7 = Node(7)
    node2.addChild(node7)
    val node8 = Node(8);
    node3.addChild(node8)
    val node9 = Node(9)
    node4.addChild(node9)
    val node10 = Node(10)
    node4.addChild(node10)
    val node11 = Node(11)
    node4.addChild(node11)
    return root
}

リーフノードへのパスを取得するには深さ優先探索を使用します.Depth-first search (dfs)は木やグラフのデータ構造を横断または探索するためのアルゴリズムである.つは、ルート(いくつかの任意のノードをグラフの場合のルートとして選択)で起動し、バックトラッキングの前に、各ブランチに沿って可能な限り探索します.
我々は、Nノード木を横断して、葉ノードが見つかるまで、すべてのノードを経路に挿入し続けます.リーフノードが見つかると、結果へのパスを追加し、最後の追加されたリーフノードをパスから削除し、次の葉ノードをチェックします.
再帰的なバックトラッキングルーチンです.

private fun findLeafNodePaths(
    node: Node<Int>,
    result: MutableList<List<Int>>,
    path: MutableList<Int>): MutableList<List<Int>> {

    path.add(node.value)
    if (!node.hasChildren()) { // leaf node
        result.add(path.map { it }) // add path to the result
        path.removeLast()//
    } else {
        for (child in node.children) {
            findLeafNodePaths(child, result, path)
        }
        path.removeLast()
    }
    return result
}

ここでは、葉ノードへのn進木と印刷パスを作成する主な機能があります.

fun main() {
    findLeafNodePaths(makeTree(),  mutableListOf(), mutableListOf() ).forEach {
        println(it)
    }
}

コンプリートコード
< div >