Insertion in einen binären Suchbaum

Question

Dies ist der Code, den ich mit einem neuen Wert einfügen in ein BST kam:

class BST(object): 
    def __init__(self, root): 
     self.root = Node(root) 

    def insert(self, new_val): 
     self.__internal_insert(self.root, new_val) 

    def __internal_insert(self, node, new_val): 
     if node is None: 
      node = Node(new_val) 
     elif new_val < node.value: 
      self.__internal_insert(node.left, new_val) 
     else: 
      self.__internal_insert(node.right, new_val) 

# Set up the tree 
tree = BST(4) 

# Insert elements 
tree.insert(2) 
tree.insert(1) 
tree.insert(3) 
tree.insert(5) 

jedoch beim Debuggen Ich habe bemerkt, dass die self.root nie aktualisiert wird, zB .: als Sobald die Methode __internal_insert() abgeschlossen ist und eine neue insert() ausgeführt wird, werden die zugehörigen Geschwisterknoten left und right wieder auf None zurückgesetzt, anstatt auf den vorherigen Wert, der festgelegt wurde.

Ich hoffe, Sie helfen mir, wo der Fehler ist. Ich habe kürzlich Python abgeholt, ich entschuldige mich, wenn das eine triviale Frage ist.

Answer 1

Sie haben node = Node(new_val) definiert, aber wo binden Sie diesen Knoten jemals an den übergeordneten Knoten an?

Grundsätzlich Rekursion Sie, aber nie die Ergebnisse gefangen Sie bauen

Try Rückkehr Sie den Knoten

erstellt

def __internal_insert(self, node, new_val): 
    if node is None: 
     node = Node(new_val) 
    elif new_val < node.value: 
     node.left = self.__internal_insert(node.left, new_val) 
    else: 
     node.right = self.__internal_insert(node.right, new_val) 
    return node 

Answer 2

Ich sehe zwei Probleme mit dem Code.

Erstens, wenn Sie node neu zuweisen, wird der Wert dem BST-Objekt nicht zugewiesen. Um dies zu tun, müssen Sie direkt darauf verweisen: self.left = Node(new_val).

Zweitens überprüfen Sie nicht die Gleichheitsbedingung, damit Ihr Code nicht wie eine traditionelle BST funktioniert. Sie werden mit vielen fremden Knoten enden.