二叉搜索树不工作的插入算法

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。你知道吗