我的数据具有以下属性:

1. 每个条目都有一个唯一的标识(Id)
2. 每个都有一个 Parent 字段，指向父级的 Id。
3. 一个节点可以有多个子节点，但只有一个父节点。

我第一次尝试 build 一棵树如下。这是错误的，因为递归会导致无限循环。即使我解决了它，我也不确定是否有更好的方法来做到这一点。目前，我分两次完成。

我希望它尽可能高效，因为我有大量数据。还需要动态重建树(根可以是任意节点)

程序中有示例数据如下:

 arry = [{"Id":"1", "Name":"abc", "Parent":""}, {"Id":"2", "Name":"abc", "Parent":"1"},
    {"Id":"3", "Name":"abc", "Parent":"2"},{"Id":"4", "Name":"abc", "Parent":"2"}]//for testing

我希望输出是(它可能是错误的嵌套结构，正如我手动编写的那样。但是，我希望的是一个有效的 JSON 结构，其中节点作为字段“值”，子节点作为数组。)

{
 "value": {"Id":"1", "Name":"abc", "Parent":""},
 "children": [
  {
   "value": {"Id":"2", "Name":"abc", "Parent":"1"},
   "children": [
    {
     "value": {"Id":"3", "Name":"abc", "Parent":"2"},
     "children": []
     },
     {
     "value": {"Id":"4", "Name":"abc", "Parent":"2"},
     "children": []
     }
   ]
..
}

示例程序:

function convertToHierarchy(arry, root) 
{
//root can be treated a special case, as the id is known
    arry = [{"Id":"1", "Name":"abc", "Parent":""}, {"Id":"2", "Name":"abc", "Parent":"1"},
    {"Id":"3", "Name":"abc", "Parent":"2"},{"Id":"4", "Name":"abc", "Parent":"2"}]//for testing


    var mapping = {}; // parent : [children]
    for (var i = 0; i < array.length; i++) 
    {
        var node = arry[i];

    if (!mapping[node.Id]) { 
          mapping[node.Id] = {value: node, children:[] } ;
        }else{
      mapping[node.Id] = {value: node} //children is already set    
    }

    if (!mapping[node.Parent]) { //TODO what if parent doesn't exist.
                mapping[node.Parent] =  {value: undefined, children:[ {value: node,children:[]} ]};
        }else {//parent is already in the list
        mapping[node.Parent].children.push({value: node,children:[]} )
    }

    }
    //by now we will have an index with all nodes and their children.

    //Now, recursively add children for root element.

    var root = mapping[1]  //hardcoded for testing, but a function argument
    recurse(root, root, mapping)
    console.log(root)

    //json dump
}

function recurse(root, node, mapping)
{
    var nodeChildren = mapping[node.value.Id].children;
    root.children.push({value:node.value, children:nodeChildren})
   for (var i = 0; i < nodeChildren.length; i++) {
        recurse(root, nodeChildren[i], mapping);
    }
    return root;
}

到目前为止，我有 3 个不错的解决方案，希望赞成票能提出更惯用、更高效的实现方案。我不确定，利用我的数据的属性，在输入数组的集合中只有一个根元素，而且根总是给出，这些实现中的任何一个都可以更好。我还应该学习如何进行基准测试，因为我的要求是重建树的效率(快速/没有太多内存)。例如，输入已经被缓存(数组)并像重建树一样

convertToHierarchy(parentid)
....
convertToHierarchy(parentid2)
...

最佳答案

这是一种解决方案:

var items = [
    {"Id": "1", "Name": "abc", "Parent": "2"},
    {"Id": "2", "Name": "abc", "Parent": ""},
    {"Id": "3", "Name": "abc", "Parent": "5"},
    {"Id": "4", "Name": "abc", "Parent": "2"},
    {"Id": "5", "Name": "abc", "Parent": ""},
    {"Id": "6", "Name": "abc", "Parent": "2"},
    {"Id": "7", "Name": "abc", "Parent": "6"},
    {"Id": "8", "Name": "abc", "Parent": "6"}
];

function buildHierarchy(arry) {

    var roots = [], children = {};

    // find the top level nodes and hash the children based on parent
    for (var i = 0, len = arry.length; i < len; ++i) {
        var item = arry[i],
            p = item.Parent,
            target = !p ? roots : (children[p] || (children[p] = []));

        target.push({ value: item });
    }

    // function to recursively build the tree
    var findChildren = function(parent) {
        if (children[parent.value.Id]) {
            parent.children = children[parent.value.Id];
            for (var i = 0, len = parent.children.length; i < len; ++i) {
                findChildren(parent.children[i]);
            }
        }
    };

    // enumerate through to handle the case where there are multiple roots
    for (var i = 0, len = roots.length; i < len; ++i) {
        findChildren(roots[i]);
    }

    return roots;
}

console.log(buildHierarchy(items));​

关于Javascript:构建分层树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12831746/