将扁平对象数组转换为嵌套对象

Question

将扁平对象数组转换为嵌套对象

5

我可以帮助您进行翻译。以下是一个数组（实际上来自后端服务）：

我有以下数组（实际上来自后端服务）：

const flat: Item[] = [
    { id: 'a', name: 'Root 1', parentId: null },
    { id: 'b', name: 'Root 2', parentId: null },
    { id: 'c', name: 'Root 3', parentId: null },

    { id: 'a1', name: 'Item 1', parentId: 'a' },
    { id: 'a2', name: 'Item 1', parentId: 'a' },

    { id: 'b1', name: 'Item 1', parentId: 'b' },
    { id: 'b2', name: 'Item 2', parentId: 'b' },
    { id: 'b2-1', name: 'Item 2-1', parentId: 'b2' },
    { id: 'b2-2', name: 'Item 2-2', parentId: 'b2' },
    { id: 'b3', name: 'Item 3', parentId: 'b' },

    { id: 'c1', name: 'Item 1', parentId: 'c' },
    { id: 'c2', name: 'Item 2', parentId: 'c' }
];

其中Item是：

interface Item {
    id: string;
    name: string;
    parentId: string;
};

为了兼容显示树形（类似文件夹）视图的组件，它需要被转换为：

const treeData: NestedItem[] = [
    {
        id: 'a',
        name: 'Root 1',
        root: true,
        count: 2,
        children: [
          {
            id: 'a1',
            name: 'Item 1'
          },
          {
            id: 'a2',
            name: 'Item 2'
          }
        ]
    },
    {
        id: 'b',
        name: 'Root 2',
        root: true,
        count: 5, // number of all children (direct + children of children)
        children: [
          {
            id: 'b1',
            name: 'Item 1'
          },
          {
            id: 'b2',
            name: 'Item 2',
            count: 2,
            children: [
                { id: 'b2-1', name: 'Item 2-1' },
                { id: 'b2-2', name: 'Item 2-2' },
            ]
          },
          {
            id: 'b3',
            name: 'Item 3'
          },
        ]
    },
    {
        id: 'c',
        name: 'Root 3',
        root: true,
        count: 2,
        children: [
          {
            id: 'c1',
            name: 'Item 1'
          },
          {
            id: 'c2',
            name: 'Item 2'
          }
        ]
    }
];

其中 NestedItem 是:

interface NestedItem {
    id: string;
    name: string;
    root?: boolean;
    count?: number;
    children?: NestedItem[];
}

到目前为止，我尝试的是类似于以下内容：

// Get roots first
const roots: NestedItem[] = flat
    .filter(item => !item.parentId)
    .map((item): NestedItem => {
        return { id: item.id, name: item.name, root: true }
    });

// Add "children" to those roots
const treeData = roots.map(node => {
    const children = flat
        .filter(item => item.parentId === node.id)
        .map(item => {
            return { id: item.id, name: item.name }
        });
    return {
        ...node,
        children,
        count: node.count ? node.count + children.length : children.length
    }
});

但是这只能获取第一级子节点（根节点的直接子节点）。它需要进行递归，但我不知道如何实现。

- MrCroft

8个回答

2

你可以采用标准方法来处理一棵树，只需使用一个循环即可存储子节点与父节点之间以及父节点与子节点之间的关系。为了获得根属性，您需要进行额外的检查。然后采用迭代和递归的方法来获取计数。

var data = [{ id: 'a', name: 'Root 1', parentId: null }, { id: 'b', name: 'Root 2', parentId: null }, { id: 'c', name: 'Root 3', parentId: null }, { id: 'a1', name: 'Item 1', parentId: 'a' }, { id: 'a2', name: 'Item 1', parentId: 'a' }, { id: 'b1', name: 'Item 1', parentId: 'b' }, { id: 'b2', name: 'Item 2', parentId: 'b' }, { id: 'b3', name: 'Item 3', parentId: 'b' }, { id: 'c1', name: 'Item 1', parentId: 'c' }, { id: 'c2', name: 'Item 2', parentId: 'c' }, { id: 'b2-1', name: 'Item 2-1', parentId: 'b2' }, { id: 'b2-2', name: 'Item 2-2', parentId: 'b2' },],
    tree = function (data, root) {

        function setCount(object) {
            return object.children
                ? (object.count = object.children.reduce((s, o) => s + 1 + setCount(o), 0))
                : 0;
        }                

        var t = {};
        data.forEach(o => {
            Object.assign(t[o.id] = t[o.id] || {}, o);
            t[o.parentId] = t[o.parentId] || {};
            t[o.parentId].children = t[o.parentId].children || [];
            t[o.parentId].children.push(t[o.id]);
            if (o.parentId === root) t[o.id].root = true;          // extra
        });

        setCount(t[root]);                                         // extra
        return t[root].children;
    }(data, null);

