Fügen Sie einen neuen Wert in eine Baumpython ein
Ich habe einen Baum wie:
tree = [[[None,1,None],2,[None,3,None]],4,[None,6,[None,7,None]]]
Die Zahlen repräsentieren die Wurzel jedes Knotens, die keine repräsentieren die Kinder, die keinen Wert haben.
Zum Beispiel ist die Hauptwurzel 4 und [[Keine, 1, Keine], 2, [Keine, 3, Keine]] ist der Unterbaum auf der linken Seite und dieser [Keine, 6, [Keine, 7, Keine]] ist er Unterbaum auf der rechten Seite. Die Hauptwurzel im Unterbaum links ist 2 etc etc ...
Und mein Problem ist, dass ich einen Wert in diesen Baum einfügen möchte.
Zum Beispiel möchte ich den Wert 5 hinzufügen, das ist, was ich möchte:
tree = [[[None, 1, None], 2, [None, 3, None]], 4, [[None, 5, None], 6, [None, 7, None]]]
Meine Funktion benötigt zwei Argumente, den Baum und die Ganzzahl, um sie hinzuzufügen. Ich muss die rekursive Funktion verwenden. Zum Beispiel habe ich Folgendes gestartet:
def insert(tree,int):
cur = tree
prev = None
while cur != None:
prev = cur
if int < cur[1]:
cur = cur[0]
else :
cur = cur[2]
Danke im Voraus
Antworten
Da Sie die Rekursion erwähnt haben, finden Sie hier eine Lösung mit Rekursion:
def insert_node(root, node):
if root == [None]: #corner case of an empty tree
root.append(node)
root.append(None) #now root will be : [None, node, None]
return
if node <= root[1]: #we need to go left
if root[0] == None:
root[0] = [None, node, None]
return
else:
insert_node(root[0], node)
else: #we need to go right
if root[2] == None:
root[2] = [None, node, None]
return
else:
insert_node(root[2], node)
Testen der Lösung:
tree = [None] #starting with an empty tree
insert_node(tree, 4)
insert_node(tree, 2)
insert_node(tree, 1)
insert_node(tree, 3)
insert_node(tree, 6)
insert_node(tree, 7)
print(tree)
Die Funktion durchläuft den Baum rekursiv, bis die richtige Stelle zum Einfügen des Knotens erreicht ist. Da es sich um einen binären Suchbaum handelt, müssen wir sicherstellen, dass jedes untergeordnete Element links von einem Knoten kleiner als dieser Knoten und jedes untergeordnete Element rechts größer sein sollte. Deshalb gehen wir nach dem Vergleich des neuen Knotens mit der aktuellen Wurzel der Durchquerung lef / right.