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
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の時は次の層を探しにいくような処理に変えます

``````javascript
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から見つけてくる必要があります。

``````javascript
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文を無限に書く必要はなくなるわけです。

``````javascript
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に書き換えます。

``````javascript
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が探す範囲でしたので、以下のようにすれば良さそうです。

``````javascript
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に戻す）
という流れにすると良さそうです。

``````javascript
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]

``````javascript
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)
  }
}
``````