将节点数组转换为树

ES6函数转换数组节点(由父ID相关)到树结构:

/**
 * Convert nodes list related by parent ID - to tree.
 * @syntax getTree(nodesArray [, rootID [, propertyName]])
 *
 * @param {Array} arr   Array of nodes
 * @param {integer} id  Defaults to 0
 * @param {string} p    Property name. Defaults to "parent_id"
 * @returns {Object}    Nodes tree
 */

const getTree = (arr, p = "parent_id") => arr.reduce((o, n) => {

  if (!o[n.id]) o[n.id] = {};
  if (!o[n[p]]) o[n[p]] = {};
  if (!o[n[p]].nodes) o[n[p]].nodes= [];
  if (o[n.id].nodes) n.nodes= o[n.id].nodes;

  o[n[p]].nodes.push(n);
  o[n.id] = n;

  return o;
}, {});

从节点树生成HTML列表

有了我们的树，这里有一个递归函数来构建UL > LI元素:

/**
 * Convert Tree structure to UL>LI and append to Element
 * @syntax getTree(treeArray [, TargetElement [, onLICreatedCallback ]])
 *
 * @param {Array} tree Tree array of nodes
 * @param {Element} el HTMLElement to insert into
 * @param {function} cb Callback function called on every LI creation
 */

const treeToHTML = (tree, el, cb) => el.append(tree.reduce((ul, n) => {
  const li = document.createElement('li');

  if (cb) cb.call(li, n);
  if (n.nodes?.length) treeToHTML(n.nodes, li, cb);

  ul.append(li);
  return ul;
}, document.createElement('ul')));

演示时间

下面是一个使用上述两个函数的线性节点数组的例子:

const getTree = (arr, p = "parent_id") => arr.reduce((o, n) => { if (!o[n.id]) o[n.id] = {}; if (!o[n[p]]) o[n[p]] = {}; if (!o[n[p]].nodes) o[n[p]].nodes = []; if (o[n.id].nodes) n.nodes = o[n.id].nodes; o[n[p]].nodes.push(n); o[n.id] = n; return o; }, {}); const treeToHTML = (tree, el, cb) => el.append(tree.reduce((ul, n) => { const li = document.createElement('li'); if (cb) cb.call(li, n); if (n.nodes?.length) treeToHTML(n.nodes, li, cb); ul.append(li); return ul; }, document.createElement('ul'))); // DEMO TIME: const nodesList = [ {id: 10, parent_id: 4, text: "Item 10"}, // PS: Order does not matters {id: 1, parent_id: 0, text: "Item 1"}, {id: 4, parent_id: 0, text: "Item 4"}, {id: 3, parent_id: 5, text: "Item 3"}, {id: 5, parent_id: 4, text: "Item 5"}, {id: 2, parent_id: 1, text: "Item 2"}, ]; const myTree = getTree(nodesList)[0].nodes; // Get nodes of Root (0) treeToHTML(myTree, document.querySelector("#tree"), function(node) { this.textContent = `(${node.parent_id} ${node.id}) ${node.text}`; this._node = node; this.addEventListener('click', clickHandler); }); function clickHandler(ev) { if (ev.target !== this) return; console.clear(); console.log(this._node.id); }; <div id="tree"></div>

下面是我根据上面的答案创建的一个简单的帮助函数，为通天塔环境量身定制:

import { isEmpty } from 'lodash'

export default function unflattenEntities(entities, parent = {id: null}, tree = []) {

  let children = entities.filter( entity => entity.parent_id == parent.id)

  if (!isEmpty( children )) {
    if ( parent.id == null ) {
      tree = children
    } else {
      parent['children'] = children
    }
    children.map( child => unflattenEntities( entities, child ) )
  }

  return tree

}

