递归与返回语句

Question

我刚接触Python和递归函数，所以请多包涵。

我正在尝试在Python中实现一个二叉搜索树，并且有一个插入方法（从类中提取出来的）：

def insert(self, key, root=None):
    '''Inserts a node in the tree'''
    if root == None:
        root = self.root
    if root.key == None:
        self._update(root, key)
        return 0
    else:
        tmp = root
        if key > tmp.key: # we work with the right subtree
            self.insert(key, root=tmp.right)
        elif key < tmp.key: # we work with the left subtree
            self.insert(key, root=tmp.left)
        else: # key already exists
            return 0

我不确定这个代码是否容易理解，但它会遍历树，直到找到一个空值（None），然后用要插入的键更新节点。

这个方法运行得很好，确实可以从零开始创建一个二叉搜索树。但是返回值有问题，因为只有在没有进行递归时，它才会返回0。

>>> bst.insert(10)
0
>>> bst.insert(15)
>>> bst.root.right.key
15
>>>

再次“插入”根节点时，返回0（来自第15行），这也是应该的。

>>> bst.insert(10)
0

我搞不清楚为什么会这样。如果我在第6行放一个打印语句，它会正确执行，但就是在第一次插入后不再返回任何东西。这是为什么呢？（我觉得我对Python和递归的一些基本知识还不太了解）

谢谢你的帮助，

伊万

附言：我听说递归不是实现二叉搜索树的最佳方法，所以我会考虑其他解决方案，但我想在继续之前先弄清楚这个问题。

Answer 1

在你的递归情况下，需要有一个返回语句。试试做这个调整。

def insert(self, key, root=None):
    '''Inserts a node in the tree'''
    if root == None:
        root = self.root
    if root.key == None:
        self._update(root, key)
        return 0
    else:
        tmp = root
        if key > tmp.key: # we work with the right subtree
            return self.insert(key, root=tmp.right)
        elif key < tmp.key: # we work with the left subtree
            return self.insert(key, root=tmp.left)
        else: # key already exists
            return 0

Answer 2

你在一个函数里，想要返回一个值，那你该怎么做呢？你可以写

def function():
    return value

在你的情况下，你想返回一个函数调用的结果，所以你需要这样做。

def function():
    return another_function()

但是如果你这样做

def function():
    another_function()

你觉得这样可以吗？当然你使用了递归，但在这种情况下，你应该记住Python的一个原则，它简单地说：

特殊情况也不能打破规则。

Answer 3

在你的递归代码中，你没有返回任何东西。如果你想让它返回0，你应该把那些地方换成这样的代码：

return self.insert(key, root=tmp.left)

而不是仅仅这样写：

self.insert(key, root=tmp.left)