python - 二叉搜索树的插入算法不起作用

Question

我正在尝试编写一个将节点插入二叉搜索树的函数。我看过几个例子，在我看来我的算法应该可以工作，但由于某种原因它没有通过测试。

def insert(tr, el):
    """ function to insert an element into a binary search tree
    following the rules of binary search trees.
    
    return: an updated tree
    precondition: assumed all elements unique
    """

    if tr == None: 
        return createEyecuBST(el, None)
    elif el < tr.value:
        if tr.left == None:
            tr.left = createEyecuBST(el, tr)
            return tr
        else: return insert(tr.left, el)
    elif el > tr.value:
        if tr.right == None:
            tr.right = createEyecuBST(el, tr)
            return tr
        else: return insert(tr.right, el)
    return None

Answer 1

您的代码中有两行出现问题:

else: return insert(tr.left, el)

和

else: return insert(tr.right, el)

在这些情况下，您的函数将返回 tr 的子树(左侧或右侧)，而您希望您的函数返回更新后的 tr 树。我认为您应该将这些行替换为:

else:
    insert(tr.left, el)
    return tr

tr.right 也是如此。