一个更简单的从列表到树的函数

NPM安装列表到树精简版

listToTree(列表)

来源:

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

斯菲德尔

我的解决方案:

允许双向映射(根到叶，叶到根) 返回所有节点、根节点和叶节点 一次数据传递和非常快的性能 香草Javascript

/**
 * 
 * @param data items array
 * @param idKey item's id key (e.g., item.id)
 * @param parentIdKey item's key that points to parent (e.g., item.parentId)
 * @param noParentValue item's parent value when root (e.g., item.parentId === noParentValue => item is root)
 * @param bidirectional should parent reference be added
 */
function flatToTree(data, idKey, parentIdKey, noParentValue = null, bidirectional = true) {
  const nodes = {}, roots = {}, leaves = {};

  // iterate over all data items
  for (const i of data) {

    // add item as a node and possibly as a leaf
    if (nodes[i[idKey]]) { // already seen this item when child was found first
      // add all of the item's data and found children
      nodes[i[idKey]] = Object.assign(nodes[i[idKey]], i);
    } else { // never seen this item
      // add to the nodes map
      nodes[i[idKey]] = Object.assign({ $children: []}, i);
      // assume it's a leaf for now
      leaves[i[idKey]] = nodes[i[idKey]];
    }

    // put the item as a child in parent item and possibly as a root
    if (i[parentIdKey] !== noParentValue) { // item has a parent
      if (nodes[i[parentIdKey]]) { // parent already exist as a node
        // add as a child
        (nodes[i[parentIdKey]].$children || []).push( nodes[i[idKey]] );
      } else { // parent wasn't seen yet
        // add a "dummy" parent to the nodes map and put the item as its child
        nodes[i[parentIdKey]] = { $children: [ nodes[i[idKey]] ] };
      }
      if (bidirectional) {
        // link to the parent
        nodes[i[idKey]].$parent = nodes[i[parentIdKey]];
      }
      // item is definitely not a leaf
      delete leaves[i[parentIdKey]];
    } else { // this is a root item
      roots[i[idKey]] = nodes[i[idKey]];
    }
  }
  return {roots, nodes, leaves};
}

使用的例子:

const data = [{id: 2, parentId: 0}, {id: 1, parentId: 2} /*, ... */];
const { nodes, roots, leaves } = flatToTree(data, 'id', 'parentId', 0);

类似问题的答案:

https://stackoverflow.com/a/61575152/7388356

更新

你可以使用ES6中引入的Map对象。基本上，你不再通过遍历数组来寻找父元素，你只需要从数组中通过父元素的id来获取父元素就像你在数组中通过索引来获取元素一样。

下面是一个简单的例子:

const 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
  }
];

function toTree(arr) {
  let arrMap = new Map(arr.map(item => [item.id, item]));
  let tree = [];

  for (let i = 0; i < arr.length; i++) {
    let item = arr[i];

    if (item.parentId !== "0") {
      let parentItem = arrMap.get(item.parentId);

      if (parentItem) {
        let { children } = parentItem;

        if (children) {
          parentItem.children.push(item);
        } else {
          parentItem.children = [item];
        }
      }
    } else {
      tree.push(item);
    }
  }

  return tree;
}

let tree = toTree(people);

console.log(tree);

Based on @FurkanO's answer, I created another version that does not mutate the origial data (like @Dac0d3r requested). I really liked @shekhardtu's answer, but realized it had to filter through the data many times. I thought a solution could be to use FurkanO's answer by copying the data first. I tried my version in jsperf, and the results where unfortunately (very) bleak... It seems like the accepted answer is really a good one! My version is quite configurable and failsafe though, so I share it with you guys anyway; here is my contribution:

function unflat(data, options = {}) {
    const { id, parentId, childrenKey } = {
        id: "id",
        parentId: "parentId",
        childrenKey: "children",
        ...options
    };
    const copiesById = data.reduce(
        (copies, datum) => ((copies[datum[id]] = datum) && copies),
        {}
    );
    return Object.values(copiesById).reduce(
        (root, datum) => {
            if ( datum[parentId] && copiesById[datum[parentId]] ) {
                copiesById[datum[parentId]][childrenKey] = [ ...copiesById[datum[parentId]][childrenKey], datum ];
            } else {
                root = [ ...root, datum ];
            }
            return root
        }, []
    );
}

const data = [
    {
        "account": "10",
        "name": "Konto 10",
        "parentAccount": null
    },{
        "account": "1010",
        "name": "Konto 1010",
        "parentAccount": "10"
    },{
        "account": "10101",
        "name": "Konto 10101",
        "parentAccount": "1010"
    },{
        "account": "10102",
        "name": "Konto 10102",
        "parentAccount": "1010"
    },{
        "account": "10103",
        "name": "Konto 10103",
        "parentAccount": "1010"
    },{
        "account": "20",
        "name": "Konto 20",
        "parentAccount": null
    },{
        "account": "2020",
        "name": "Konto 2020",
        "parentAccount": "20"
    },{
        "account": "20201",
        "name": "Konto 20201",
        "parentAccount": "2020"
    },{
        "account": "20202",
        "name": "Konto 20202",
        "parentAccount": "2020"
    }
];

const options = {
    id: "account",
    parentId: "parentAccount",
    childrenKey: "children"
};

console.log(
    "Hierarchical tree",
    unflat(data, options)
);

通过options参数，可以配置将哪个属性用作id或父id。也可以配置children属性的名称，如果有人想要“childNodes”:[]或其他什么。

OP可以简单地使用默认选项:

input.People = unflat(input.People);

如果父对象id是假的(null, undefined或其他假的值)或父对象不存在，我们认为该对象是根节点。

ES6地图版本:

getTreeData = (items) => {
  if (items && items.length > 0) {
    const data = [];
    const map = {};
    items.map((item) => {
      const id = item.id; // custom id selector !!!
      if (!map.hasOwnProperty(id)) {
        // in case of duplicates
        map[id] = {
          ...item,
          children: [],
        };
      }
    });
    for (const id in map) {
      if (map.hasOwnProperty(id)) {
        let mappedElem = [];
        mappedElem = map[id];
        /// parentId : use custom id selector for parent
        if (
          mappedElem.parentId &&
          typeof map[mappedElem.parentId] !== "undefined"
        ) {
          map[mappedElem.parentId].children.push(mappedElem);
        } else {
          data.push(mappedElem);
        }
      }
    }
    return data;
  }
  return [];
};

/// use like this :

const treeData = getTreeData(flatList);

我的typescript解决方案，可能对你有帮助:

type ITreeItem<T> = T & {
    children: ITreeItem<T>[],
};

type IItemKey = string | number;

function createTree<T>(
    flatList: T[],
    idKey: IItemKey,
    parentKey: IItemKey,
): ITreeItem<T>[] {
    const tree: ITreeItem<T>[] = [];

    // hash table.
    const mappedArr = {};
    flatList.forEach(el => {
        const elId: IItemKey = el[idKey];

        mappedArr[elId] = el;
        mappedArr[elId].children = [];
    });

    // also you can use Object.values(mappedArr).forEach(...
    // but if you have element which was nested more than one time
    // you should iterate flatList again:
    flatList.forEach((elem: ITreeItem<T>) => {
        const mappedElem = mappedArr[elem[idKey]];

        if (elem[parentKey]) {
            mappedArr[elem[parentKey]].children.push(elem);
        } else {
            tree.push(mappedElem);
        }
    });

    return tree;
}

用法示例:

createTree(yourListData, 'id', 'parentId');