插入二叉搜索树

安迪·雷斯

这是我想出的将新值插入 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 

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章