这是我想出的将新值插入 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，如果这是一个微不足道的问题，我深表歉意。
请您参考如下方法:
您定义了 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
