插入二进位搜索树

Question

因此，我必须将一个节点插入到二进制搜索树中。在我的入门课中，二进制搜索树表示为链接列表，如下图所示的该二叉树的[4, [5, [0, [],[]], [2, [], []]], [1, [],[]]]：

​

。

(这不是一个二叉树搜索树，只是一个二叉树，我有一张照片)。

因此，为了将节点插入到树中，我编写了以下递归代码：

def tree_node(key):
    return [key, [],[]]

def insert(bst,key):
    if bst == []:
        return tree_node(key)
    if key < bst[0]:
        return insert(bst[1],key)
    else:
        return insert(bst[2],key)
    return bst

这只是返回节点，而不是节点的新树。

例如：

>>> insert([2, [1, [], []], [3, [], []]], 6)
[6, [], []]

当它应该是：

>>> insert([2, [1, [], []], [3, [], []]], 6)
[2, [1, [], []], [3, [], [6, [], []]]]

谢谢!

Answer 1

你需要改变你的基本情况。您需要修改传入的空列表，而不是返回新的list。切片分配可能是最简单的：

def insert(bst,key):
    if bst == []:
        bst[:] = tree_node(key)
    elif key < bst[0]:
        insert(bst[1],key)
    else:
        insert(bst[2],key)

因为这个函数修改了树的位置，所以我不会返回它。如果需要，只需在末尾重新添加return bst (但不是递归步骤，我们希望忽略这些返回值)。

Answer 2

用return insert(bst[1],key)更改bst[1] = insert(bst[1],key) (与bst[2]类似)；通过这种方式，您实际上是在插入某些内容，并将执行最终的return语句。