BST Einfügen funktioniert nicht richtig in Python

Question

Ich implementiere eine BST in Python, aber ich habe Probleme mit but_insert(t, k). Grundsätzlich, wenn ich nur hinzufügen, Kinder an die Wurzel, wie unten, es funktioniert:

T = Node(7) 
bst_insert(T, 9) 
bst_insert(T, 5) 

Aber wenn ich eine andere Taste legen, dann ein ganzer Zweig aus der Wurzel scheint fallen gelassen zu werden. Zum Beispiel, wenn ich ausführen:

T = Node(7) 
bst_insert(T, 9) 
bst_insert(T, 5) 
bst_insert(T, 3) 

Dann, wenn ich T um Druck nur ich 7 9 bekommen.

Hier ist der Node Konstruktor und bst_insert (die print_in_order Funktion funktioniert ordnungsgemäß, so dass ich es nicht aufgenommen habe).

class Node: 
    def __init__(self, key): 
     self.key = key 
     self.left = None 
     self.right = None 


def bst_insert(t, k): 
    if t is None: 
     t = Node(k) 

    elif k <= t.key: 
     if t.left is None: 
      t.left = Node(k) 
     else: 
      t.left = bst_insert(t.left, k) 
    else: 
     if t.right is None: 
      t.right = Node(k) 
     else: 
      t.right = bst_insert(t.right, k) 

Danke.

Answer 1

class Node: 
     def __init__(self, key): 
      self.key = key 
      self.left = None 
      self.right = None 


    def bst_insert(t, k): 
     if t is None: 
      t = Node(k) 

     elif k <= t.key: 
      if t.left is None: 
       t.left = Node(k) 
      else: 
       t.left = bst_insert(t.left, k) #1 
     else: 
      if t.right is None: 
       t.right = Node(k) 
      else: 
       t.right = bst_insert(t.right, k) #2 
     # return the node, #1 and #2 will always get None value 
     return t