如何給樹型結構添加大綱目錄索引
需求
我們有如下的樹型結構
想統一給這樣的數據，添加目錄索引，變成這樣
我們知道從人眼看，只需要從上到下掃描就行了，可這要放在程序中可怎麼寫，人的思維和程序是不一樣的。
其實這涉及到一個樹的遍歷問題，有兩種方式可以實現
實現
方法一：逐層遍歷添加大綱
比如第一層添加x，第二層添加x.x，第三層添加x.x.x，如下圖
其實這種逐層擴散的遍歷叫：「廣度優先遍歷」，對應的是迭代實現，python代碼如下
def add_tree_index_iterative(tree_list):
for i, v in enumerate(tree_list):
v['index'] = i + 1
q.append(v)
while q:
v = q.pop(0) # 出隊列
if v['children']:
for i, node in enumerate(v['children']):
node['index'] = f'{v["index"]}.{i + 1}'
q.append(node) # 入隊列
這其實藉助了一個隊列實現，python中的list的append和pop(0)分別對應了隊列的入隊和出隊操作
方法二：深度遍歷添加大綱
就是每次都走到頭添加完了再回來
這種一次走到頭的遍歷叫：「深度優先遍歷」，對應的是遞歸實現
def add_tree_index_recursive(tree_list, parent_index=""):
for i, v in enumerate(tree_list):
if not parent_index:
v['index'] = i + 1
else:
v['index'] = f'{parent_index}.{i + 1}'
if v['children']:
add_tree_index_recursive(v['children'], v['index'])
測試結果
原始數據如下
[
{
"id": 1,
"parent_id": 0,
"name": "A",
"children": [
{
"id": 2,
"parent_id": 1,
"name": "AA",
"children": []
},
{
"id": 3,
"parent_id": 1,
"name": "AB",
"children": [
{
"id": 4,
"parent_id": 3,
"name": "ABA",
"children": []
},
{
"id": 5,
"parent_id": 3,
"name": "ABB",
"children": []
},
{
"id": 6,
"parent_id": 3,
"name": "ABC",
"children": []
}
]
},
{
"id": 7,
"parent_id": 1,
"name": "AC",
"children": [
{
"id": 8,
"parent_id": 7,
"name": "ACA",
"children": [
{
"id": 9,
"parent_id": 8,
"name": "ACAA",
"children": []
},
{
"id": 10,
"parent_id": 8,
"name": "ACAB",
"children": []
}
]
}
]
}
]
}
]
經過大綱函數，最終會給每個節點添加對應的Index字段，如下
