从扁平的对象数组构建对象树形数组

Question

我希望能够从扁平数组中构建一棵树状数组：

以下是扁平数组：

nodes = [
    {id: 1, pid: 0, name: "kpittu"},
    {id: 2, pid: 0, name: "news"},
    {id: 3, pid: 0, name: "menu"},
    {id: 4, pid: 3, name: "node"},
    {id: 5, pid: 4, name: "subnode"},
    {id: 6, pid: 1, name: "cace"}
];

我希望将其转换为以下数组：

NB: id = 节点ID; pid = 父节点ID。

nodes = [{
    id: 1,
    name: 'kpittu',
    childs: [{
        id: 6,
        name: 'cace'
    }]
}, {
    id: 2,
    name: 'news'
}, {
    id: 3,
    name: 'menu',
    childs: [{
        id: 4,
        name: 'node',
        childs: [{
            id: 5,
            name: 'subnode'
        }]
    }]
}];

我尝试使用递归函数来实现期望的结果，但我正在寻找更好的方法。谢谢您的回复。

- Salim Ibrohimi

---

请添加您的功能。将以下与编程相关的内容从英语翻译成中文。仅返回翻译后的文本。 - Nina Scholz

建议，如果你自己无法解决这个问题，就无法学习或练习递归知识，相反，回答这个问题的人会更有收获。 - asdf_enel_hak

Answer 1

你可以使用哈希表，在每个循环中将id和pid作为连接的节点。

这个方案也适用于未排序的数据。

var nodes = [{ id: 6, pid: 1, name: "cace" }, { id: 1, pid: 0, name: "kpittu" }, { id: 2, pid: 0, name: "news" }, { id: 3, pid: 0, name: "menu" }, { id: 4, pid: 3, name: "node" }, { id: 5, pid: 4, name: "subnode" }],
    tree = function (data, root) {
        var r = [], o = {};
        data.forEach(function (a) {
            if (o[a.id] && o[a.id].children) {
                a.children = o[a.id] && o[a.id].children;
            }
            o[a.id] = a;
            if (a.pid === root) {
                r.push(a);
            } else {
                o[a.pid] = o[a.pid] || {};
                o[a.pid].children = o[a.pid].children || [];
                o[a.pid].children.push(a);
            }
        });
        return r;
    }(nodes, 0);

console.log(tree);

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

- Nina Scholz

---

你能否更新代码以处理一种轻微变体？在这种情况下，没有父级ID。相反，假定如果深度低于或等于前一个列表元素，则其父级是其前任。 - SumNeuron

@SumNeuron，请添加一个新问题并尝试回答。 - Nina Scholz

将 JavaScript 平面列表转换为树形结构（无需父 ID） - SumNeuron

Answer 2

你也可以使用在ES6中引入的Map对象。

let nodes = [
  { id: 1, pid: 0, name: "kpittu" },
  { id: 2, pid: 0, name: "news" },
  { id: 3, pid: 0, name: "menu" },
  { id: 4, pid: 3, name: "node" },
  { id: 5, pid: 4, name: "subnode" },
  { id: 6, pid: 1, name: "cace" }
];

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.pid) {
      let parentItem = arrMap.get(item.pid);

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

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

  return tree;
}

let tree = toTree(nodes);

console.log(tree);

- Yusufbek

Answer 3

使用Array#reduce和一个辅助对象进行迭代：

var nodes = [
  {id: 1, pid: 0, name: "kpittu"},
  {id: 2, pid: 0, name: "news"},
  {id: 3, pid: 0, name: "menu"},
  {id: 4, pid: 3, name: "node"},
  {id: 5, pid: 4, name: "subnode"},
  {id: 6, pid: 1, name: "cace"}
];

const helper = nodes.reduce((h, o) => (h[o.id] = Object.assign({}, o), h), Object.create(null));

const tree = nodes.reduce((t, node) => {
  const current = helper[node.id];
  
  if(current.pid === 0) { // if it doesn't have a parent push to root
    t.push(current);
  } else {
    helper[node.pid].children || (helper[node.pid].children = []) // add the children array to the parent, if it doesn't exist
    helper[node.pid].children.push(current); // push the current item to the parent children array
  }
  
  return t;
}, []);

console.log(tree);

- Ori Drori