前提・実現したいこと

javascriptを扱っています。

こういった配列データがあるとします。

var datas = [
  {
    id: 0,
    parent: null
  },
  {
    id: 1,
    parent:0
  },
  {
    id: 2,
    parent:0
  },
  {
    id: 3,
    parent:1
  },
  {
    id: 4,
    parent: 1
  },
  {
    id: 5,
    parent: 2
  }
]

これをネスト構造のオブジェクトに構築したいです。

var tree = [{
  id: 0,
  children: [
    {
      id: 1,
      children: [
        {
          id: 3,
          children: []
        },
        {
          id: 4,
          children: []
        }
      ]
    }, {
      id: 2,
      children: [
        {
          id: 5,
          children: []
        }
      ]
    }
  ]
}]

再帰関数を作ればできるかと思い、以下の方法を試しましたが最後詰まってしまいました。

良い解決方法はあるでしょうか。

試したこと

datasは順々に0番目からtreeに押し込まれていきます。

まずdatas[0]は、{id:0,parent:null}は親がいませんからtreeにそのまま押し込まれます。（この処理だけ例外的なので、ここの処理は後から考えます）

tree=[
 {id:0,
  children:[]
 }
]

ここからが再帰関数処理の考え所です。

datas[1] {id:1,parent:0}は、treeの中から親となるid:0を探し出して、id:0のchildrenに自分自身を押し込みます。
datas[2]も同様に、treeの中から親となるid:0を探し出して、id:0のchildrenに自分自身を押し込みます。

ここまでの動きを関数で示すと以下の通りです。

function createTree(){
  return datas.reduce((acc,cur) => { 
    var parent = tree.find(e=>e.id==cur.id)
    parent.children.push(cur)
    return acc
  },[])
}

今のところ、treeは以下のように出来上がっているはずです。

var tree = [{
    id: 0,
    children: [
      {
        id: 1,
        children: []
      },{
        id: 2,
        children: []
      }
    ]
  }]

ここまでは良いのですが、datas[3]はparentがid:1のため、tree.findでは見つけるべき親を見つけられず、treeから親を見つけるためには以下のように記述する必要があります。

tree[0].children.find(e=>e.id==cur.id)

このようにreduceのtree.findではネストの深部まで見つけられないため、深部まで探って見つけてくるような関数を実装してやります。
新たな関数名をdeepFindとしました。
ひとまずはfindと同じ機能となるよう実装します。

javascript
1function deepFind(tree,cur){
2  var result=tree.find(e=>e.id==cur.id)
3  return result
4}
5
6//以下と同じ機能
7result=tree.find(e=>e.id==cur.id)

さて、deepFind関数を実装していくにあたり、datas[4]をどのように処理していくか考えましょう。
ひとまず、そのままではresultは何も返って来ないので、undefinedの時は次の層を探しにいくような処理に変えます

javascript
1function deepFind(tree,cur){
2  var result=tree.find(e=>e.id==cur.id)
3+ if(result){
4+   return result
5+ }else{
6+   result=tree[0].children.find(e=>e.id==cur.id)
7+   return result
8+ }
9}

この状態でdatas[5]までは対応できます。
しかしdatas[6]の親はtree[0].childrenからは見つけれこれず、tree[1].childrenから見つけてくる必要があります。

javascript
1function deepFind(tree,cur){
2  var result=tree.find(e=>e.id==cur.id)
3  if(result){
4    return result
5  }else{
6    result=tree[0].children.find(e=>e.id==cur.id)
7+   if(result){
8+     return result
9+   }else{
10+     rusult=tree[1].children.find(e=>e.id==cur.id)
11+     if(result){
12+       return result
13+     }else{
14+       //以下同じように続いていく
15+     }
16+   }
17  }
18}

さて、ここまで書いていて気づくかもしれませんが、この関数は「resultがあればresultを返し、なければ探す範囲を変えて同じようにfindメソッドで検索していく」という流れです。

ということは、function deepFind(tree,cur)のtreeの部分さえ、次の探す範囲に書き換えてやればif文を無限に書く必要はなくなるわけです。

javascript
1function deepFind(tree,cur){
2  var result=tree.find(e=>e.id==cur.id)
3  if(result){
4    return result
5  }else{
6+   return deepFind(*次の検索範囲*,cur)
7  }
8}

探す範囲がtreeなのは最初の一発だけなので、もっと一般的な意味あいでtargetという言葉に書き換えてやります。
ついでに探すキーワードをcurからsubjectに書き換えます。

javascript
1function deepFind(target,subject){
2  var result=target.find(e=>e.id==subject.id)
3  if(result){
4    return result
5  }else{
6    return deepFind(*次の検索範囲*,subject)
7  }
8}

さて、この次の検索範囲というのはどのように指定すれば良いのでしょうか。

data[1]とdata[2]ではtreeが、
datas[3]とdatas[4]ではtree[0].children、datas[5]ではtree[1].childrenが探す範囲でしたので、以下のようにすれば良さそうです。

javascript
1var idx=0;
2function deepFind(target,subject){
3  var result=target.find(e=>e.id==subject.id)
4  if(result){
5    return result
6  }else{
7    idx++
8    var nextTarget=tree[idx].children
9    return deepFind(nextTarget,subject)
10  }
11}

ただこの記述だと、ネストが1階層は対応できますが、もっと深いネストになった時に対応できません。

treeのネストが深くなっていった時に、どうやったら抜け漏れなく親を探せるか考えます。

0①--1②--3③--5④
 　|  　|  　|-6④
 　|  　|-4③--7⑤
 　|  　   　|-8⑤
 　|-2②--9⑥

検索範囲の指定方法
①tree
②tree[0].children
③tree[0].children[0].children
④tree[0].children[0].children[0].children  //これ以上深いネストはない
⑤tree[0].children[0].children[1].children　//これより下に兄弟ネストはない
⑥tree[0].children[1]

このように深いネストの時はtargetに[0].childrenを追加し、兄弟ネストに移る時は0にプラス1にすれば良いわけです。

したがってロジックとしては、
今探しているところに親が見つからない
→もう一段階深いネストがあれば、そこを検索
→それ以上深いネストがない時は、インデックスにプラス1して兄弟ネストを検索する
→兄弟ネストもない時は、一段階浅いネストに移動して兄弟ネストを検索する（その時インデックスは0に戻す）
という流れにすると良さそうです。

javascript
1function deepFind(target,subject){
2  var result=target.find(e=>e.id==subject.id)
3  if(result){
4    return result
5  }else{
6    //もう一段階深いネストがあれば、そこが次の検索ターゲット
7    if(target[0].children.length){
8      var nextTarget=target[0].children
9    } else { 
10      //深いネストがない場合は弟ネストを検索する。
11      if(idx+1<target.length){  //弟がいるか。idx+1がtarget.lengthと同じ値の時には弟はいない
12        var nextTarget=target[idx+1].children
13      }
14    } else {
15    //兄弟ネストもない時は、一段階浅いネストに移動してその弟ネストを検索する
16    //このやり方がわかりません
17    }
18    return deepFind(nextTarget,subject)
19  }
20}

質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう！

前提・実現したいこと

試したこと

new Map

class

オブジェクト初期化子

追記

追記2

追記 id が連番でない、またはルートが複数ある場合

関連した質問