console.log(tree);

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

- Nina Scholz

1

假设平坦项数组始终按照您的情况进行排序（父节点在子节点之前排序），则下面的代码应该可以完成工作。首先，我使用数组上的 reduce 构建树，以构建一个映射来跟踪每个节点并将父节点链接到子节点，而不使用 count 属性。

type NestedItemMap = { [nodeId: string]: NestedItem };

let nestedItemMap: NestedItemMap = flat
    .reduce((nestedItemMap: NestedItemMap, item: Item): NestedItemMap => {

        // Create the nested item
        nestedItemMap[item.id] = {
            id: item.id,
            name: item.name
        }

        if(item.parentId == null){
            // No parent id, it's a root node
            nestedItemMap[item.id].root = true;
        }
        else{
            // Child node
            let parentItem: NestedItem = nestedItemMap[item.parentId];

            if(parentItem.children == undefined){
                // First child, create the children array
                parentItem.children = [];
                parentItem.count = 0;

            }

            // Add the child node in it's parent children
            parentItem.children.push(
                nestedItemMap[item.id]
            );
            parentItem.count++;
        }

        return nestedItemMap;
    }, {});

父节点在减少数组时总是首先出现，这确保了在构建子节点时父节点在nestedItemMap中可用。

这里有树，但没有count属性：

let roots: NestedItem[] = Object.keys(nestedItemMap)
    .map((key: string): NestedItem => nestedItemMap[key])
    .filter((item: NestedItem): boolean => item.root);

为了填充count属性，我个人更喜欢在树上执行后序深度优先搜索。但是在您的情况下，由于节点ID命名（排序后，父节点ID首先出现），您可以使用以下方法计算它们：

let roots: NestedItem[] = Object.keys(nestedItemMap)
    .map((key: string): NestedItem => nestedItemMap[key])
    .reverse()
    .map((item: NestedItem): NestedItem => {
        if(item.children != undefined){
            item.count = item.children
                .map((child: NestedItem): number => {
                    return 1 + (child.count != undefined ? child.count : 0);
                })
                .reduce((a, b) => a + b, 0);
        }

        return item;
    })
    .filter((item: NestedItem): boolean => item.root)
    .reverse();

我只是将数组反转以先获取所有子元素(类似于后序深度优先搜索)，并计算count值。最后一次反转只是为了按照您的问题排序 :).

- Rauks

1

也许这可以帮到你，输入是平面对象。

nestData = (data, parentId = '') => {
return data.reduce((result, fromData) => {
  const obj = Object.assign({}, fromData);

  if (parentId === fromData.parent_id) {
    const children = this.nestData(data, fromData.id);
    if (children.length) {
      obj.children = children;
    } else {
      obj.userData = [];
    }
    result.push(obj);
  }
  return result;
}, []);

};

- Quang Mẫn

这可能是从一个不同但相关的任务的代码中取出的。为了解决这个问题，需要对其进行清理。如果作为独立的代码，你需要从递归调用nestData中移除 this。你需要将 parent_id 改为 parentId，由于 userData 与此问题无关，因此可以删除 else 块。然而最大的问题在于它没有包括所要求的 count 或 root 属性。root 很容易解决，但是 count 则需要一些工作。一个相关的方法在另一个答案的最后更新中提到。 - Scott Sauyet

0

this.treeData = this.buildTreeData(
    flat.filter(f => !f.parentId), flat
);

private buildTreeData(datagroup: Item[], flat: Item[]): any[] {
    return datagroup.map((data) => {
        const items = this.buildTreeData(
            flat.filter((f) => f.parentId === data.id), flat
      );
      return {
          ...data,
          root: !data.parentId,
          count: items?.length || null
          children: items,
      };
  });
}

- timdo

请添加更多细节以扩展您的答案，例如工作代码或文档引用。 - cursorrux

0

你好，我尝试了Cody的推荐答案，但在数据未排序和嵌套数据的级别>2时遇到了一些问题。

在这个沙盒中： https://codesandbox.io/s/runtime-dew-g48sk?file=/src/index.js:1875-1890 我只是稍微改变了顺序（id=3被移到了列表的末尾），请看控制台，我们现在可以看到c只有一个子节点

