如何按父子关系对嵌套对象中的元素进行分组？

我们有如下动态对象数组：

[
    {
        "object": "block",
        "id": "089cd0d8-ccbf-4e9e-97a6",
        "parent": {
            "type": "page_id",
            "page_id": "d4b96daf-47a3-4a04-b200"
        },
        "type": "child_database",
        "child_database": {
            "title": "Hero"
        }
    },
    {
        "object": "page",
        "id": "d3022361-96d2-4e15-999e",
        "parent": {
            "type": "database_id",
            "database_id": "089cd0d8-ccbf-4e9e-97a6"
        },
    },
    {
        "object": "block",
        "id": "a0cba166-1787-4e30-8cc3",
        "parent": {
            "type": "page_id",
            "page_id": "d3022361-96d2-4e15-999e"
        },
        "type": "heading_1",
        "heading_1": {
            "rich_text": [
                {
                    "type": "text",
                    "text": {
                        "content": "Introduction",
                        "link": null
                    },
                    "plain_text": "Introduction",
                    "href": null
                }
            ],
        }
    },
    {
        "object": "block",
        "id": "dbfdd892-8c04-4de3-bf0e",
        "parent": {
            "type": "page_id",
            "page_id": "d3022361-96d2-4e15-999e"
        },
        "type": "heading_2",
        "heading_2": {
            "rich_text": [
                {
                    "type": "text",
                    "text": {
                        "content": "This is introduction section",
                        "link": null
                    },
                    "plain_text": "This is introduction section",
                    "href": null
                }
            ],
        }
    }
]

每个对象都包含"parent"属性，需要基于父子关系重构该数组，将拥有相同父级的元素分组到child数组下。

期望输出 #

{
  "d4b96daf-47a3-4a04-b200": {
    "object": "block",
    "id": "089cd0d8-ccbf-4e9e-97a6",
    "type": "child_database",
    "child": [{
      "d3022361-96d2-4e15-999e": {
        "object": "page",
        "child": [{
            "a0cba166-1787-4e30-8cc3": {
              "object": "block",
              "type": "heading_1",
              "heading_1": {
                "rich_text": [{
                  "type": "text",
                  "text": {
                    "content": "Introduction",
                    "link": null
                  },
                  "plain_text": "Introduction",
                  "href": null
                }]
              }
            }
          },
          {
            "dbfdd892-8c04-4de3-bf0e": {
              "object": "block",
              "type": "heading_2",
              "heading_2": {
                "rich_text": [{
                  "type": "text",
                  "text": {
                    "content": "This is introduction section",
                    "link": null
                  },
                  "plain_text": "This is introduction section",
                  "href": null
                }]
              }
            }
          }
        ]
      }
    }]
  }
}

当前思路（卡壳中） #

/**
 * 遍历嵌套对象的生成器
 */
function* traverse(xs: any[] = []): any {
  for (let x of xs) {
    yield x
    yield* traverse(x.child || [])
  }
}

/**
 * 如果嵌套对象中存在符合条件的属性，返回对应节点
 */
const deepFind = (block: any, pred: any) => (obj: any) => {
  for (let node of traverse([obj])) {
    if (pred(node)) {
      return node
    }
  }
}

const findById = (block: any) => (obj: any) => deepFind(block, (o: any) => o[block.id])(obj)

export default async function group(pages: Page[]) {
  // 卡在这里了 🙏 
}

可以通过建立ID到节点的映射，再遍历每个节点将其挂载到父节点的child数组中，最后收集顶级节点（父节点不在数组中的节点）来实现：

type Item = {
  object: string;
  id: string;
  parent: {
    type: string;
    page_id?: string;
    database_id?: string;
  };
  type?: string;
  child_database?: { title: string };
  heading_1?: any;
  heading_2?: any;
};

export default function group(items: Item[]) {
  // 1. 建立ID到节点的映射，同时复制节点并移除parent属性
  const idMap = new Map<string, any>();
  const topLevel: Record<string, any> = {};

  items.forEach(item => {
    // 复制节点，排除parent属性
    const node = { ...item };
    delete node.parent;
    // 初始化child数组
    node.child = [];
    idMap.set(item.id, node);
  });

  // 2. 遍历每个节点，将其挂载到对应的父节点下
  items.forEach(item => {
    const parentId = item.parent.page_id || item.parent.database_id;
    const childNode = idMap.get(item.id);
    const parentNode = idMap.get(parentId);

    if (parentNode) {
      // 父节点存在，挂载到父节点的child数组
      parentNode.child.push({ [item.id]: childNode });
    } else {
      // 父节点不在当前数组中，作为顶级节点
      topLevel[parentId] = childNode;
    }
  });

  return topLevel;
}

代码说明 #

1. ID映射表：先遍历所有元素，将每个元素的ID作为键，元素本身（移除parent属性并初始化child数组）作为值存入Map，方便快速查找。
2. 挂载子节点：再次遍历元素，获取父节点ID，通过Map找到父节点，将当前节点包装成{ [id]: node }的形式推入父节点的child数组。
3. 收集顶级节点：如果父节点不在Map中（即父节点是外部节点），则将该节点作为顶级节点存入结果对象。

验证结果 #

调用group函数传入输入数组，得到的结果与期望输出一致，同时修正了期望输出中第二个子节点的type错误（原输入为heading_2，期望输出误写为heading_1，代码会保留原节点的type属性）。

内容的提问来源于stack exchange，提问作者Kacy