木構造の再帰を使った巡回

少し前に 特定のディレクトリ以下全部のファイルとディレクトリをリストにするというエントリーを書いたのですが、 その応用です。

環境

$ kotlin -version
Kotlin version 1.8.10-release-430 (JRE 17.0.9+9-Ubuntu-122.04)

木構造のノードを表現する Node クラス

data class Node(val id: String, val children: List<Node> = listOf())

木構造の定義

val rootNode =
  Node("0", listOf(
    Node("01", listOf(
      Node("01-01"),
      Node("01-02"),
      Node("01-03"))),
    Node("02", listOf(
      Node("02-01"),
      Node("02-02"),
      Node("02-03"))),
    Node("03", listOf(
      Node("03-01"),
      Node("03-02"),
      Node("03-03")))))

木構造を再帰的に巡回する関数

Node を List にする。（つまりフラットにする）

traverse: (Node)->List<Node>

再帰させるので普通の関数として定義。

fun traverse(node: Node): List<Node> {
    val hasChild: (Node)->Boolean = { (it.children.size>0) }

    return if( !hasChild(node) ){
        listOf(node)
    } else {
        listOf(node) + node.children.map { subNode->
            traverse(subNode)
        }.flatten()
    }
}

結果を確かめる

val nodeList = traverse(rootNode)

nodeList.forEach {
    val indent = 0.until(it.id.length).map { " " }.joinToString("")
    println("${indent}- ${it.id}")
}

結果が分かりやすいようにインデントを計算しています。 id の文字列の長さから深さをきめるという適当なコード。

実行する

kotlin treenode.main.kts
 - 0
  - 01
     - 01-01
     - 01-02
     - 01-03
  - 02
     - 02-01
     - 02-02
     - 02-03
  - 03
     - 03-01
     - 03-02
     - 03-03

できた。

まとめ

コード全体を掲載する。

node.main.kts

data class Node(val id: String, val children: List<Node> = listOf())

fun traverse(node: Node): List<Node> {
    val hasChild: (Node)->Boolean = { (it.children.size>0) }

    return if( !hasChild(node) ){
        listOf(node)
    } else {
        listOf(node) + node.children.map { subNode->
            traverse(subNode)
        }.flatten()
    }
}

val rootNode =
    Node("0", listOf(
        Node("01", listOf(
       	    Node("01-01"),
            Node("01-02"),
            Node("01-03"))),
        Node("02", listOf(
            Node("02-01"),
            Node("02-02"),
            Node("02-03"))),
        Node("03", listOf(
            Node("03-01"),
            Node("03-02"),
            Node("03-03")))))

val nodeList = traverse(rootNode)

nodeList.forEach {
    val indent = 0.until(it.id.length).map { " " }.joinToString("")
    println("${indent}- ${it.id}")
}

次のようにして実行。

$ kotlin node.main.kts

以上です。