如何有效地將平桌放入嵌套的樹結構中？

將扁平表高效解析為樹狀結構

簡介

將表示樹形層次結構的扁平表高效轉換為嵌套結構，可以使用多種方法實現。本文探討了一種使用基本數據結構的極簡方案，並考慮了用於優化樹形表示的替代數據庫存儲方法。

解析的極簡方法

假設一個表包含以下數據：

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

將此表解析為樹形結構：

1. 創建字典：將每個節點的 Id 映射到其對應的數據。

2. 識別根節點：根節點是沒有 ParentId 的節點。

3. 構建樹：通過遞歸創建子節點並將其添加到相應的父節點來構建樹。

   • 對於每個非根節點，使用其 ParentId 在字典中查找其父節點。
   • 將節點添加為父節點的子節點。

4. 排序子節點：根據子節點的 Order 對每個節點的子節點進行排序。

此方法的偽代碼：

<code>创建字典(table)
def 获取根节点():
    根节点 = []
    对于 id, 节点 in 字典.items():
        如果 节点['ParentId'] == 0:
            根节点.append(节点)
    返回 根节点

def 构建树(根节点):
    对于 根节点 in 根节点:
        子节点 = []
        对于 id, 节点 in 字典.items():
            如果 节点['ParentId'] == 根节点['Id']:
                子节点.append(节点)
        子节点.sort(key=lambda x: x['Order'])
        根节点['children'] = 子节点
        构建树(子节点)

def 打印树(根节点):
    对于 根节点 in 根节点:
        打印(根节点['Name'])
        如果 'children' in 根节点:
            打印树(根节点['children'])</code>

SQL 中樹形結構的替代存儲方法

閉包表：

在關係數據庫中存儲樹形結構的另一種方法是使用閉包表，其中包含一個單獨的表，該表包含祖先節點 ID 和後代節點 ID 列。這允許輕鬆查詢關係。

使用閉包表的查詢：

<code>SELECT f.name, GROUP_CONCAT(b.ancestor_id order by b.path_length desc) AS breadcrumbs
FROM FlatTable f 
JOIN ClosureTable a ON (f.id = a.descendant_id) 
JOIN ClosureTable b ON (b.descendant_id = a.descendant_id) 
WHERE a.ancestor_id = 1 
GROUP BY a.descendant_id 
ORDER BY f.name</code>

嵌套集：

嵌套集涉及在單個表中存儲樹中每個節點的位置信息。此方法允許對給定級別或子樹中的節點進行高效的基於範圍的查詢。

結論

雖然提供的示例使用扁平表作為輸入，但所提出的方法非常適用於不同的數據結構和存儲方法。通過使用適當的技術，您可以高效地解析樹形層次結構，並確保數據完整性和易於訪問。

以上是如何有效地將平桌放入嵌套的樹結構中？的詳細內容。更多資訊請關注PHP中文網其他相關文章！