list 在javascript中从平面数组构建树数组

Build tree array from flat array in javascript

提问by Franck

I have a complex json file that I have to handle with javascript to make it hierarchical, in order to later build a tree. Every entry of the json has : id : a unique id, parentId : the id of the parent node (which is 0 if the node is a root of the tree) level : the level of depth in the tree

我有一个复杂的 json 文件，我必须用 javascript 处理它以使其分层，以便以后构建一棵树。json 的每个条目都有： id ：一个唯一的 id， parentId ：父节点的 id （如果节点是树的根，则为 0） level ：树中的深度级别

The json data is already "ordered". I mean that an entry will have above itself a parent node or brother node, and under itself a child node or a brother node.

json 数据已经“排序”了。我的意思是一个条目将在其自身之上有一个父节点或兄弟节点，在其自身之下有一个子节点或兄弟节点。

Input :

输入 ：

{
    "People": [
        {
            "id": "12",
            "parentId": "0",
            "text": "Man",
            "level": "1",
            "children": null
        },
        {
            "id": "6",
            "parentId": "12",
            "text": "Boy",
            "level": "2",
            "children": null
        },
                {
            "id": "7",
            "parentId": "12",
            "text": "Other",
            "level": "2",
            "children": null
        },
        {
            "id": "9",
            "parentId": "0",
            "text": "Woman",
            "level": "1",
            "children": null
        },
        {
            "id": "11",
            "parentId": "9",
            "text": "Girl",
            "level": "2",
            "children": null
        }
    ],
    "Animals": [
        {
            "id": "5",
            "parentId": "0",
            "text": "Dog",
            "level": "1",
            "children": null
        },
        {
            "id": "8",
            "parentId": "5",
            "text": "Puppy",
            "level": "2",
            "children": null
        },
        {
            "id": "10",
            "parentId": "13",
            "text": "Cat",
            "level": "1",
            "children": null
        },
        {
            "id": "14",
            "parentId": "13",
            "text": "Kitten",
            "level": "2",
            "children": null
        },
    ]
}

Expected output :

预期输出：

{
    "People": [
        {
            "id": "12",
            "parentId": "0",
            "text": "Man",
            "level": "1",
            "children": [
                {
                    "id": "6",
                    "parentId": "12",
                    "text": "Boy",
                    "level": "2",
                    "children": null
                },
                {
                    "id": "7",
                    "parentId": "12",
                    "text": "Other",
                    "level": "2",
                    "children": null
                }   
            ]
        },
        {
            "id": "9",
            "parentId": "0",
            "text": "Woman",
            "level": "1",
            "children":
            {

                "id": "11",
                "parentId": "9",
                "text": "Girl",
                "level": "2",
                "children": null
            }
        }

    ],    

    "Animals": [
        {
            "id": "5",
            "parentId": "0",
            "text": "Dog",
            "level": "1",
            "children": 
                {
                    "id": "8",
                    "parentId": "5",
                    "text": "Puppy",
                    "level": "2",
                    "children": null
                }
        },
        {
            "id": "10",
            "parentId": "13",
            "text": "Cat",
            "level": "1",
            "children": 
            {
                "id": "14",
                "parentId": "13",
                "text": "Kitten",
                "level": "2",
                "children": null
            }
        }

    ]
}

回答by Halcyon

There is an efficient solution if you use a map-lookup. If the parents always come before their children you can merge the two for-loops. It supports multiple roots. It gives an error on dangling branches, but can be modified to ignore them. It doesn't require a 3rd-party library. It's, as far as I can tell, the fastest solution.

如果您使用地图查找，则有一个有效的解决方案。如果父母总是在他们的孩子之前，你可以合并两个 for 循环。它支持多个根。它在悬垂的分支上给出错误，但可以修改以忽略它们。它不需要第 3 方库。据我所知，这是最快的解决方案。

