2

我正在尝试编写一个函数，它返回二叉树而不是二叉搜索树中的最小值。这是我写的，不正确。

def min(root, min_t): # min_t is the initially the value of root
    if not root:
            return min_t

    if root.key < min_t:
            min_t = root.key

    min(root.left, min_t)
    min(root.right, min_t)

    return min_t

我觉得我不太了解递归。我似乎无法弄清楚何时将 return 语句与递归调用一起使用，何时不使用。

感谢您的见解！

这是我想出的另一个，它有效，但似乎不是最有效的：

n = []
def min_tree(root, n):
    if root:
        n += [(root.key)]
        min_tree(root.left, n)
        min_tree(root.right, n)
    return min(n)

想法？

4

4 回答 4

4

迈克尔的回答解释了您可能应该解决问题的方式，但他没有解释您当前的尝试有什么问题。据我了解，您的策略是检查每个节点，并随时跟踪最低值，使用递归查找所有节点。一旦检查了所有节点，您就会知道结果是整个树的最小值。这是一种完全有效的方法，它本来可以奏效的，只是论点不像您预期​​的那样有效。

Python 按值传递参数，而不是按引用传递。当您使用“min_t = root.key”为 min_t 赋值时，它只在函数内部生效。函数的调用者看不到新值。

您可以使用一些更简单的代码对此进行测试：

def add_one_to(x):
    x = x + 1
    print "add_one_to", x

x = 2
add_one_to(x)
print x

当您运行代码时，您可以看到 x 在函数内部递增，但在顶层没有递增。

这也适用于函数调用自身时。每个调用都有自己的一组局部变量，并且分配给函数内部的局部变量不会影响调用它的实例。

请注意，某些语言确实允许您通过引用传递参数。如果您通过引用传递参数，那么在函数内部分配该参数也会影响调用者。如果 Python 是其中一种语言，您可以将 min_t 作为参考参数，并且您的函数将正常工作。

虽然 Python 不直接支持引用参数，但您也可以将引用参数视为在函数被调用时进入函数并在函数完成时传递回调用者的值。你可以分别做这两件事。要将值传递回调用者，请返回该值。然后调用者可以将该函数分配给它的本地函数，并且您基本上已经通过引用传递了一个参数。

以下是如何将其应用于上面的示例：

def add_one_to(x):
    x = x + 1
    print "add_one_to", x
    return x

x = 2
x = add_one_to(x)
print x

只需添加一个返回值和赋值，它就可以正常工作。

您也可以将其应用于您的原始功能：

def min(root, min_t): # min_t is the initially the value of root
    if not root:
            return min_t

    if root.key < min_t:
            min_t = root.key

    min_t = min(root.left, min_t)
    min_t = min(root.right, min_t)

    return min_t

我所做的只是在每次调用 min() 之前添加“min_t =”，并将您的 return 语句更改为最后返回 min_t。（我认为您可能无论如何都打算返回 min_t。min 是您的函数的名称，所以这没有多大意义。）我相信该版本会起作用。

编辑：尽管如此，您的 min_tree 函数起作用的原因是 n 是一个列表，而列表是可变对象。当我在上面谈论“价值观”时，我真正的意思是“对象”。python 中的每个变量名都映射到一个特定的对象。如果你有这样的代码：

def replace_list(x):
    x = [1, 2, 3]

x = [2]
replace_list(x)
print x

结果是[2]。因此，如果您使用“x =”为 x 分配一个新值，调用者将看不到它。但是，如果您这样做：

def replace_list(x):
    x.append(1)

x = [2]
replace_list(x)
print x

结果是 [2, 1]。这是因为你没有改变 x 的值；x 仍然指向同一个列表。但是，该列表现在包含一个附加值。不幸的是，“+=”运算符在这方面令人困惑。您可能认为“x += y”与“x = x + y”相同，但在 Python 中并非总是如此。如果“x”是一种专门支持“+=”的对象，那么该操作将修改该对象。否则，它将与“x = x + 1”相同。列表知道如何处理“+=”，因此将 += 与列表一起使用会就地修改它，但与数字一起使用则不会。

您实际上可以在不进行任何函数调用的情况下对其进行测试：

x = [1, 2]
y = x
y += [3]
print x # [1, 2, 3]
print y # [1, 2, 3]
print x is y # True, x and y are the same object, which was modified in place

x = [1, 2]
y = x
y = y + [3]
print x # [1, 2]
print y # [1, 2, 3]
print x is y # False, y is a new object equal to x + [3]

x = 1
y = x
y += 2
print x # 1
print y # 3
print x is y # False, y is a new object equal to x + 2
于 2012-04-21T01:05:06.200 回答
1

因为与罐装解决方案相比，您自己尝试解决这个问题会得到更多，所以这里有一些提示。首先，你不应该调用它min，因为当然你不能调用 pythonmin来测试你的结果。正如迈克尔的回答提醒我的那样，您不必通过考试，min_t因为您可以进行测试root.key——但我认为通过考试有助于min_t理解问题。

除此之外，你的第一行是正确的；这里做得很好。：

def tree_min(root, min_t): # min_t is the initially the value of root
    if not root:
            return min_t
    if root.key < min_t:
            min_t = root.key

现在你必须考虑返回什么。基本上，存在三个可能的最小值。第一个是min_t。第二个是right子树的最小值。第三个是left子树的最小值。获取后两个值（这是递归调用进来的地方），然后返回最小值。

于 2012-04-21T00:53:22.517 回答
1

对于这个特定的问题，您想要遍历整个树并返回看到的最小值。但总的来说，递归的基本原理是，当你再次调用函数时，你会看到相同问题的修改版本。

考虑你的树：

    root
   /    \
left   right

当您在左子树上调用递归函数时，您会再次看到一棵树。因此，您应该能够使用相同的逻辑。

递归函数的关键是基本情况和递归步骤。在您的树示例中，基本情况不是您找到最小值（您怎么知道？），而是当您到达树的底部（又名叶子）时。

而且，您的递归步骤是查看每个子问题（bin_min（左）和 bin_min（右））。

最后一块是考虑返回值。不变的是您的函数返回了它所看到的最小元素。因此，当您的递归调用返回时，您知道它是最小元素，然后您需要返回的是三个可能选择（root、left_min 和 right_min）中的最小元素。

def min_bin(root):
    if not root:
        return MAX_VAL
    left_min = min_bin(root.left)
    right_min = min_bin(root.right)

    return min(left_min, right_min, root.val)

请注意，这是与@Rik Poggi 不同的解决方案。他使用尾递归对其进行了一些优化。

于 2012-04-21T00:49:45.250 回答
0

这是一个找到最小元素的递归方法：

minelement = float("inf")
def minimum(self, root):
    global minelement
    if root:
        if root.data < minelement:
            minelement = root.data

        self.minimum(root.left)
        self.minimum(root.right)
    return minelement
于 2017-02-25T17:57:11.697 回答