如何首先從父級遞回排序資料，然后使用python繼續其子級？

我有一個名為 Topics 的模型，其中包含如下資料：

我想先按父項對其進行排序，然后像深度優先處理一樣對其子項進行排序，并僅獲取沒有 has_sub_topic 的主題的資料。因此，資料將按如下順序排序：https : //upload.wikimedia.org/wikipedia/commons/7/7f/Depth-First-Search.gif并僅獲取資料 4、7、8、10

以前我嘗試使用排序函式，但對很多孩子來說并不順利。所以，我必須使用遞回函式。我使用遞回的代碼是這樣的：

# Example data for topics
import pandas as pd
topics = pd.DataFrame({
    'id': [27, 31, 34, 28, 29, 40, 32, 33, 41, 43, 44, 42, 45, 47, 48], 
    'has_sub_topic': [1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0],
    'parent_id': [None, None, None, 27, 27, 27, 31, 31, 40, 40, 40, 41, 44, 44, 47],
    'subject_module_level_id': [25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25],
    'order': [1, 2, 3, 1, 2, 3, 1, 2, 1, 2, 3, 1, 1, 2, 1]
    })

def topic_child_order(topic, list_topics=None):
    if list_topics is None: list_topics = []

    if topic.has_sub_topic:
        topics = Topics.objects.filter(parent=topic).order_by('order')
        for child in topics:
            result = topic_child_order(child, list_topics)
    else:
        result = topic

    list_topics.append(result)

    return list_topics
    

topics = Topics.objects.filter(
    subject_module_level_id=25,
    parent=None
).order_by('order')

topics_order = []

for topic in topics:
    topics_order.append(topic_child_order(topic))

結果是這樣的：

[
  [
    <Topics: Topicsobject(28)>,
    <Topics: Topicsobject(29)>,
    <Topics: Topicsobject(42)>,
    [
      ...
    ],
    <Topics: Topicsobject(43)>,
    <Topics: Topicsobject(45)>,
    <Topics: Topicsobject(48)>,
    [
      ...
    ],
    [
      ...
    ],
    [
      ...
    ],
    [
      ...
    ]
  ],
  [
    <Topics: Topicsobject(32)>,
    <Topics: Topicsobject(33)>,
    [
      ...
    ]
  ],
  [
    <Topics: Topicsobject(34)>
  ]
]

The sort order is right but I don't know why the result has empty lists. Anyone know how to fix this? Or anyone know how to do this more better way so the result only return in one list not nested list?

uj5u.com熱心網友回復：

我以嵌套 python dict 的形式顯式構建了一個樹，將父 ID 映射到子 ID 串列，.iterrows用于向樹添加節點。孩子們按照他們給定的順序進行排序。

然后我在樹中執行一個簡單的深度優先搜索，沿途產生葉子的 id。

最后我.loc用來選擇資料框中的行。

import pandas as pd

topics = pd.DataFrame({
    'id': [27, 31, 34, 28, 29, 40, 32, 33, 41, 43, 44, 42, 45, 47, 48], 
    'has_sub_topic': [1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0],
    'parent_id': [0, 0, 0, 27, 27, 27, 31, 31, 40, 40, 40, 41, 44, 44, 47],
    'subject_module_level_id': [25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25],
    'order': [1, 2, 3, 1, 2, 3, 1, 2, 1, 2, 3, 1, 1, 2, 1]
    }).set_index('id')

tree = {}
for i, row in topics.iterrows():
    tree.setdefault(row['parent_id'], []).append(i)

for brotherhood in tree.values():
    brotherhood.sort(key=lambda sibling: topics.at[sibling,'order'])

# print( tree )
# {0: [27, 31, 34], 27: [28, 29, 40], 31: [32, 33], 40: [41, 43, 44], 41: [42], 44: [45, 47], 47: [48]}

def gen_leaves(tree, i=0):
    if i in tree:
        for child in tree[i]:
            yield from gen_leaves(tree, child)
    else:
        yield i

# print( list(gen_leaves(tree)) )
# [28, 29, 42, 43, 45, 48, 32, 33, 34]

leaf_ids = list(gen_leaves(tree))
topics_leaves = topics.loc[leaf_ids]

print(topics_leaves)
#     has_sub_topic  parent_id  subject_module_level_id  order
# id                                                          
# 28              0         27                       25      1
# 29              0         27                       25      2
# 42              0         41                       25      1
# 43              0         40                       25      2
# 45              0         44                       25      1
# 48              0         47                       25      1
# 32              0         31                       25      1
# 33              0         31                       25      2
# 34              0          0                       25      3

標籤：python recursion depth-first-search

上一篇：如何遞回遍歷潛在的無限樹

下一篇：從命令列設定Python遞回限制