91762


自身のIDと親IDを持つOriginalDataを木構造の形にしたいと考えています。

`inputDatas`を`result`の形に変換したい

再帰的な処理をしたいのですが、いい方法が思いつきません。

言語は特に何でも大丈夫です。

[code]

    struct OriginalData {
      let id: String
      let parentID: String?
    }
    
    struct Node {
      let id: String
      var children: [Node]
    }
    
    let inputDatas: [OriginalData] = [
      .init(id: "1", parentID: nil),
      .init(id: "2", parentID: "1"),
      .init(id: "3", parentID: "2"),
      .init(id: "4", parentID: "1"),
      .init(id: "5", parentID: "4"),
    ]
    
    let result = Node(id: "1", children: [
      Node(id: "2", children: [Node(id: "3", children: [])]),
      Node(id: "4", children: [Node(id: "5", children: [])])
    ])
    
[/code]


CC BY-SA 4.0
2022-10-23T09:07:12.353
91758
2022-10-23T14:52:38.793
2022-10-23T10:16:39.907
19110
40856
question
アルゴリズム データ構造
１次元配列を木構造の形に成形したい


入力データが表す構造が木になっていることを仮定すると、深さ優先探索のようなことをすれば計算できます。

  1. 入力は child から parent が探せる形になっているので parent から child たちを探しやすいように parent id を key、child id たちの配列が value になるような辞書にする。（これをしなくても計算はできるので、やらなくてもよい。）
  2. 木の根（parent が nil な node）から見て `Node` の構築を始める。
  3. 今見ている node について `Node(id: "ほにゃらら", children: ???)` までは作れるので、`children` を以下のように作る。 
    * ひもづく child たちがいなければ自分が木の葉（末端 node）になる。つまり `children` は `[]`。
    * ひもづく child たちがいれば、それぞれに対して手順 3 を行って返ってきた node たちを `children` にする。


CC BY-SA 4.0
2022-10-23T10:32:29.547
91762
2022-10-23T10:32:29.547
19110
91758
answer

[code]

    extension Node {
      mutating func addChild(allData: [OriginalData]) {
        for i in children.indices {
          children[i].children = allData.filter { children[i].id == $0.parentID }.map { .init(id: $0.id, children: [])}
          
          for j in children.indices {
            children[j].addChild(allData: allData)
          }
        }
      }
    }
    
[/code]


CC BY-SA 4.0
2022-10-23T14:52:38.793
91770
2022-10-23T14:52:38.793
40856
91758
answer