Ich habe eine Klasse für Baumknoten gebaut. Diese speichert jeweils einen eigenen Wert und referenzen auf die Kinderknoten und den Elternknoten (die natürlich auch wieder Objekte der Baumknoten-Klasse sind). Das ganze habe ich noch mit einigen Funktionen angereichert, die mir helfen meinen Algorithmus ablaufen zu lassen, hier aber eher nicht relevant sind. Ich speichere alle inneren Knoten-Objekte in einer mehrdimensionalen Dict "knoten" und alle Blätter-Objekte in einem Dict "blaetter".
Mein Problem ist nun, dass ich diesen ganzen Baum mit allem drum und dran gerne kopieren würde. Sprich ich müsste irgendwie das Dict "knoten" und "blaetter" so kopieren das alle Objekte dupliziert werden und die inneren Verknüpfungen entsprechend umgeschrieben werden. Habt ihr Vorschläge, wie das gehen könnte? Es ist auch noch möglich die Datenstruktur umzubauen, allerdings müsste sie schon ein Baum aus Objekten sein, damit die Knoten untereinander mit entsprechenden Methoden komunizieren können und außerdem brauche ich das blaetter-dict um schnell an ein bestimmtes Blatt zu kommen.
Anbei mal das wichtigste aus meinem Code:
Die Klasse TreeNode aus der die einzelnen Knotenobjekte generiert werden. Für den Baumaufbau sind nur die ersten Methoden wichtig, die meisten dienen der Werteverwaltung und haben mit dem Baumaufbau nichts zu tun.
Code: Alles auswählen
import weakref
class TreeNode:
def __init__(self, value = 0, itemId = None):
self.parent = None #Speichert Referenz auf den Elternknoten
self.parentPos = None #Speichert ob dieser Knoten das linke oder rechte Kind seiner Eltern ist
self.children = [None, None] #Speichert Referenzen auf die beiden Kinder
self.value = {"self":value, 0:0, 1:0} #Speichert den Eigen-Wert des Knotens und die Werte der Kinder
self.itemId = itemId
return None
def __del__(self):
r = self.parent()
if r is not None:
r.removeChildByPos(self.parentPos)
def addChild(self, pos, child):
"""Speichert Referenz auf Kind und aktualisiert Wert"""
print "Füge Kind hinzu (self, pos, kin)", self, pos, child
self.children[pos] = weakref.ref(child)
self.value[pos] += child.getValue()
child._setParent(self, pos)
self.updateValueToParent()
def _setParent(self, parent, pos):
"""Empfange und speichere Referenz auf Elternknoten"""
print "Setze Parent (self, parent, pos)", self, parent, pos
self.parent = weakref.ref(parent)
self.parentPos = pos
##########################################################
# Nachfolgende Methoden dienen der Werte-Verwaltung und haben nichts direkt mit dem Aufbau
# des Baumes zu tun!!!
##########################################################
def setItem(self, value, itemId):
"""Verändert Eigenwert und ItemId des Knotens"""
self.value["self"] = value
self.itemId = itemId
self.updateValueToParent()
return True
def updateValueFromChild(self, pos):
"""Wird aufgerufen, wenn sich Wert eines Kindes ändert, empfängt geänderte Werte von Kindern und gibt diese zusammen mit dem Eigenwert nach oben weiter"""
r = self.children[pos]()
self.value[pos] = r.getValue()
self.updateValueToParent()
def updateValueToParent(self):
"""Eigene Gesamtwert hat sich geändert, gibt ihn nach oben weiter"""
if self.parent is not None:
r = self.parent ()
#print "Gebe neuen Wert an Parent weiter", self
r.updateValueFromChild(self.parentPos)
def addChild(self, pos, child):
"""Speichert Referenz auf Kind und aktualisiert Wert"""
print "Füge Kind hinzu (self, pos, kin)", self, pos, child
self.children[pos] = weakref.ref(child)
self.value[pos] += child.getValue()
child._setParent(self, pos)
self.updateValueToParent()
def _setParent(self, parent, pos):
"""Empfange und speichere Referenz auf Elternknoten"""
print "Setze Parent (self, parent, pos)", self, parent, pos
self.parent = weakref.ref(parent)
self.parentPos = pos
def getValue(self):
return sum(self.value.values())
def getItemId(self):
return self.itemId
def removeChildByPos(self, pos):
self.value[pos] = 0
self.children[pos] = None
self.updateValueToParent()
def printRec(self, level = 0):
print "%d: %s [%s-%s-%s] (%s)" % (level, str(sum(self.value.values())), str(self.value["self"]), str(self.value[0]), str(self.value[1]), str(self.itemId))
if self.children[0] is not None:
r = self.children[0]()
r.printRec((level+1))
if self.children[1] is not None:
r = self.children[1]()
r.printRec((level+1))
Code: Alles auswählen
liste = sorted([1, 2, 3, 4, 5, 6, 7, 8, 9])
blaetter = {}
knoten = {}
for i, v in enumerate(liste):
print i, v
blaetter[i] = TreeNode(v, i) #Erzeuge Knoten für Blätter
tmp = blaetter.values()
level = 0
dir = 0
while len(tmp) > 1: #Verbinde jeweils 2 Blätter zu einem Knoten,
#bzw. zwei Knoten zu einem Knoten höherer
#Ordnung, bis nur noch ein Wurzelknoten übrig ist
level += 1
knoten[level] = []
while 1:
if len(tmp) > 1:
knoten[level].append(TreeNode())
knoten[level][-1].addChild(0, tmp.pop(0))
knoten[level][-1].addChild(1, tmp.pop(0))
elif len(tmp) == 1:
knoten[level].append(TreeNode())
knoten[level][-1].addChild(0, tmp.pop(0))
dir = 0
break
if len(tmp) < 1:
break
tmp = knoten[level][:]
