插入到二叉搜索树

Question

这是我想出了插入一个新值到BST代码：

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) 

然而，在调试时我注意到，self.root从不更新，例如：作为一旦__internal_insert()方法完成并且执行新的insert()，则其兄弟节点left和right返回到None，而不是返回到之前设置的值。

希望你能帮我发现问题所在。我最近选择了Python，如果这是一个微不足道的问题，我很抱歉。

Answer 1

您定义了node = Node(new_val)，但是您在哪里将该节点附加到它的父级？

基本上，你递归，但从来没有捕获你正在构建

尝试的结果返回节点创建

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

我看到的代码的两个问题。

首先，当您重新指定node时，它不会将值分配给BST对象。要做到这一点，你需要直接引用它：self.left = Node(new_val)。

其次，你没有检查等于条件，所以你的代码不会像传统的BST那样工作。你会得到很多无关的节点。