Rekursive Erstellung einer Baumhierarchie ohne Verwendung von Klasse/Objekt

Question

Ich habe Probleme beim Erstellen einer Baumhierarchie in Python 3. Ich möchte dies ohne Verwendung von Klassen tun können.

Die Daten, die ich mit beginnen muß, ist nicht in Ordnung und im Format ['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']] 

Ich mag den (Baum) Wörterbuch Variable ohne die Verwendung von Klassen und am Ende mit etwas schaffen wie:

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

ODER

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

Offensichtlich haben R1 und R2 mehr Kinder als das, aber vielleicht würde die Baumstruktur so aussehen?

Answer 1

Sie können einfach durchlaufen jeden child, parent Tupel, erstellen Wörterbuch, das die IDs des Kindes abbildet und die Eltern zu einer Liste, die die Kinder dieser Elemente enthalten. Wir machen das solange, bis wir fertig sind.

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 

Jetzt, wo wir das getan haben, ist roots ein Satz der IDs der Baumwurzeln: so für jedes solches Element wissen wir, dass es keine ID, die ein Elternteil ist. Für jede ID in der roots, können wir einfach von der mapping abrufen und das ist ein Wörterbuch der Struktur {'childid':child} wo childid ist die ID (hier ein string) und child ist wieder ein Wörterbuch dieser Form.

So können Sie sie mögen drucken:

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

So in Ihrem Fall die tree ist:

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

Für Ihre Probe data, es erzeugt:

>>> 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': {}}}}}