如何在不使用指针的情况下用Python构建二叉搜索树？

Question

我看到有一些关于“如何构建二叉树”的回答，但这些回答似乎都不太管用！它们的算法大致是这样的：

def insert(item, tree):
    if (item < tree.entry):
        if (tree.left != None):
            insert(item, tree.left)
        else:
            tree.left = Tree(item)
    else:
        if (tree.right != None):
            insert(item, tree.right)
        else:
            tree.right = Tree(item)

之前提到的代码是由Isaac1000写的，其他的代码也很相似。问题在于，当调用下面的“insert”函数时，传入tree.right或tree.left：

insert(item, tree.left)
insert(item, tree.right)

写代码的人以为传的是引用，而不是值的副本，所以tree.left或tree.right实际上并没有被真正改变。最后，这个函数或者类似的函数只在树的第一层或零层有效，而在树的n层就不行了。那么，如何在不使用指针的情况下构建一个二叉搜索树呢？

补充说明一下，我说“没有指针”只是因为我知道Python没有指针，但如果我错了请告诉我。

@qfiard

“如果你把一个可变对象传入一个方法，这个方法会得到对这个对象的引用，你可以随意修改它，但如果你在方法中重新绑定这个引用，外部的作用域就不知道了，等你完成后，外部的引用仍然指向原来的对象。”（Blay Conrad）

这段话让我明白了。我明白了我的代码不管用是因为我习惯于重新绑定tree.left。下面的代码是我一直在用的：

    def insert(self, data):
        if self is None:
            self = Tree(data)
        else:
            if data < self.data:
                Link.insert(self.left, data)
            else:
                Link.insert(self.right, data)

最后，当我写self = Tree(data)时，我试图重新绑定一个对象，而外部作用域对此一无所知。相反，使用我发布的这个方法，当我使用self.right或self.left时，我是在尝试修改对象而不是重新绑定，这样外部作用域就能记住我的更改。

Answer 1

在Python中，参数是通过赋值的方式传递的，这种方式对于可变类型（比如列表、对象等）来说，和通过引用传递参数有点像。想了解更多，可以看看这个StackOverflow的回答：https://stackoverflow.com/a/986145/2887956。

你提供的代码在使用对象来表示树的时候运行得非常好。以下代码的输出是：

<<None, 0, None>, 1, <None, 2, None>>

class Tree(object):

  def __init__(self, entry):
      self.entry = entry
      self.left = None
      self.right = None

  def __str__(self):
      return '<%s, %d, %s>' % (self.left, self.entry, self.right)

def insert(item, tree):
    if item < tree.entry:
        if tree.left is not None:
            insert(item, tree.left)
        else:
            tree.left = Tree(item)
    else:
        if tree.right is not None:
            insert(item, tree.right)
        else:
            tree.right = Tree(item)

root = Tree(1)
insert(0, root)
insert(2, root)
print root

如果你用列表来表示树，你的算法也能工作，不过你需要做一些比较大的修改。