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