如何实现buildTree()函数：合并多棵树对象为单棵树结构

我需要实现一个buildTree()函数，接收特定格式的数组输入，将其中ID相同的元素合并，把它们的子节点合并为同一父节点下的兄弟节点，最终输出符合要求的树形结构。

示例输入输出 #

示例1

输入：

let array = [
  { levelOne: [ { id: 'a', rowData: {} } ] },
  { levelOne: [ { id: 'b', children: { levelTwo: [ { id: 'c', rowData: {} } ] } } ] },
  { levelOne: [ { id: 'b', children: { levelTwo: [ { id: 'd', rowData: {} } ] } } ] }
]

调用buildTree(array)后预期输出：

{
  levelOne: [
    { id: 'a', rowData: {} },
    { id: 'b', children: { levelTwo: [ { id: 'c', rowData: {} }, { id: 'd', rowData: {} } ] } }
  ]
}

示例2

输入：

let array2 = [
  { levelOne: [ { id: 'a', rowData: {} } ] },
  { levelOne: [ { id: 'a', children: { levelTwo: [ { id: 'b', rowData: {} } ] } } ] },
  { levelOne: [ { id: 'a', children: { levelTwo: [ { id: 'b', children: { levelThree: [ { id: 'c', rowData: {} } ] } } ] } } ] },
  { levelOne: [ { id: 'a', children: { levelTwo: [ { id: 'b', children: { levelThree: [ { id: 'd', rowData: {} } ] } } ] } } ] }
];

调用buildTree(array2)后预期输出：

{
  levelOne: [
    { id: 'a', rowData: {}, children: { levelTwo: [ { id: 'b', rowData: {}, children: { levelThree: [ { id: 'c', rowData: {} }, { id: 'd', rowData: {} } ] } } ] } }
  ]
}

核心规则与约束 #

• 若数组中两个元素ID相同，则它们的子节点需合并为同一父节点下的兄弟节点
• 输入数据中，rowData始终处于树的最底层
• 输入中levelOne、levelTwo等数组均为仅包含一个对象的单元素数组
• levelOne、levelTwo等为动态键，需保留在输出结构中

现有代码问题 #

我已经写了辅助函数getElementByLevel()用于获取指定层级的元素，但buildTree()函数尚未完成且无法正常工作：

getElementByLevel(tree: any, level: number , count = 0){
  if(tree){
    let key = Object.keys(tree)[0]
    let element = tree[key][0];
    if(count<level){
      count=count+1
      return this.getElementByLevel(element.children,level , count)
    } else {
      return element;
    }
  } else {
    return null;
  }
}

buildTree(mainArray: any[]){
  let myTree = {};
  mainArray.forEach((item , index) => {
    if(index == 0){
      myTree = {...item};
      console.log(myTree);
    } else {
      debugger;
      let myElement = this.getElementByLevel(myTree, 0);
      let elementToAdd = this.getElementByLevel(mainArray[1],0 )
      myElement = {...myElement, ...elementToAdd}
      console.log(myElement);
      myTree = myElement;
    }
  })
}

要解决这个问题，核心是递归遍历并合并同ID的节点，我们可以拆解为以下几个步骤：

• 解析单个输入项的路径与节点：每个输入项是嵌套结构，需要拆解成从根层级到叶子节点的完整路径，以及每个节点的属性（比如rowData）。
• 递归查找或创建节点：从树的根节点开始，沿着路径依次查找每个层级的节点：
  • 如果当前层级下已存在同ID的节点，就合并该节点的属性和子节点
  • 如果不存在，就创建新的节点并添加到对应层级的数组中
• 处理动态层级键：因为levelOne、levelTwo是动态的，每次处理时要先获取当前层级的键名，而非硬编码。
• 合并子节点逻辑：当找到同ID节点时，若两者都有子节点，需要递归合并子节点内容；若只有一方有子节点，则直接将子节点添加到现有节点中。

以下是调整后的辅助函数和完整的buildTree()实现：

class TreeBuilder {
  // 递归合并两个同ID节点
  mergeNodes(existingNode, newNode) {
    // 合并基础属性（如rowData）
    Object.assign(existingNode, newNode);
    
    // 处理子节点合并
    if (existingNode.children && newNode.children) {
      const existingChildKey = Object.keys(existingNode.children)[0];
      const newChildKey = Object.keys(newNode.children)[0];
      
      // 按输入约束，子层级键应该一致
      if (existingChildKey === newChildKey) {
        const existingChildren = existingNode.children[existingChildKey];
        const newChildren = newNode.children[newChildKey];
        
        // 遍历新子节点，合并到现有数组中
        newChildren.forEach(newChild => {
          const match = existingChildren.find(child => child.id === newChild.id);
          if (match) {
            this.mergeNodes(match, newChild);
          } else {
            existingChildren.push(newChild);
          }
        });
      }
    } else if (newNode.children) {
      // 现有节点无子节点，直接赋值新节点的子节点
      existingNode.children = newNode.children;
    }
  }

  // 将单个输入项插入到目标树中
  insertItemIntoTree(tree, item) {
    const rootKey = Object.keys(item)[0];
    // 初始化根层级数组（如果不存在）
    tree[rootKey] = tree[rootKey] || [];
    const rootNodes = tree[rootKey];
    const newRootNode = item[rootKey][0];
    
    // 查找根节点中是否有同ID的节点
    const matchNode = rootNodes.find(node => node.id === newRootNode.id);
    if (matchNode) {
      this.mergeNodes(matchNode, newRootNode);
    } else {
      rootNodes.push(newRootNode);
    }
  }

  buildTree(mainArray) {
    const resultTree = {};
    
    mainArray.forEach(item => {
      this.insertItemIntoTree(resultTree, item);
    });
    
    return resultTree;
  }
}

// 测试示例1
const array = [
  { levelOne: [ { id: 'a', rowData: {} } ] },
  { levelOne: [ { id: 'b', children: { levelTwo: [ { id: 'c', rowData: {} } ] } } ] },
  { levelOne: [ { id: 'b', children: { levelTwo: [ { id: 'd', rowData: {} } ] } } ] }
];
const builder = new TreeBuilder();
console.log(JSON.stringify(builder.buildTree(array), null, 2));

// 测试示例2
const array2 = [
  { levelOne: [ { id: 'a', rowData: {} } ] },
  { levelOne: [ { id: 'a', children: { levelTwo: [ { id: 'b', rowData: {} } ] } } ] },
  { levelOne: [ { id: 'a', children: { levelTwo: [ { id: 'b', children: { levelThree: [ { id: 'c', rowData: {} } ] } } ] } } ] },
  { levelOne: [ { id: 'a', children: { levelTwo: [ { id: 'b', children: { levelThree: [ { id: 'd', rowData: {} } ] } } ] } } ] }
];
console.log(JSON.stringify(builder.buildTree(array2), null, 2));

代码说明 #

1. mergeNodes函数：负责合并两个同ID节点，先合并基础属性，再递归处理子节点的合并逻辑，确保子节点也能正确合并为兄弟节点。
2. insertItemIntoTree函数：处理单个输入项，先获取根层级的动态键，然后在根节点数组中查找同ID节点，存在则合并，不存在则添加新节点。
3. buildTree函数：初始化空的结果树，遍历所有输入项，逐个插入并合并到结果树中，最终返回完整的树形结构。

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