function list_to_tree(list) {
  var map = {}, node, roots = [], i;
  for (i = 0; i < list.length; i += 1) {
   map[list[i].id] = i; // initialize the map
   list[i].children = []; // initialize the children
  }
  for (i = 0; i < list.length; i += 1) {
   node = list[i];
   if (node.parentId !== "0") {
    // if you have dangling branches check that map[node.parentId] exists
    list[map[node.parentId]].children.push(node);
   } else {
    roots.push(node);
   }
  }
  return roots;
 }

 var entries = [
        {
            "id": "12",
            "parentId": "0",
            "text": "Man",
            "level": "1",
            "children": null
        },
        {
            "id": "6",
            "parentId": "12",
            "text": "Boy",
            "level": "2",
            "children": null
        },
                {
            "id": "7",
            "parentId": "12",
            "text": "Other",
            "level": "2",
            "children": null
        },
        {
            "id": "9",
            "parentId": "0",
            "text": "Woman",
            "level": "1",
            "children": null
        },
        {
            "id": "11",
            "parentId": "9",
            "text": "Girl",
            "level": "2",
            "children": null
        }
    ];

 console.log(list_to_tree(entries));

If you're into complexity theory this solution is Θ(n log(n)). The recursive-filter solution is Θ(n^2) which can be a problem for large data sets.

如果您对复杂性理论感兴趣，则此解决方案是 Θ(n log(n))。递归过滤器的解决方案是 Θ(n^2)，这对于大型数据集来说可能是一个问题。

回答by Stephen Harris

