如何用递归在JavaScript中将扁平数据结构转为树形结构（测试问题）

我想用递归把给定的扁平数据转换成树形结构，但运行npm测试时失败了——树形结构确实生成了，但和预期结构不一致。

原始代码 #

let data = [
    { id: 'animals', parent: null },
    { id: 'mammals', parent: 'animals' },
    { id: 'cats', parent: 'mammals' },
    { id: 'dogs', parent: 'mammals' },
    { id: 'labrador', parent: 'dogs' },
    { id: 'retreiver', parent: 'dogs' },
    { id: 'corgi', parent: 'dogs' },
    { id: 'persian', parent: 'cats' },
    { id: 'siamese', parent: 'cats' },
    { id: 'maineCoon', parent: 'cats' }
];

// 要求实现一个makeTree函数，接收扁平数据，返回如下树形结构，必须用递归
function makeTree(arr, parent) {
     return arr  
     .filter((data) => data.parent === parent)
     .reduce(
         (tree, data) => [
             ...tree, 
             {
                 ...data,
                 child: makeTree(arr, data.id),
             },
         ],
         [], 
     )
}

console.log('making tree')
console.log(
    JSON.stringify(
        makeTree(data, null)
        , null, 2
    )
)

// 预期的树形结构
let expected = {
    animals: {
        mammals: {
            dogs: {
                labrador: {},
                retreiver: {},
                corgi: {},
            },
            cats: {
                persian: {},
                siamese: {},
                maineCoon: {}
            }
        }
    }
}

问题原因 #

当前函数返回的是数组结构，每个节点是包含id、parent和child数组的对象，但预期的是以节点id为键的嵌套对象，没有多余的id/parent字段，子节点直接作为对应键的值。

修正后的代码 #

let data = [
    { id: 'animals', parent: null },
    { id: 'mammals', parent: 'animals' },
    { id: 'cats', parent: 'mammals' },
    { id: 'dogs', parent: 'mammals' },
    { id: 'labrador', parent: 'dogs' },
    { id: 'retreiver', parent: 'dogs' },
    { id: 'corgi', parent: 'dogs' },
    { id: 'persian', parent: 'cats' },
    { id: 'siamese', parent: 'cats' },
    { id: 'maineCoon', parent: 'cats' }
];

function makeTree(arr, parent) {
    // 过滤出当前父节点下的所有子元素
    const children = arr.filter(item => item.parent === parent);
    // 用reduce构建嵌套对象，而不是数组
    return children.reduce((tree, item) => {
        // 递归处理子节点，作为当前id键的值
        tree[item.id] = makeTree(arr, item.id);
        return tree;
    }, {}); // 初始值是空对象，而非数组
}

const result = makeTree(data, null);
console.log(JSON.stringify(result, null, 2));

// 验证是否匹配预期
let expected = {
    animals: {
        mammals: {
            dogs: {
                labrador: {},
                retreiver: {},
                corgi: {},
            },
            cats: {
                persian: {},
                siamese: {},
                maineCoon: {}
            }
        }
    }
};

console.log('是否匹配预期：', JSON.stringify(result) === JSON.stringify(expected));

说明 #

1. 把reduce的初始值从数组[]改成了空对象{}，贴合预期的对象结构
2. 不再保留原数据的id/parent字段，直接用item.id作为对象的键
3. 递归调用得到的子节点直接赋值给当前键，去掉了多余的child属性
4. 当节点没有子元素时，reduce返回空对象，完全匹配预期结构

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