Fügen Sie einen neuen Wert in eine Baumpython ein

Nov 24 2020

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

2 Maaddy Nov 24 2020 at 09:00

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.