我曾经遇到过另一个问题，即找不到父级，因为在findParent函数中，如果使用第一个参数为长度大于1的数组进行递归调用（例如，在以下情况下查找id=21的父级：

{id: 1,parentId: null, children: [
    {
      id: 10,
      parentId: 1,
      children: []
    },
    {
      id: 11,
      parentId: 1,
      children: [{
        id: 21...
      }]
    }
]}

将会失败，因为found变量被重置为false。

无论如何，我认为流本身很好，只需要一些小的修复和重命名，所以这是对我有用的东西，我删除了一些我没有使用的属性（例如counter），并添加了一些自己的属性（例如expanded），但显然完全没有关系，我也在使用TS（但我将所有类型都更改为any）：

class NestService {
  public nestSearchResultsToTree(flatItemsPath: any[]) {
    const nested = flatItemsPath.reduce(
      (
        initial: { nested: any[]; left: any[] },
        value: any,
        index: number,
        original: any
      ) => {
        if (value.parentId === null) {
          if (initial.left.length) this.checkLeftOvers(initial.left, value);
          initial.nested.push(value);
        } else {
          const parentFound = this.findParent(initial.nested, value);
          if (parentFound) this.checkLeftOvers(initial.left, value);
          else initial.left.push(value);
        }
        return index < original.length - 1 ? initial : initial.nested;
      },
      { nested: [], left: [] }
    );
    return nested;
  }

  private checkLeftOvers(leftOvers: any[], possibleParent: any) {
    for (let i = 0; i < leftOvers.length; i++) {
      const possibleChild = leftOvers[i];
      if (possibleChild.id === possibleParent.id) continue;
      if (possibleChild.parentId === possibleParent.id) {
        possibleParent.children
          ? possibleParent.children.push(possibleChild)
          : (possibleParent.children = [possibleChild]);
        possibleParent.expanded = true;
        possibleParent.isFetched = true;
        this.checkLeftOvers(leftOvers, possibleChild);
      }
    }
  }

  private findParent(
    possibleParents: any,
    child: any,
    isAlreadyFound?: boolean
  ): boolean {
    if (isAlreadyFound) return true;
    let found = false;
    for (let i = 0; i < possibleParents.length; i++) {
      const possibleParent = possibleParents[i];
      if (possibleParent.id === child.parentId) {
        possibleParent.expanded = true;
        possibleParent.isFetched = true;
        found = true;
        if (possibleParent.children) possibleParent.children.push(child);
        else possibleParent.children = [child];
        return true;
      } else if (possibleParent.children)
        found = this.findParent(possibleParent.children, child, found);
    }
    return found;
  }
}

- oriRas

0

另一种方法可能是这样的：

const countKids = (nodes) => 
  nodes.length + nodes.map(({children = []}) => countKids(children)).reduce((a, b) => a + b, 0)

const makeForest = (id, xs) => 
  xs .filter (({parentId}) => parentId == id)
     .map (({id, parentId, ...rest}) => {
       const kids = makeForest (id, xs)
       return {id, ...rest, ...(kids .length ? {count: countKids (kids), children: kids} : {})}
     })

const nest = (flat) =>
  makeForest (null, flat)
    .map ((node) => ({...node, root: true}))

const flat = [{id: "a", name: "Root 1", parentId: null}, {id: "b", name: "Root 2", parentId: null}, {id: "c", name: "Root 3", parentId: null}, {id: "a1", name: "Item 1", parentId: "a"}, {id: "a2", name: "Item 1", parentId: "a"}, {id: "b1", name: "Item 1", parentId: "b"}, {id: "b2", name: "Item 2", parentId: "b"}, {id: "b2-1", name: "Item 2-1", parentId: "b2"}, {id: "b2-2", name: "Item 2-2", parentId: "b2"}, {id: "b3", name: "Item 3", parentId: "b"}, {id: "c1", name: "Item 1", parentId: "c"}, {id: "c2", name: "Item 2", parentId: "c"}]

console .log (nest (flat))

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

主要函数（makeForest）查找所有ID与目标匹配的子项（最初为null），然后递归地对这些子项的ID执行相同的操作。

唯一的复杂性在于如果节点的子项为空，则不包括count或children。如果包含它们不是问题，则可以简化此过程。

- Scott Sauyet

0

如果您事先拥有这么多信息，那么可以更轻松地反向构建树形结构。由于您非常了解输入的形状以及它们之间的关系已经明确定义，因此可以轻松将其分成多个数组，并从底部开始构建。