正如@Sander提到的，@Halcyon的答案假设一个预先排序的数组，下面的不是。(然而，它假设你已经加载了underscore.js -尽管它可以用香草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>

需求

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

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

我已经编写了一个测试脚本来评估用户shekhardtu(见答案)和FurkanO(见答案)提出的两种最通用的解决方案的性能(意味着输入不需要事先排序，代码不依赖于第三方库)。

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

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

这是我在一个react项目中使用的

// ListToTree.js
import _filter from 'lodash/filter';
import _map from 'lodash/map';

export default (arr, parentIdKey) => _map(_filter(arr, ar => !ar[parentIdKey]), ar => ({
  ...ar,
  children: _filter(arr, { [parentIdKey]: ar.id }),
}));

用法:

// somewhere.js
import ListToTree from '../Transforms/ListToTree';

const arr = [
   {
      "id":"Bci6XhCLZKPXZMUztm1R",
      "name":"Sith"
   },
   {
      "id":"C3D71CMmASiR6FfDPlEy",
      "name":"Luke",
      "parentCategoryId":"ltatOlEkHdVPf49ACCMc"
   },
   {
      "id":"aS8Ag1BQqxkO6iWBFnsf",
      "name":"Obi Wan",
      "parentCategoryId":"ltatOlEkHdVPf49ACCMc"
   },
   {
      "id":"ltatOlEkHdVPf49ACCMc",
      "name":"Jedi"
   },
   {
      "id":"pw3CNdNhnbuxhPar6nOP",
      "name":"Palpatine",
      "parentCategoryId":"Bci6XhCLZKPXZMUztm1R"
   }
];
const response = ListToTree(arr, 'parentCategoryId');

输出:

[
   {
      "id":"Bci6XhCLZKPXZMUztm1R",
      "name":"Sith",
      "children":[
         {
            "id":"pw3CNdNhnbuxhPar6nOP",
            "name":"Palpatine",
            "parentCategoryId":"Bci6XhCLZKPXZMUztm1R"
         }
      ]
   },
   {
      "id":"ltatOlEkHdVPf49ACCMc",
      "name":"Jedi",
      "children":[
         {
            "id":"C3D71CMmASiR6FfDPlEy",
            "name":"Luke",
            "parentCategoryId":"ltatOlEkHdVPf49ACCMc"
         },
         {
            "id":"aS8Ag1BQqxkO6iWBFnsf",
            "name":"Obi Wan",
            "parentCategoryId":"ltatOlEkHdVPf49ACCMc"
         }
      ]
   }
]```

我使用@FurkanO answer并创建了一个可以用于任何对象类型的泛型函数，我还用TypeScript写了这个函数，我更喜欢它，因为它有自动补全功能。

实现:

1. Javascript:

export const flatListToTree = (flatList, idPath, parentIdPath, childListPath, isParent) => {
  const rootParents = [];
  const map = {};
  for (const item of flatList) {
    if (!item[childListPath]) item[childListPath] = [];
    map[item[idPath]] = item;
  }
  for (const item of flatList) {
    const parentId = item[parentIdPath];
    if (isParent(item)) {
      rootParents.push(item);
    } else {
      const parentItem = map[parentId];
      parentItem[childListPath].push(item);
    }
  }
  return rootParents;
};

2. TypeScript:我假设“T”类型有一个属性的孩子列表，你可以改变“childListPath”是一个字符串而不是“keyof T”如果你有不同的用例。

export const flatListToTree = <T>(
  flatList: T[],
  idPath: keyof T,
  parentIdPath: keyof T,
  childListPath: keyof T,
  isParent: (t: T) => boolean,
) => {
  const rootParents: T[] = [];
  const map: any = {};
  for (const item of flatList) {
    if (!(item as any)[childListPath]) (item as any)[childListPath] = [];
    map[item[idPath]] = item;
  }
  for (const item of flatList) {
    const parentId = item[parentIdPath];
    if (isParent(item)) {
      rootParents.push(item);
    } else {
      const parentItem = map[parentId];
      parentItem[childListPath].push(item);
    }
  }
  return rootParents;
};

使用方法:

  const nodes = [
    { id: 2, pid: undefined, children: [] },
    { id: 3, pid: 2 },
    { id: 4, pid: 2 },
    { id: 5, pid: 4 },
    { id: 6, pid: 5 },
    { id: 7, pid: undefined },
    { id: 8, pid: 7 },
  ];
  
  const result = flatListToTree(nodes, "id", "pid", "children", node => node.pid === undefined);