JavaScript递归构建含循环引用节点树问题求助

问题说明 #

需要基于给定的节点数组构建树结构，要求：

• 以输入数组的第一个元素作为根节点
• 若节点的子节点包含父节点ID或根节点ID，仅展示该子节点的一层结构（不再递归展开其子节点）
• 最终输出仅包含一个根节点的数组
  当前使用的树生成函数无法生成符合预期的结构，需重新实现。

输入数据 #

[
  { "neo4jId": "1", "nodeName": "A", "children": ["12", "13", "14"] },
  { "neo4jId": "12", "nodeName": "AA", "children": ["1", "21", "22", "23"] },
  { "neo4jId": "13", "nodeName": "AB", "children": ["1"] },
  { "neo4jId": "14", "nodeName": "AC", "children": ["12"] },
  { "neo4jId": "21", "nodeName": "AAA", "children": ["1"] },
  { "neo4jId": "22", "nodeName": "AAB", "children": ["13"] },
  { "neo4jId": "23", "nodeName": "AAC", "children": [] }
]

预期输出 #

[
  {
    "key": "1",
    "data": { "nodeName": "A" },
    "children": [
      {
        "key": "12",
        "data": { "nodeName": "AA" },
        "children": [
          {
            "key": "21",
            "data": { "nodeName": "AAA" },
            "children": [
              { "key": "1", "data": { "nodeName": "A" }, "children": [] }
            ]
          },
          {
            "key": "22",
            "data": { "nodeName": "AAB" },
            "children": [
              {
                "key": "13",
                "data": { "nodeName": "AB" },
                "children": [
                  { "key": "1", "data": { "nodeName": "A" }, "children": [] }
                ]
              }
            ]
          },
          { "key": "23", "data": { "nodeName": "AAC" }, "children": [] },
          { "key": "1", "data": { "nodeName": "A" }, "children": [] }
        ]
      },
      {
        "key": "13",
        "data": { "nodeName": "AB" },
        "children": [
          { "key": "1", "data": { "nodeName": "A" }, "children": [] }
        ]
      },
      {
        "key": "14",
        "data": { "nodeName": "AC" },
        "children": [
          {
            "key": "12",
            "data": { "nodeName": "AA" },
            "children": [
              {
                "key": "21",
                "data": { "nodeName": "AAA" },
                "children": [
                  { "key": "1", "data": { "nodeName": "A" }, "children": [] }
                ]
              },
              {
                "key": "22",
                "data": { "nodeName": "AAB" },
                "children": [
                  {
                    "key": "13",
                    "data": { "nodeName": "AB" },
                    "children": [
                      { "key": "1", "data": { "nodeName": "A" }, "children": [] }
                    ]
                  }
                ]
              },
              { "key": "23", "data": { "nodeName": "AAC" }, "children": [] },
              { "key": "1", "data": { "nodeName": "A" }, "children": [] }
            ]
          }
        ]
      }
    ]
  }
]

当前使用的函数 #

const getTree = (data = []) => {
  const getObject = (key) =>
      (({ children, noRecursion = [], ...o }) => ({
        ...o,
        children: [...children.map(getObject), ...noRecursion.map((key) => ({ ...r[key], children: [] }))],
      }))(r[key]),
    c = new Set(),
    r = Object.fromEntries(data.map(({ neo4jId: key, children = [], ...data }) => [key, { key, data, children }])),
    keys = Object.keys(r);

  keys.forEach((k) => {
    r[k].children.forEach((l) => {
      if (r[l].children.length < r[k].children.length) {
        r[l].noRecursion = [...r[l].children];
        r[l].children.length = 0;
      }
    });
  });

  keys.forEach((k) => r[k].children.forEach(Set.prototype.add, c));

  console.log(keys.filter((k) => !c.has(k)).map(getObject));

  return keys.filter((k) => !c.has(k)).map(getObject);
};

解决方案代码 #

const buildTree = (nodes) => {
  // 构建节点映射，实现快速查找
  const nodeMap = new Map(nodes.map(node => [node.neo4jId, node]));
  const rootNode = nodes[0];
  const rootId = rootNode.neo4jId;

  // 递归生成节点结构，跟踪当前路径防止循环
  const buildNode = (currentNodeId, parentPath) => {
    const node = nodeMap.get(currentNodeId);
    if (!node) return null;

    const children = node.children.map(childId => {
      // 若子节点是根节点或存在于当前路径，仅返回一层结构
      if (childId === rootId || parentPath.includes(childId)) {
        return {
          key: childId,
          data: { nodeName: nodeMap.get(childId).nodeName },
          children: []
        };
      }
      // 否则继续递归，更新路径
      return buildNode(childId, [...parentPath, currentNodeId]);
    }).filter(Boolean);

    return {
      key: currentNodeId,
      data: { nodeName: node.nodeName },
      children
    };
  };

  // 从根节点开始构建树
  return [buildNode(rootId, [rootId])];
};

代码说明 #

1. 节点映射：用Map存储所有节点，将节点查找复杂度降到O(1)
2. 递归逻辑：
   • 跟踪当前路径的节点ID集合，用于检测循环引用
   • 遇到根节点或循环节点时，直接返回无嵌套的单层结构
   • 正常节点则继续递归，同时将当前节点ID加入路径
3. 根节点启动：固定以输入数组第一个元素为根节点，最终返回仅含根节点的数组

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