在不使用類/對象的情況下遞歸創建樹層次結構

我在創建Python 3中的樹層次結構時遇到了問題。我希望能夠在不使用類的情況下執行此操作。在不使用類/對象的情況下遞歸創建樹層次結構

我要開始用的數據是不是爲了和格式['ID','Parent']：

data=[['E1', 'C1'],['C1', 'P1'],['P1', 'R1'],['E2', 'C2'],['C2', 'P2'],['P2', 'R1'],['C3', 'P2'],['E3', 'C4'],['C4', 'P3'], 
    ['P3', 'R2'],['C5', 'P3'],['E4', 'C6'],['C6', 'P4'], ['P4', 'R2'],['E5', 'C7'],['C7', 'P5'],['P5', 'R3'],['E6', 'C9'],['C9', 'P6'],['P6', 'R3'], 
    ['C8', 'P6'],['E7', 'C10'],['C10', 'P7'],['P7', 'R4'],['C11', 'P7'],['E8', 'C12'],['C12', 'P8'],['P8', 'R4']]

我想不使用類創建（樹）詞典變量和東西最終像：

Tree={'R1':{'P1':{},'P2':{}},'R2':{}} etc

OR

Tree={'R1':[{'P1':[],'P2':[]}],'R2':[]} etc

顯然，R1和R2的子元素比這個多，但也許這就是Tree結構的樣子？

來源

2017-03-03 citizen2077

是什麼瞭解數據中元素的顯示順序？ –

你知道你不能在字典中使用與不同元素相同的密鑰，對吧？ ;） – alfasin

Python字典必須具有唯一鍵。如果你試圖定義類似'{'ID'：1，'ID'：2}'，你最終會得到'{'ID'：2}'，因爲第二個'ID'會覆蓋第一個。 –

您可以簡單地遍歷每個child，parent元組，創建將子項和父項的id映射到包含這些元素的子項的列表的字典。我們一直這樣做直到我們完成。

roots = set() 
mapping = {} 
for child,parent in data: 
    childitem = mapping.get(child,None) 
    if childitem is None: 
     childitem = {} 
     mapping[child] = childitem 
    else: 
     roots.discard(child) 
    parentitem = mapping.get(parent,None) 
    if parentitem is None: 
     mapping[parent] = {child:childitem} 
     roots.add(parent) 
    else: 
     parentitem[child] = childitem

現在我們已經做到了，roots是一套樹根的id的：使每一個這樣的元素，我們知道，沒有ID作爲父。對於roots中的每個ID，我們可以簡單地從mapping中獲取並且這是結構{'childid':child}的字典，其中childid是id（這裏是string）並且child又是該形式的字典。

所以，你可以打印出來，如：

for root in roots: 
    print(mapping[root])

你的情況

所以，tree是：

tree = { id : mapping[id] for id in roots }

爲您的樣品data，它產生：

>>> tree 
{'R1': {'P1': {'C1': {'E1': {}}}, 'P2': {'C2': {'E2': {}}, 'C3': {}}}, 'R2': {'P4': {'C6': {'E4': {}}}, 'P3': {'C5': {}, 'C4': {'E3': {}}}}, 'R3': {'P6': {'C8': {}, 'C9': {'E6': {}}}, 'P5': {'C7': {'E5': {}}}}, 'R4': {'P8': {'C12': {'E8': {}}}, 'P7': {'C11': {}, 'C10': {'E7': {}}}}}

來源

2017-03-03 21:18:37

感謝您的輸入，但輸出樹似乎是不完整的，例如P4應該有孩子C6和ID，如C9缺失，許多是實際上缺少 – citizen2077

@new_to_coding：你是對的。我發現了這個錯誤。現在它應該工作。 –

這是正確的，非常感謝您的幫助！ – citizen2077

在不使用類/對象的情況下遞歸創建樹層次結構

回答

相關問題