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と同じ機能となるよう実装します。

function deepFind(tree,cur){
  var result=tree.find(e=>e.id==cur.id)
  return result
}

//以下と同じ機能
result=tree.find(e=>e.id==cur.id)

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

function deepFind(tree,cur){
  var result=tree.find(e=>e.id==cur.id)
+ if(result){
+   return result
+ }else{
+   result=tree[0].children.find(e=>e.id==cur.id)
+   return result
+ }
}

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

function deepFind(tree,cur){
  var result=tree.find(e=>e.id==cur.id)
  if(result){
    return result
  }else{
    result=tree[0].children.find(e=>e.id==cur.id)
+   if(result){
+     return result
+   }else{
+     rusult=tree[1].children.find(e=>e.id==cur.id)
+     if(result){
+       return result
+     }else{
+       //以下同じように続いていく
+     }
+   }
  }
}

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

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

function deepFind(tree,cur){
  var result=tree.find(e=>e.id==cur.id)
  if(result){
    return result
  }else{
+   return deepFind(*次の検索範囲*,cur)
  }
}

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

function deepFind(target,subject){
  var result=target.find(e=>e.id==subject.id)
  if(result){
    return result
  }else{
    return deepFind(*次の検索範囲*,subject)
  }
}

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

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

var idx=0;
function deepFind(target,subject){
  var result=target.find(e=>e.id==subject.id)
  if(result){
    return result
  }else{
    idx++
    var nextTarget=tree[idx].children
    return deepFind(nextTarget,subject)
  }
}

ただこの記述だと、ネストが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に戻す）
という流れにすると良さそうです。

function deepFind(target,subject){
  var result=target.find(e=>e.id==subject.id)
  if(result){
    return result
  }else{
    //もう一段階深いネストがあれば、そこが次の検索ターゲット
    if(target[0].children.length){
      var nextTarget=target[0].children
    } else { 
      //深いネストがない場合は弟ネストを検索する。
      if(idx+1<target.length){  //弟がいるか。idx+1がtarget.lengthと同じ値の時には弟はいない
        var nextTarget=target[idx+1].children
      }
    } else {
    //兄弟ネストもない時は、一段階浅いネストに移動してその弟ネストを検索する
    }
    return deepFind(nextTarget,subject)
  }
}

①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]

var target=tree
depth=0
brothers=[0]

function deepFind(target,subject){
  var result=target.find(e=>e.id==subject.id)
  if(result){
    return result
  }else{
    //もう一段階深いネストがあれば、そこが次の検索ターゲット
    if(target[idx].children.length){
      var nextTarget=target[brothers[depth]].children
      depth++
      brothers.push(0)
    } else { 
      //深いネストがない場合は弟ネストを検索する。
      if(idx+1<target.length){  //弟がいるか。idx+1がtarget.lengthと同じ値の時には弟はいない
        var nextTarget=target[brother[depth]].children
      }
    } else {
    //兄弟ネストもない時は、一段階浅いネストに移動してその弟ネストを検索する
      //ここの実装で行き詰まってしまっています
    }
    return deepFind(nextTarget,subject)
  }
}