解析平面表为树的最高效/优雅的方法是什么？

calendar 2023-09-09 09:34:25 · 1 min read · hierarchical-data tree recursion algorithm sql

假设你有一个存储有序树层次结构的平面表：

1Id   Name         ParentId   Order
2 1   'Node 1'            0      10
3 2   'Node 1.1'          1      10
4 3   'Node 2'            0      20
5 4   'Node 1.1.1'        2      10
6 5   'Node 2.1'          3      10
7 6   'Node 1.2'          1      20

你可以通过以下方式将其正确排序、正确缩进到HTML（或文本）中：

根节点0是虚构的根节点。

下面是一个图表，其中我们使用[id] Name。

1                       [0] ROOT
2                          /    \ 
3              [1] Node 1          [3] Node 2
4              /       \                   \
5    [2] Node 1.1     [6] Node 1.2      [5] Node 2.1
6          /          
7 [4] Node 1.1.1

要将其转换为树结构，我们可以使用递归算法。可以使用递归函数将节点插入其父节点的下属节点列表中，并不断调用自己以处理更深层次的节点。以下是将平面表转换为树结构的示例伪代码：

 1function buildTree(flatTable, parentId):
 2    tree = []
 3    for row in flatTable:
 4        if row["ParentId"] == parentId:
 5            node = {
 6                "Id": row["Id"],
 7                "Name": row["Name"],
 8                "Children": buildTree(flatTable, row["Id"])
 9            }
10            tree.append(node)
11    return tree
12
13flatTable = [
14    {"Id": 1, "Name": "Node 1", "ParentId": 0, "Order": 10},
15    {"Id": 2, "Name": "Node 1.1", "ParentId": 1, "Order": 10},
16    {"Id": 3, "Name": "Node 2", "ParentId": 0, "Order": 20},
17    {"Id": 4, "Name": "Node 1.1.1", "ParentId": 2, "Order": 10},
18    {"Id": 5, "Name": "Node 2.1", "ParentId": 3, "Order": 10},
19    {"Id": 6, "Name": "Node 1.2", "ParentId": 1, "Order": 20},
20]
21
22tree = buildTree(flatTable, 0)

使用此算法，可以将平面表转换为具有层次结构的树。

此方法的时间复杂度为 O(n)，其中 n 是平面表中的条目数。在树结构较大时可能会有一些性能问题，但对于大多数情况下的平面表，它应该是高效的。

此外，我们还可以考虑将树结构存储在关系数据库中的其他方式，例如使用闭包表（Closure Table）或嵌套集模型（Nested Set Model）。这些方法在一些特定的场景下可能会更有效，但它们也会带来其他的复杂性和额外的存储开销。具体选择取决于数据的特点和操作的需求。

相关文章推荐