As mentioned by @Sander, @Halcyon`s answerassumes a pre-sorted array, the following does not. (It does however assume you have loaded underscore.js - though it could be written in vanilla javascript):

正如@Sander 所提到的，@Halcyon 的回答假设一个预先排序的数组，以下不是。（然而，它确实假设您已经加载了 underscore.js - 尽管它可以用 vanilla javascript 编写）：

Code

代码

// Example usage
var arr = [
    {'id':1 ,'parentid' : 0},
    {'id':2 ,'parentid' : 1},
    {'id':3 ,'parentid' : 1},
    {'id':4 ,'parentid' : 2},
    {'id':5 ,'parentid' : 0},
    {'id':6 ,'parentid' : 0},
    {'id':7 ,'parentid' : 4}
];

unflatten = function( array, parent, tree ){
    tree = typeof tree !== 'undefined' ? tree : [];
    parent = typeof parent !== 'undefined' ? parent : { id: 0 };
        
    var children = _.filter( array, function(child){ return child.parentid == parent.id; });
    
    if( !_.isEmpty( children )  ){
        if( parent.id == 0 ){
           tree = children;   
        }else{
           parent['children'] = children
        }
        _.each( children, function( child ){ unflatten( array, child ) } );                    
    }
    
    return tree;
}

tree = unflatten( arr );
document.body.innerHTML = "<pre>" + (JSON.stringify(tree, null, " "))

<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.9.1/underscore-min.js"></script>

Requirements

要求

It assumes the properties 'id' and 'parentid' indicate ID and parent ID respectively. There must be elements with parent ID 0, otherwise you get an empty array back. Orphaned elements and their descendants are 'lost'

它假定属性 'id' 和 'parentid' 分别表示 ID 和父 ID。必须有父 ID 为 0 的元素，否则返回一个空数组。孤立元素及其后代“丢失”

http://jsfiddle.net/LkkwH/1/

http://jsfiddle.net/LkkwH/1/

回答by FurkanO

( BONUS1 : NODES MAY or MAY NOT BE ORDERED )

（奖励 1：节点可能会或可能不会被订购）

( BONUS2 : NO 3RD PARTY LIBRARY NEEDED, PLAIN JS )

（奖励 2：不需要第 3 方库，纯 JS）

( BONUS3 : User "Elias Rabl" says this is the fastest solution, see his answer below )

（奖励3：用户“Elias Rabl”说这是最快的解决方案，请参阅下面的答案）

Here it is:

这里是：

const createDataTree = dataset => {
    let hashTable = Object.create(null)
    dataset.forEach( aData => hashTable[aData.ID] = { ...aData, childNodes : [] } )
    let dataTree = []
    dataset.forEach( aData => {
      if( aData.parentID ) hashTable[aData.parentID].childNodes.push(hashTable[aData.ID])
      else dataTree.push(hashTable[aData.ID])
    } )
    return dataTree
}

Here is a test, it might help you to understand how the solution works :

这是一个测试，它可能会帮助您了解解决方案的工作原理：

it('creates a correct shape of dataTree', () => {

    let dataSet = [
        {
            "ID": 1,
            "Phone": "[phone]",
            "City": "Coevorden",
            "Name": "Grady"
        },
        {
            "ID": 2,
            "parentID": 1,
            "Phone": "[phone]",
            "City": "Che?m",
            "Name": "Scarlet"
        }
    ]

    let expectedDataTree = [ 
    {
            "ID": 1,
            "Phone": "[phone]",
            "City": "Coevorden",
            "Name": "Grady",
            childNodes : [
                {
                    "ID": 2,
                    "parentID": 1,
                    "Phone": "[phone]",
                    "City": "Che?m",
                    "Name": "Scarlet",
                    childNodes : []
                }
            ]
    } 
    ]

  expect( createDataTree(dataSet) ).toEqual(expectedDataTree)
});

回答by alexandru.pausan

Had the same problem, but I could not be certain that the data was sorted or not. I could not use a 3rd party library so this is just vanilla Js; Input data can be taken from @Stephen's example;

有同样的问题，但我无法确定数据是否已排序。我无法使用 3rd 方库，所以这只是普通的 Js；输入数据可以从@Stephen 的例子中获取；

 var arr = [
        {'id':1 ,'parentid' : 0},
        {'id':4 ,'parentid' : 2},
        {'id':3 ,'parentid' : 1},
        {'id':5 ,'parentid' : 0},
        {'id':6 ,'parentid' : 0},
        {'id':2 ,'parentid' : 1},
        {'id':7 ,'parentid' : 4},
        {'id':8 ,'parentid' : 1}
      ];
    function unflatten(arr) {
      var tree = [],
          mappedArr = {},
          arrElem,
          mappedElem;

      // First map the nodes of the array to an object -> create a hash table.
      for(var i = 0, len = arr.length; i < len; i++) {
        arrElem = arr[i];
        mappedArr[arrElem.id] = arrElem;
        mappedArr[arrElem.id]['children'] = [];
      }


      for (var id in mappedArr) {
        if (mappedArr.hasOwnProperty(id)) {
          mappedElem = mappedArr[id];
          // If the element is not at the root level, add it to its parent array of children.
          if (mappedElem.parentid) {
            mappedArr[mappedElem['parentid']]['children'].push(mappedElem);
          }
          // If the element is at the root level, add it to first level elements array.
          else {
            tree.push(mappedElem);
          }
        }
      }
      return tree;
    }

var tree = unflatten(arr);
document.body.innerHTML = "<pre>" + (JSON.stringify(tree, null, " "))

JS Fiddle

JS小提琴

Flat Array to Tree

平面数组到树

回答by shekhardtu

Use this ES6 approach. Works like charm

使用这种 ES6 方法。像魅力一样工作

// Data Set
// One top level comment 
const comments = [{
    id: 1,
    parent_id: null
}, {
    id: 2,
    parent_id: 1
}, {
    id: 3,
    parent_id: 1
}, {
    id: 4,
    parent_id: 2
}, {
    id: 5,
    parent_id: 4
}];

const nest = (items, id = null, link = 'parent_id') =>
  items
    .filter(item => item[link] === id)
    .map(item => ({ ...item, children: nest(items, item.id) }));

console.log(
  nest(comments)
)

回答by William Leung

a more simple function list-to-tree-lite

一个更简单的函数list-to-tree-lite

npm install list-to-tree-lite

npm install list-to-tree-lite

listToTree(list)

listToTree(list)

source:

来源：

function listToTree(data, options) {
    options = options || {};
    var ID_KEY = options.idKey || 'id';
    var PARENT_KEY = options.parentKey || 'parent';
    var CHILDREN_KEY = options.childrenKey || 'children';

    var tree = [],
        childrenOf = {};
    var item, id, parentId;

    for (var i = 0, length = data.length; i < length; i++) {
        item = data[i];
        id = item[ID_KEY];
        parentId = item[PARENT_KEY] || 0;
        // every item may have children
        childrenOf[id] = childrenOf[id] || [];
        // init its children
        item[CHILDREN_KEY] = childrenOf[id];
        if (parentId != 0) {
            // init its parent's children object
            childrenOf[parentId] = childrenOf[parentId] || [];
            // push it into its parent's children object
            childrenOf[parentId].push(item);
        } else {
            tree.push(item);
        }
    };

    return tree;
}

jsfiddle

提琴手

回答by Iman Bahrampour

You can handle this question with just two line coding:

您只需使用两行代码即可处理此问题：

_(flatArray).forEach(f=>
           {f.nodes=_(flatArray).filter(g=>g.parentId==f.id).value();});

var resultArray=_(flatArray).filter(f=>f.parentId==null).value();

Test Online(see the browser console for created tree)

在线测试（参见浏览器控制台创建树）

Requirements:

要求：

1- Install lodash 4 (a Javascript library for manipulating objects and collections with performant methods => like the Linq in c#) Lodash

1- 安装 lodash 4（一个用于使用高性能方法操作对象和集合的 Javascript 库 => 就像 c# 中的 Linq）Lodash

2- A flatArray like below:

2- 如下所示的 flatArray：

    var flatArray=
    [{
      id:1,parentId:null,text:"parent1",nodes:[]
    }
   ,{
      id:2,parentId:null,text:"parent2",nodes:[]
    }
    ,
    {
      id:3,parentId:1,text:"childId3Parent1",nodes:[]
    }
    ,
    {
      id:4,parentId:1,text:"childId4Parent1",nodes:[]
    }
    ,
    {
      id:5,parentId:2,text:"childId5Parent2",nodes:[]
    }
    ,
    {
      id:6,parentId:2,text:"childId6Parent2",nodes:[]
    }
    ,
    {
      id:7,parentId:3,text:"childId7Parent3",nodes:[]
    }
    ,
    {
      id:8,parentId:5,text:"childId8Parent5",nodes:[]
    }];

Thank Mr. Bakhshabadi

感谢 Bakhshabadi 先生

Good luck

祝你好运

回答by DenQ

It may be useful package list-to-treeInstall:

包列表到树安装可能很有用：

bower install list-to-tree --save

or

或者

npm install list-to-tree --save

For example, have list:

例如，有列表：

var list = [
  {
    id: 1,
    parent: 0
  }, {
    id: 2,
    parent: 1
  }, {
    id: 3,
    parent: 1
  }, {
    id: 4,
    parent: 2
  }, {
    id: 5,
    parent: 2
  }, {
    id: 6,
    parent: 0
  }, {
    id: 7,
    parent: 0
  }, {
    id: 8,
    parent: 7
  }, {
    id: 9,
    parent: 8
  }, {
    id: 10,
    parent: 0
  }
];

Use package list-to-tree:

使用包列表到树：

var ltt = new LTT(list, {
  key_id: 'id',
  key_parent: 'parent'
});
var tree = ltt.GetTree();

Result:

结果：

[{
  "id": 1,
  "parent": 0,
  "child": [
    {
      "id": 2,
      "parent": 1,
      "child": [
        {
          "id": 4,
          "parent": 2
        }, {
          "id": 5, "parent": 2
        }
      ]
    },
    {
      "id": 3,
      "parent": 1
    }
  ]
}, {
  "id": 6,
  "parent": 0
}, {
  "id": 7,
  "parent": 0,
  "child": [
    {
      "id": 8,
      "parent": 7,
      "child": [
        {
          "id": 9,
          "parent": 8
        }
      ]
    }
  ]
}, {
  "id": 10,
  "parent": 0
}];

回答by Elias Rabl

I've written a test script to evaluate the performance of the two most general solutions (meaning that the input does not have to be sorted beforehand and that the code does not depend on third party libraries), proposed by users shekhardtu (see answer) and FurkanO (see answer).

我编写了一个测试脚本来评估用户 shekhardtu 提出的两个最通用的解决方案的性能（意味着不必预先对输入进行排序并且代码不依赖于第三方库）（请参阅答案）和 FurkanO（见答案）。

http://playcode.io/316025?tabs=console&script.js&output

http://playcode.io/316025?tabs=console&script.js&output

FurkanO's solution seems to be the fastest.

FurkanO 的解决方案似乎是最快的。

/*
** performance test for https://stackoverflow.com/questions/18017869/build-tree-array-from-flat-array-in-javascript
*/

// Data Set (e.g. nested comments)
var comments = [{
    id: 1,
    parent_id: null
}, {
    id: 2,
    parent_id: 1
}, {
    id: 3,
    parent_id: 4
}, {
    id: 4,
    parent_id: null
}, {
    id: 5,
    parent_id: 4
}];

// add some random entries
let maxParentId = 10000;
for (let i=6; i<=maxParentId; i++)
{
  let randVal = Math.floor((Math.random() * maxParentId) + 1);
  comments.push({
    id: i,
    parent_id: (randVal % 200 === 0 ? null : randVal)
  });
}

// solution from user "shekhardtu" (https://stackoverflow.com/a/55241491/5135171)
const nest = (items, id = null, link = 'parent_id') =>
  items
    .filter(item => item[link] === id)
    .map(item => ({ ...item, children: nest(items, item.id) }));
;

// solution from user "FurkanO" (https://stackoverflow.com/a/40732240/5135171)
const createDataTree = dataset => {
    let hashTable = Object.create(null)
    dataset.forEach( aData => hashTable[aData.id] = { ...aData, children : [] } )
    let dataTree = []
    dataset.forEach( aData => {
      if( aData.parent_id ) hashTable[aData.parent_id].children.push(hashTable[aData.id])
      else dataTree.push(hashTable[aData.id])
    } )
    return dataTree
};


/*
** lets evaluate the timing for both methods
*/
let t0 = performance.now();
let createDataTreeResult = createDataTree(comments);
let t1 = performance.now();
console.log("Call to createDataTree took " + Math.floor(t1 - t0) + " milliseconds.");

t0 = performance.now();
let nestResult = nest(comments);
t1 = performance.now();
console.log("Call to nest took " + Math.floor(t1 - t0) + " milliseconds.");




//console.log(nestResult);
//console.log(createDataTreeResult);

// bad, but simple way of comparing object equality
console.log(JSON.stringify(nestResult)===JSON.stringify(createDataTreeResult));

回答by Nina Scholz

This is a proposal for unordered items. This function works with a single loop and with a hash table and collects all items with their id. If a root node is found, then the object is added to the result array.

这是对无序项目的建议。此函数使用单个循环和哈希表，并使用它们的id. 如果找到根节点，则将该对象添加到结果数组中。

function getTree(data, root) {
    var o = {};
    data.forEach(function (a) {
        if (o[a.id] && o[a.id].children) {
            a.children = o[a.id].children;
        }
        o[a.id] = a;
        o[a.parentId] = o[a.parentId] || {};
        o[a.parentId].children = o[a.parentId].children || [];
        o[a.parentId].children.push(a);
    });
    return o[root].children;
}

var data = { People: [{ id: "12", parentId: "0", text: "Man", level: "1", children: null }, { id: "6", parentId: "12", text: "Boy", level: "2", children: null }, { id: "7", parentId: "12", text: "Other", level: "2", children: null }, { id: "9", parentId: "0", text: "Woman", level: "1", children: null }, { id: "11", parentId: "9", text: "Girl", level: "2", children: null }], Animals: [{ id: "5", parentId: "0", text: "Dog", level: "1", children: null }, { id: "8", parentId: "5", text: "Puppy", level: "2", children: null }, { id: "10", parentId: "13", text: "Cat", level: "1", children: null }, { id: "14", parentId: "13", text: "Kitten", level: "2", children: null }] },
    tree = Object.keys(data).reduce(function (r, k) {
        r[k] = getTree(data[k], '0');
        return r;
    }, {});

console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }