插入二叉搜索树

Question

所以我必须将一个节点插入到二叉搜索树中。在我的介绍 class 中，二叉搜索树表示为链表，例如 , [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

这只是 returns 节点，而不是包含节点

的新树

例如：

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

应该是：

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

谢谢！

Answer 1

您需要更改基本情况。您需要修改传入的空列表，而不是 return 创建一个新的 list。切片分配可能是最简单的：

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

由于此函数会就地修改树，因此我不会 returning 它。如果需要，只需在末尾重新添加 return bst（但不是在递归步骤中，我们要忽略那些 return 值）。

Answer 2

将 return insert(bst[1],key) 更改为 bst[1] = insert(bst[1],key)（bst[2] 也类似）；这样你实际上是在插入一些东西，并将执行最终的 return 语句。

插入二叉搜索树

Insertion into Binary Search Tree

python

tree