3

私はブレインブレーカーに直面しています（少なくとも私にとっては）：次のようなデータオブジェクトの1つの深さの配列を持つjsonファイルを取得します：

[
{"id":1, "name":"Sport", "parent_id":0, "children":[]},
{"id":2, "name":"Tennis", "parent_id":4, "children":[]},
{"id":3, "name":"Climbing", "parent_id":5, "children":[]},
{"id":4, "name":"Indoor", "parent_id":1, "children":[]},
{"id":5, "name":"Outdoor", "parent_id":1, "children":[]},
{"id":6, "name":"Bowling", "parent_id":4, "children":[]}
]

これを、子が親の子配列内に配置されるツリー構造に変換するにはどうすればよいですか? オブジェクトは常に正しい順序であるとは限りません。配列内で子が親の前に来ることがあります。(私の例では id 2 と 3 のように)

これが最終的に必要な方法です：

[
{"id":1, "name":"Sport", "parent_id":0, "children":
  [
    {"id":4, "name":"Indoor", "parent_id":1, "children":
    [
      {"id":2, "name":"Tennis", "parent_id":4, "children":[]},
      {"id":6, "name":"Bowling", "parent_id":4, "children":[]},
    ]},
    {"id":5, "name":"Outdoor", "parent_id":1, "children":
    [
      {"id":3, "name":"Climbing", "parent_id":5, "children":[]}
    ]},
  ]}
]

これを達成する方法はありますか？

要素を反復処理して、親の子配列内にプッシュしようとしましたが、親が移動すると、次の兄弟はもう親を見つけることができません...

4

5 に答える 5

5

非効率な O 2アルゴリズム (入れ子になった for ループ)を書くことに誰もが熱中する理由はわかりませんが、O(n log n) 時間の例を次に示します。

function treeify(nodes) {
    var indexed_nodes = {}, tree_roots = [];
    for (var i = 0; i < nodes.length; i += 1) {
        indexed_nodes[nodes[i].id] = nodes[i];
    }
    for (var i = 0; i < nodes.length; i += 1) {
        var parent_id = nodes[i].parent_id;
        if (parent_id === 0) {
            tree_roots.push(nodes[i]);
        } else {
            indexed_nodes[parent_id].children.push(nodes[i]);
        }
    }
    return tree_roots;
}

var nodes = [
    {"id":1, "name":"Sport", "parent_id":0, "children":[]},
    {"id":2, "name":"Tennis", "parent_id":4, "children":[]},
    {"id":3, "name":"Climbing", "parent_id":5, "children":[]},
    {"id":4, "name":"Indoor", "parent_id":1, "children":[]},
    {"id":5, "name":"Outdoor", "parent_id":1, "children":[]},
    {"id":6, "name":"Bowling", "parent_id":4, "children":[]}
];

console.log(JSON.stringify(treeify(nodes), undefined, "\t"));
于 2013-10-07T11:12:46.617 に答える
0

これを試して

for (var i = 0; i < a.length; i++) {
    for (var j = 0; j < a.length; j++) {
        if(a[j].id == a[i].parent_id){
            a[i].children.push(a[j])
        }
    }
}

フィドル

于 2013-10-07T10:50:25.303 に答える
0

関数 reorder は、配列を階層に変換します。これは、parent_id ===0 を持つオブジェクトをルート オブジェクトとして返します。 このフィドルを参照してください

var src = 
    [
{"id":1, "name":"Sport", "parent_id":0, "children":[]},
{"id":2, "name":"Tennis", "parent_id":4, "children":[]},
{"id":3, "name":"Climbing", "parent_id":5, "children":[]},
{"id":4, "name":"Indoor", "parent_id":1, "children":[]},
{"id":5, "name":"Outdoor", "parent_id":1, "children":[]},
{"id":6, "name":"Bowling", "parent_id":4, "children":[]}
];

function reorder(orig)
{
    var cnt,id, pid, root, fcnt;
    for(cnt = 0; cnt < orig.length; cnt = cnt + 1) {
        pid = orig[cnt].parent_id;
        id = orig[cnt].id;
        if (pid === 0) {
            root = orig[cnt]
        }
        // loop until cnt, then skip that index
        for (fcnt=0;fcnt<cnt;fcnt=fcnt+1){
            if (orig[fcnt].parent_id === id) {
                orig[cnt].children.push(orig[fcnt]);
            }
        }
        // loop from cnt + 1 till end of array 
        for (fcnt=cnt+1;fcnt<orig.length;fcnt=fcnt+1){
           if (orig[fcnt].parent_id === id) {
                orig[cnt].children.push(orig[fcnt]);
            }
        }            
    }
    return root;
}

var dest = reorder(src);
console.log(JSON.stringify(dest));
于 2013-10-07T10:53:48.877 に答える