Javascript:构建分层树

Question

我的数据有以下属性:

1. 每个条目都有唯一的ID(Id)
2. 每个都有一个Parent字段,它指向父节点的Id.
3. 节点可以有多个子节点,但只有一个父节点.

我第一次尝试建造一棵树就在下面.它是错误的,因为递归导致无限循环.即使我解决了,我也不确定是否有更好的方法来做到这一点.目前,我正在进行2次传球.

我希望它尽可能高效,因为我有相当数量的数据.它还需要动态重建树(根可以是任何节点)

以下程序中有样本数据:

 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)
...

Answer 1

这是一个解决方案:

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));?

Answer 2

虽然上述解决方案确实有效- 我认为它们非常慢且未经优化，有太多循环和过时的方法（我们将使用ES6语法）。我建议使用以下优化的解决方案，这将为您带来性能提升。阅读这篇博文以了解其工作原理。

javascript

const hierarchy = (data) => {
    const tree = [];
    const childOf = {};
    data.forEach((item) => {
        const { Id, Parent } = item;
        childOf[Id] = childOf[Id] || [];
        item.children = childOf[Id];
        Parent ? (childOf[Parent] = childOf[Parent] || []).push(item) : tree.push(item);
    });
    return tree;
};

// print
console.log(hierarchy([{"Id":"1", "Name":"abc", "Parent":""}, {"Id":"2", "Name":"abc", "Parent":"1"}, {"Id":"3", "Name":"abc", "Parent":"2"},{"Id":"4", "Name":"abc", "Parent":"2"}], { idKey: 'Id', parentKey: 'Parent' }));

这是一些结果以及其他海报之间的比较

http://jsben.ch/ekTls

如果您正在寻找带有参数的版本，以获得更动态但稍慢的版本，如下所示：

const hierarchy = (data = [], { idKey = 'id', parentKey = 'parentId', childrenKey = 'children' } = {}) => {
    const tree = [];
    const childrenOf = {};
    data.forEach((item) => {
        const { [idKey]: id, [parentKey]: parentId = 0 } = item;
        childrenOf[id] = childrenOf[id] || [];
        item[childrenKey] = childrenOf[id];
        parentId ? (childrenOf[parentId] = childrenOf[parentId] || []).push(item) : tree.push(item);
    });
    return tree;
}

快乐黑客

Answer 3

这是另一个.这适用于多个根节点:

function convertToHierarchy() { 

    var arry = [{ "Id": "1", "Name": "abc", "Parent": "" }, 
    { "Id": "2", "Name": "abc", "Parent": "1" },
    { "Id": "3", "Name": "abc", "Parent": "2" },
    { "Id": "4", "Name": "abc", "Parent": "2"}];

    var nodeObjects = createStructure(arry);

    for (var i = nodeObjects.length - 1; i >= 0; i--) {
        var currentNode = nodeObjects[i];

        //Skip over root node.
        if (currentNode.value.Parent == "") {
            continue;
        }

        var parent = getParent(currentNode, nodeObjects);

        if (parent == null) {
            continue;
        }

        parent.children.push(currentNode);
        nodeObjects.splice(i, 1);
    }

    //What remains in nodeObjects will be the root nodes.
    return nodeObjects;
}

function createStructure(nodes) {
    var objects = [];

    for (var i = 0; i < nodes.length; i++) {
        objects.push({ value: nodes[i], children: [] });
    }

    return objects;
}

function getParent(child, nodes) {
    var parent = null;

    for (var i = 0; i < nodes.length; i++) {
        if (nodes[i].value.Id == child.value.Parent) {
            return nodes[i];
        }
    }

    return parent;
}