3

我正面临着一个脑筋急转弯（至少对我来说）：我得到一个 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 回答
1

这应该做http://jsfiddle.net/arPgr/

var arr = [
{"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":[]}
]

var i = 0, len = arr.length, item, parent, id, key, treeArr = {};

for (; i < len; i++) {
    item = arr[i];
    parent = item.parent_id;
    id = item.id;

    if (treeArr[id] == undefined) {
       treeArr[id] = item;   
    } else if (typeof treeArr[id] == 'object') {
        for (key in item) {
            if (key == 'children') continue;
            treeArr[id][key] = item[key];   
        }        
    }

    if (typeof treeArr[parent] != 'object') {
        treeArr[parent] = { children: [] };   
    }

    treeArr[parent].children.push(treeArr[id]);
}

console.log(treeArr[0]);
于 2013-10-07T10:59:46.920 回答
0

使用新数组存储结果..

var ret = [];
for (var i = 0; i < arr.length; i++) {
    if (arr[i].parent_id == 0) {
        ret.push(arr[i]);
        continue;
    }
    for (var j = 0; j < arr.length; j++) {
        if (arr[i].parent_id == arr[j].id) {
            arr[j].children.push(arr[i]);
            break;
        }
    }
}
于 2013-10-07T11:09:00.747 回答
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 回答