JS 将平面结构的列表转换为树形结构

export function deepTree(list: any[]): any[] {
    const newList: any[] = [];
    const map: any = {};

    list.forEach((e) => (map[e.id] = e));

    list.forEach((e) => {
        const parent = map[e.parentId];
        if (parent) {
            (parent.children || (parent.children = [])).push(e);
        } else {
            newList.push(e);
        }
    });

    const fn = (list: Array<any>) => {
        list.map((e) => {
            if (e.children instanceof Array) {
                fn(e.children);
            }
        });
    };

    fn(newList);

    return newList;
}

这段代码是一个将平面结构的列表转换为树形结构的函数。每个元素应该有一个唯一的 id 和一个指向其父元素的 parentId。如果 parentId 不存在或无效，该元素被视为根元素。我将提供一个使用这个 deepTree 函数的示例：

假设的初始数据：

假设我们有一个表示组织结构的列表，每个员工有一个唯一的 id，以及一个 parentId 指向其直接上级：

const employees = [
    { id: 1, name: "Boss", parentId: null },
    { id: 2, name: "Manager 1", parentId: 1 },
    { id: 3, name: "Manager 2", parentId: 1 },
    { id: 4, name: "Employee 1", parentId: 2 },
    { id: 5, name: "Employee 2", parentId: 2 },
    { id: 6, name: "Employee 3", parentId: 3 }
];

在这个列表中，有一个总经理（Boss），两个经理（Manager 1 和 Manager 2），以及三名普通员工（Employee 1、Employee 2 和 Employee 3）。

使用 `deepTree` 函数：

现在我们使用 deepTree 函数将这个平面列表转换为树形结构：

const orgChart = deepTree(employees);
console.log(orgChart);

预期输出：

这段代码会生成一个树形结构的数组，如下所示：

[
    {
        id: 1,
        name: "Boss",
        parentId: null,
        children: [
            {
                id: 2,
                name: "Manager 1",
                parentId: 1,
                children: [
                    { id: 4, name: "Employee 1", parentId: 2 },
                    { id: 5, name: "Employee 2", parentId: 2 }
                ]
            },
            {
                id: 3,
                name: "Manager 2",
                parentId: 1,
                children: [
                    { id: 6, name: "Employee 3", parentId: 3 }
                ]
            }
        ]
    }
]

解释：

Boss（id: 1）是根节点，因为它的 parentId 是 null。
Manager 1 和 Manager 2 是 Boss 的子节点。
Employee 1、Employee 2 是 Manager 1 的子节点，而 Employee 3 是 Manager 2 的子节点。

通过这种方式，deepTree 函数能够将一个平面的列表转换为表达层级关系的树形结构，这在处理层级数据（如组织结构图、目录结构等）时非常有用。

要实现反向操作，即将树形结构转换回平面列表，我们需要编写一个函数来遍历树形结构并收集所有节点。这个过程通常涉及递归遍历，因为树形结构的每个节点可能有子节点，这些子节点也可能有自己的子节点，依此类推。

以下是一个实现这一功能的函数示例：

反向操作函数

function flattenTree(tree) {
    let result = [];
    
    function traverse(node) {
        if (node) {
            result.push({
                id: node.id,
                name: node.name,
                parentId: node.parentId
            });

            if (node.children && node.children.length > 0) {
                node.children.forEach(child => {
                    traverse(child);
                });
            }
        }
    }

    tree.forEach(rootNode => {
        traverse(rootNode);
    });

    return result;
}

使用示例

假设我们有以下树形结构数据：

const orgChart = [
    {
        id: 1,
        name: "Boss",
        parentId: null,
        children: [
            {
                id: 2,
                name: "Manager 1",
                parentId: 1,
                children: [
                    { id: 4, name: "Employee 1", parentId: 2 },
                    { id: 5, name: "Employee 2", parentId: 2 }
                ]
            },
            {
                id: 3,
                name: "Manager 2",
                parentId: 1,
                children: [
                    { id: 6, name: "Employee 3", parentId: 3 }
                ]
            }
        ]
    }
];

我们可以使用 flattenTree 函数将其转换回平面列表：

const flattenedList = flattenTree(orgChart);
console.log(flattenedList);

预期输出

输出应该是原始平面列表的形式：

[
    { id: 1, name: "Boss", parentId: null },
    { id: 2, name: "Manager 1", parentId: 1 },
    { id: 4, name: "Employee 1", parentId: 2 },
    { id: 5, name: "Employee 2", parentId: 2 },
    { id: 3, name: "Manager 2", parentId: 1 },
    { id: 6, name: "Employee 3", parentId: 3 }
]

说明

在这个函数中，我们定义了一个内部函数 traverse 来递归地遍历每个节点。对于树中的每个节点，我们将其简化信息（id、name、parentId）添加到结果列表中。如果节点有子节点，我们对这些子节点递归地执行相同的操作。通过这种方式，我们能够将整个树形结构“展平”成一个一维列表。