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

Question

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

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

当然，这只能获得第一级子级(根节点的直接子级)。它需要某种程度的递归，但我不知道如何做到这一点。

Answer 1

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

Array.prototype.reduce具有足够的灵活性来完成这一任务。如果您不熟悉Array.prototype.reduce，我推荐读这个。您可以通过执行以下操作来完成这一任务。

这里有两个依赖递归的函数：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)

​

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

​

Answer 3

假设平面项数组总是按照您的情况排序(父节点在子节点之前排序)。下面的代码应该可以完成这项工作。

首先，我在没有count属性的情况下构建树，使用数组上的reduce来构建一个映射，以跟踪每个节点，并将父节点链接到子节点：

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值。最后一个相反的情况是在这里进行排序，就像在您的问题:)。