使用Python中的字典构建二进制搜索树

Question

我正在尝试使用python中的dict构建BST（二进制搜索树）。我不明白为什么我的代码没有在BST中添加节点。我在这里看到了类似的帖子：How to implement a binary search tree in Python?它看起来与我的代码相同，只是声明了一个节点类，但是我想知道为什么我的dict实现失败（并希望增进我对使用递归在python中传递参数的理解）。

keys = [10,9,2,5,3,7,101,18]
start = {'key': keys[-1], 'val': 1, 'left': None, 'right': None}
def binarySearch(root, node):
# compare keys and insert node into right place
    if not root:
        root = node
    elif node['key'] < root['key']:
        binarySearch(root['left'], node)
    else:
        binarySearch(root['right'], node)

# Now let's test our function and build a BST
while keys:
    key = keys.pop()
    node = {'key': key, 'val': 1, 'left': None, 'right': None}
    binarySearch(start, node)
print(start) # unchanged, hence my confusion. Thx for your time!

===========================================>

编辑：这是使它起作用的代码！

def binarySearch(root, node):
# compare keys and insert node into right place
    if not root:
        root = node
    elif node['key'] < root['key']:
        if not root['left']: root['left'] = node
        else: binarySearch(root['left'], node)
    else:
        if not root['right']: root['right'] = node
        else: binarySearch(root['right'], node)

这是我想在幕后发生的事情（为什么一个版本可以添加到BST，而另一个版本不能添加到BST：]

[在原始版本中，我们将到达一个递归调用，其中root仍指向BST中的None，但是root = node使root指向与node绝对没有联系的start BST本身。然后删除局部变量，不做任何更改。

在修改后的版本中，我们将避免这种情况，因为当我们通过例如root['left'] = node。这里root仍指向原始BST，因此我们正在修改原始BST中的键-值对，而不是使root指向完全不在BST之外的东西。

我正在尝试使用python中的dict构建BST（二进制搜索树）。我不明白为什么我的代码没有在BST中添加节点。我在这里看到了类似的帖子：如何在...

Answer 1

就像我们是python解释器一样，让您遍历您的代码。