BST插入在Python中無法正常工作

Question

我正在Python中實現BST，但是我遇到了與but_insert(t, k)有關的問題。 基本上，如果我再補充孩子的根，如下圖所示，它的工作原理：

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

但如果我插入另一個鍵，然後從根的整個分支似乎被丟棄。舉例來說，如果我執行：

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

後來，當我爲了打印T我只得到7 9。

這裏是Node構造函數和bst_insert（print_in_order函數正常工作，所以我沒有包括它）。

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) 

謝謝。

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