Skip to main content
 首页 » 编程设计

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

2025年05月04日8zhoujg

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

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

请您参考如下方法:

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

else: return insert(tr.left, el) 

和

else: return insert(tr.right, el) 

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

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

tr.right 也是如此。