Javascript：构建分层树 [英] Javascript: Building a hierarchical tree

问题描述

我的数据包含以下属性：

My data has these properties:

1. 每个条目都有唯一ID（Id）


2. 每个都有一个父字段，它指向父母的Id。


3. 一个节点可以有多个子节点，但只有一个父节点。

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

My first attempt to build a tree is below. It is buggy as the recursion causes an infinite loop. Even if I solve it, I am not sure if there is a better approach to do this. Currently, I am doing it in 2 passes.

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

I would like it to be as efficient as possible as I have a decent amount of data. It also needs to rebuild the tree dynamically (the root can be any node)

下面的程序中有样本数据：

There is sample data in the program below:

 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结构，节点作为字段'值'和子项为一个数组。）

I was hoping the output to be (it might be wrong nested structure, as I manually wrote it. but, what I am hoping is a valid JSON structure with node as a field 'value' and children as an array.)

{
 "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个很好的解决方案，希望upvotes建议更多惯用，有效实施。我不确定，利用我的数据的属性，输入数组中只有一个根元素，并且总是给出根，这些实现中的任何一个都可能更好。我也应该学习如何进行基准测试，因为我的要求是如何有效地（快速/没有太多内存）树可以重建。例如，输入已经缓存（数组）并重建树，如

I have 3 good solutions so far, and hope the upvotes suggest more idiomatic, efficient implementation. I am not sure, utilizing the property of my data that, there will be only one root element in the set of input array, and also the root is always given, any of these implementation could be better. I should also be learning how to benchmark, as my requirement is how efficiently (fast/without much memory) the tree can be rebuild. For example, the input is already cached (array) and rebuild the tree like

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：构建分层树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！