将具有级别信息的平面数组重新排列为具有子级的n元树

基础概念

在计算机科学中，树是一种抽象数据结构，它模拟了具有根值和父节点的子树的层次结构。一个n元树是指每个节点可以有n个子节点的树结构。当处理具有层级关系的数据时，通常需要将这些数据转换为树形结构，以便于数据的存储、检索和管理。

类型

二叉树：每个节点最多有两个子节点。
多叉树：每个节点可以有多个子节点。
B树/B+树：用于数据库和文件系统，优化了大块数据的存储和检索。
红黑树：自平衡的二叉搜索树，用于保持数据有序。

应用场景

文件系统：文件和目录的层级结构。
组织结构：公司或团队的层级管理。
XML/JSON解析：数据通常以树形结构表示。
路由算法：网络中的路由表通常以树形结构存储。

示例代码

以下是一个将具有级别信息的平面数组转换为n元树的JavaScript示例代码：

function buildTree(items) {
    const rootItems = [];
    const lookup = {};

    // 初始化lookup表
    items.forEach(item => {
        lookup[item.id] = { ...item, children: [] };
    });

    // 构建树结构
    items.forEach(item => {
        if (item.parentId === null || item.parentId === undefined) {
            rootItems.push(lookup[item.id]);
        } else {
            lookup[item.parentId].children.push(lookup[item.id]);
        }
    });

    return rootItems;
}

// 示例数据
const data = [
    { id: 1, name: 'Root', parentId: null },
    { id: 2, name: 'Child1', parentId: 1 },
    { id: 3, name: 'Child2', parentId: 1 },
    { id: 4, name: 'GrandChild1', parentId: 2 },
    { id: 5, name: 'GrandChild2', parentId: 2 }
];

console.log(JSON.stringify(buildTree(data), null, 2));

可能遇到的问题及解决方法

问题：数据中存在循环引用，导致无限递归。

原因：数据中的某个节点被错误地设置为其自身的祖先。

解决方法：在构建树之前，检查并修正数据中的循环引用。

function hasCycle(node, lookup, path = []) {
    if (path.includes(node.id)) {
        return true;
    }
    path.push(node.id);
    for (const child of node.children) {
        if (hasCycle(child, lookup, path)) {
            return true;
        }
    }
    path.pop();
    return false;
}

function buildTreeSafe(items) {
    const rootItems = [];
    const lookup = {};

    items.forEach(item => {
        lookup[item.id] = { ...item, children: [] };
    });

    items.forEach(item => {
        if (item.parentId === null || item.parentId === undefined) {
            if (!hasCycle(lookup[item.id], lookup)) {
                rootItems.push(lookup[item.id]);
            }
        } else {
            if (!hasCycle(lookup[item.id], lookup)) {
                lookup[item.parentId].children.push(lookup[item.id]);
            }
        }
    });

    return rootItems;
}

通过这种方式，可以确保构建的树结构不会因为循环引用而导致程序崩溃。