function buildTree(arr: Item[]): NestedItem[] {
  /* first split the input into separate arrays based on their nested level */
  const roots = arr.filter(r => /^\w{1}$/.test(r.id));
  const levelOne = arr.filter(r => /^\w{1}\d{1}$/.test(r.id));
  const levelTwo = arr.filter(r => /^\w{1}\d{1}-\d{1}$/.test(r.id));

  /* then create the bottom most level based on their relationship to their parent*/
  const nested = levelOne.map(item => {
    const children = levelTwo.filter(c => c.parentId === item.id);
    if (children) {
      return {
        ...item,
        count: children.length,
        children
      };
    } else return item;
  });

  /* and finally do the same with the root items and return the result */
  return roots.map(item => {
    const children = nested.filter(c => c.parentId === item.id);
    if (children) {
      return {
        ...item,
        count: children.length,
        children,
        root: true
      };
    } else return { ...item, root: true };
  });
}

这可能不是最高效的解决方案，而且根据输入的预期形状需要进行一些调整，但它是一个干净且易读的解决方案。

- Robbie Milejczak

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cory Kleiser · Accepted Answer

不假设扁平化数组的顺序或嵌套对象的深度：

Array.prototype.reduce非常灵活，可以完成此操作。如果您不熟悉Array.prototype.reduce，我建议您阅读此文。您可以通过以下方式实现此目标。

这里有两个依赖于递归的函数：findParent和checkLeftOvers。 findParent试图找到对象的父级，并根据是否找到返回true或false。在我的reducer中，如果findParent返回false，则将当前值添加到剩余项数组中。如果findParent返回true，则调用checkLeftOvers查看剩余项数组中的任何对象是否是findParent刚刚添加的对象的子级。

注意：我将{ id: 'b2-2-1', name: 'Item 2-2-1', parentId: 'b2-2'}添加到flat数组中，以证明它可以深入到您想要的任何深度。我还重新排序了flat以证明这种情况也可以使用。希望这有所帮助。

const flat = [
    { id: 'a2', name: 'Item 1', parentId: 'a' },
    { id: 'b2-2-1', name: 'Item 2-2-1', parentId: 'b2-2'},
    { id: 'a1', name: 'Item 1', parentId: 'a' },
    { id: 'a', name: 'Root 1', parentId: null },
    { id: 'b', name: 'Root 2', parentId: null },
    { id: 'c', name: 'Root 3', parentId: null },
    { id: 'b1', name: 'Item 1', parentId: 'b' },
    { id: 'b2', name: 'Item 2', parentId: 'b' },
    { id: 'b2-1', name: 'Item 2-1', parentId: 'b2' },
    { id: 'b2-2', name: 'Item 2-2', parentId: 'b2' },
    { id: 'b3', name: 'Item 3', parentId: 'b' },
    { id: 'c1', name: 'Item 1', parentId: 'c' },
    { id: 'c2', name: 'Item 2', parentId: 'c' }
];

function checkLeftOvers(leftOvers, possibleParent){
  for (let i = 0; i < leftOvers.length; i++) {
    if(leftOvers[i].parentId === possibleParent.id) {
      delete leftOvers[i].parentId
      possibleParent.children ? possibleParent.children.push(leftOvers[i]) : possibleParent.children = [leftOvers[i]]
      possibleParent.count = possibleParent.children.length
      const addedObj = leftOvers.splice(i, 1)
      checkLeftOvers(leftOvers, addedObj[0])
    }
  }
}

function findParent(possibleParents, possibleChild) {
  let found = false
  for (let i = 0; i < possibleParents.length; i++) {
    if(possibleParents[i].id === possibleChild.parentId) {
      found = true
      delete possibleChild.parentId
      if(possibleParents[i].children) possibleParents[i].children.push(possibleChild)
      else possibleParents[i].children = [possibleChild]
      possibleParents[i].count = possibleParents[i].children.length
      return true
    } else if (possibleParents[i].children) found = findParent(possibleParents[i].children, possibleChild)
  } 
  return found;
}
 
 const nested = flat.reduce((initial, value, index, original) => {
   if (value.parentId === null) {
     if (initial.left.length) checkLeftOvers(initial.left, value)
     delete value.parentId
     value.root = true;
     initial.nested.push(value)
   }
   else {
      let parentFound = findParent(initial.nested, value)
      if (parentFound) checkLeftOvers(initial.left, value)
      else initial.left.push(value)
   }
   return index < original.length - 1 ? initial : initial.nested
 }, {nested: [], left: []})
 
console.log(nested)