递归和返回语句 [英] Recursion and return statements

问题描述

我对 Python 和递归函数还很陌生，请原谅我的无知.

我正在尝试在 Python 中实现一个二叉搜索树并有以下插入方法(从类中取出):

def insert(self, key, root=None):'''在树中插入一个节点'''如果根 == 无:根 = self.root如果 root.key == 无:self._update(root, key)返回 0别的:tmp = 根如果键 >tmp.key: # 我们使用右子树self.insert(key, root=tmp.right)elif 键 

我不确定这是否清晰，但它会遍历树直到达到 None 值并使用要插入的键更新节点.

现在，该方法运行良好且正确地从头开始创建 BST.但是 return 语句有问题，如果没有执行递归，它只返回 0.

<预><代码>>>>bst.insert(10)0>>>bst.insert(15)>>>bst.root.right.key15>>>

再次插入"根键返回 0(来自第 15 行).

<预><代码>>>>bst.insert(10)0

我不明白为什么会发生这种情况.如果我将打印语句放在第 6 行，它会正确执行，但它不会在第一次插入之后返回任何内容.为什么是这样?(我很确定我遗漏了一些关于 Python 和递归的基本信息)

感谢您的帮助，

伊万

P.S.:我读过递归不是实现 BST 的最佳方式，所以我会研究其他解决方案，但我想在继续之前知道答案.

解决方案

在递归行中，您不返回任何内容.如果你想让它返回 0，你应该用类似的行替换它们:

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

而不仅仅是

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

I'm fairly new to Python and recursive functions as a whole, so pardon my ignorance.

I am trying to implement a binary search tree in Python and have the following insert method (taken out of a class):

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

I'm not sure if this is legible, but it traverses the tree until it gets to a None value and updates the node with the key to insert.

Now, the method works nicely and correctly creates a BST from scratch. But there's a problem with the return statements, as it only returns 0 if there is no recursion performed.

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

"Inserting" the root key again returns 0 (from line 15) the way it should.

>>> bst.insert(10)
0

I can't figure out why this happens. If I put a print statement in line 6, it executes correctly, yet it just won't return anything past the first insertion. Why is this? (I'm pretty sure I'm missing some basic information regarding Python and recursion)

Thanks for your help,

Ivan

P.S.: I've read that recursion is not the best way to implement a BST, so I'll look into other solutions, but I'd like to know the answer to this before moving on.

解决方案

On your recursive lines, you do not return anything. If you want it to return 0, you should replace them with lines like:

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

instead of just

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

这篇关于递归和返回语句的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！