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

问题描述 投票：2回答：4

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

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

但是，这仅获得第一级子级（根节点的直接子级）。它以某种方式需要递归，但是我不知道如何实现。

javascript typescript recursion nested
4个回答
3
投票

不对展平数组的顺序或嵌套对象的深度进行任何假设：

Array.prototype.reduce足够灵活以完成此操作。如果您不熟悉Array.prototype.reduce，建议您使用reading this。您可以通过执行以下操作来完成此操作。

我这里有两个依赖递归的函数：findParent和checkLeftOvers。 findParent尝试查找父对象，并根据是否找到它返回true或false。在我的化简器中，如果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)
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();

我只是反转数组以首先获得所有子项（就像在后置DFS中一样），并计算count值。最后一个相反的地方就是按照您的问题进行排序：）。

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

这可能不是性能最高的解决方案，根据输入的预期形状，可能需要进行一些调整，但这是一种干净易懂的解决方案。

0
投票

您可以为树采取一个单循环并存储子级与父级之间以及父级与子级之间的关系的标准方法。

对于具有根属性，您需要进行其他检查。

然后采取迭代和递归的方法获得计数。

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; }
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.