如何将扁平dbDataArray转换为树形结构适配Select组件？

问题背景 #

从数据库获取的扁平数据需要转换为嵌套树形结构，适配TreeSelect组件的格式。

数据库表结构 #

转换后的扁平数组（dbDataArray） #

type TreeSelectType = {
  title: string;
  value: string;
  key: string;
  parentName: string | undefined;
  children: TreeSelectType[];
};

const dbDataArray: TreeSelectType[] = [
    {
        "title": "Marvel",
        "value": "1000",
        "key": "1000",
        "parentName": null,
        "children": []
    },
    {
        "title": "X-man",
        "value": "1100",
        "key": "1100",
        "parentName": "Marvel",
        "children": []
    },
    {
        "title": "Wolverine",
        "value": "1110",
        "key": "1110",
        "parentName": "X-man",
        "children": []
    },
    {
        "title": "Professor X",
        "value": "1120",
        "key": "1120",
        "parentName": "X-man",
        "children": []
    },
    {
        "title": "Avengers",
        "value": "1200",
        "key": "1200",
        "parentName": "Marvel",
        "children": []
    },
    {
        "title": "Captain America",
        "value": "1210",
        "key": "1210",
        "parentName": "Avengers",
        "children": []
    },
    {
        "title": "Peggy Carter",
        "value": "1211",
        "key": "1211",
        "parentName": "Captain America",
        "children": []
    },
    {
        "title": "Iron Man",
        "value": "1220",
        "key": "1220",
        "parentName": "Avengers",
        "children": []
    },
    {
        "title": "Tony Startk",
        "value": "1221",
        "key": "1221",
        "parentName": "Iron Man",
        "children": []
    },
    {
        "title": "War Machines",
        "value": "1222",
        "key": "1222",
        "parentName": "Iron Man",
        "children": []
    },
    {
        "title": "DC",
        "value": "2000",
        "key": "2000",
        "parentName": null,
        "children": []
    },
    {
        "title": "BatMan",
        "value": "2100",
        "key": "2100",
        "parentName": "DC",
        "children": []
    },
    {
        "title": "SuperMan",
        "value": "2200",
        "key": "2200",
        "parentName": "DC",
        "children": []
    },
];

目标树形结构（treeDataArray） #

[
    {
        "title": "Marvel",
        "value": "1000",
        "key": "1000",
        "parentName": "Marvel",
        "children": [
            {
                "title": "X-man",
                "value": "1100",
                "key": "1100",
                "parentName": "Marvel",
                "children": [
                    {
                        "title": "Wolverine",
                        "value": "1110",
                        "key": "1110",
                        "parentName": "X-man",
                        "children": []
                    },
                    {
                        "title": "Professor X",
                        "value": "1120",
                        "key": "1120",
                        "parentName": "X-man",
                        "children": []
                     },
                 ],
            },
            {
                "title": "Avengers",
                "value": "1200",
                "key": "1200",
                "parentName": "Marvel",
                "children": [
                    {
                        "title": "Captain America",
                        "value": "1210",
                        "key": "1210",
                        "parentName": "Avengers",
                        "children": [
                            {
                                "title": "Peggy Carter",
                                "value": "1211",
                                "key": "1211",
                                "parentName": "Captain America",
                                "children": []
                            },
                        ]
                    },
                    {
                        "title": "Iron Man",
                        "value": "1220",
                        "key": "1220",
                        "parentName": "Avengers",
                        "children": [
                            {
                                "title": "Tony Startk",
                                "value": "1221",
                                "key": "1221",
                                "parentName": "Iron Man",
                                "children": []
                            },
                            {
                                "title": "War Machines",
                                "value": "1222",
                                "key": "1222",
                                "parentName": "Iron Man",
                                "children": []
                            },
                        ]    
                    },
                ]
            },
        ]
    },
    {
        "title": "DC",
        "value": "2000",
        "key": "2000",
        "parentName": null,
        "children": [
            {
                "title": "BatMan",
                "value": "2100",
                "key": "2100",
                "parentName": "DC",
                "children": []
            },
            {
                "title": "SuperMan",
                "value": "2200",
                "key": "2200",
                "parentName": "DC",
                "children": []
            },
        ]
    },
]

解决方案 #

通过构建节点映射表+迭代挂载的方式实现高效转换，步骤如下：

1. 构建以节点title为键的映射表，快速定位父节点
2. 遍历所有节点，将子节点挂载到对应父节点的children数组中
3. 收集所有顶级节点（parentName为null或空字符串）作为树形结构的根节点

实现代码 #

function convertToTree(data: TreeSelectType[]): TreeSelectType[] {
    const nodeMap = new Map<string, TreeSelectType>();
    const tree: TreeSelectType[] = [];

    // 初始化映射表，同时收集顶级节点并处理特殊节点的parentName
    data.forEach(node => {
        const clonedNode = {...node};
        // 按目标结构要求修正Marvel的parentName
        if (clonedNode.parentName === null && clonedNode.title === "Marvel") {
            clonedNode.parentName = clonedNode.title;
        }
        nodeMap.set(clonedNode.title, clonedNode);
        if (clonedNode.parentName === null || clonedNode.parentName === "") {
            tree.push(clonedNode);
        }
    });

    // 挂载子节点到对应父节点
    data.forEach(node => {
        const parentName = node.parentName;
        if (parentName && parentName !== "") {
            const parentNode = nodeMap.get(parentName);
            if (parentNode) {
                parentNode.children.push({...node});
            }
        }
    });

    return tree;
}

// 使用示例
const treeDataArray = convertToTree(dbDataArray);
console.log(treeDataArray);

说明 #

• 映射表将节点查找复杂度降至O(1)，整体转换时间复杂度为O(n)，效率较高
• 代码中对Marvel的parentName做了特殊处理以匹配目标结构，若无需此规则可直接删除对应判断
• 克隆节点是为了避免修改原始数据，若允许修改原始数组可省略克隆步骤

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