Python

Question

我正在尝试运行此代码用于在二叉树中搜索元素。它运行良好，但我无法 return 该值但可以显示它。

这是我的代码：

def getNodeAddress(self, data):
        print(self._getNodeAddress(data, self.root))
    
def _getNodeAddress(self, data, root):
        if root:
            if root.data == data:
                print("<<<< ", root.data)
                return root
            self._getNodeAddress(data, root.left)
            self._getNodeAddress(data, root.right)

def _getNodeAddress(self, data, root, res):
        if root:
            if root.data == data:
                print("<<<< ", root.data)
                res = root
            self._getNodeAddress(data, root.left, res)
            self._getNodeAddress(data, root.right, res)
        print(res)
        return res

所以在上面的方法中，它遍历树来寻找作为变量键的值，当它找到一个时，它打印如“print("<<<< ", root.data )”，它确实按预期显示。但是现在，当我需要 return 父方法的值“getNodeAddress”时，问题就出现了。我无法打印父方法中的值。它只是打印“None” 所以我的问题是如何 return 递归的值。

我也尝试了上面代码中方法名相同的第二种方法，但仍然是完全相同的问题任何帮助将不胜感激

Answer 1

看起来只有基本情况实际上是 returning 任何东西。您还需要在 non-base 案例中添加 return 语句。例如：

def _getNodeAddress(self, data, root):
        if root:
            if root.data == data:
                print("<<<< ", root.data)
                return root
            res = self._getNodeAddress(data, root.left)
            if res is None:
                res = self._getNodeAddress(data, root.right)
            return res

Answer 2

二叉树

这棵特定的树性能不佳，因为它在所有分支和节点中执行线性（递归）搜索。这意味着如果您的树有 1,000,000 个节点，则可能需要 1,000,000 次递归才能找到数据。如果您实施了适当的 binary search tree，您可以保证 20 次递归或更少 .

的结果

除此之外，我们仍然可以为您的树实施 find(t, data)，t -

def find(t, data):
  if not t:
    return None
  elif t.data == data:
    return t
  else:
    return find(t.left, data) or find(t.right, data)

因为递归是一种函数式继承，所以将它与函数式风格一起使用会产生最好的结果。这意味着我们避免了突变、变量重新分配和其他副作用。

请注意，此函数并不像您的原始函数名称所暗示的那样return 路径。如果我们想获得树中匹配数据的确切路径，我们可以通过添加默认的 path 参数 -

来实现

def find(t, data, path = ()):
  if not t:
    return None
  elif t.data == data:
    return (*path, t)
  else:
    return find(t.left, data, (*path, t)) or find(t.right, data, (*path, t))

注意 path 如何以空元组开始，()。每个递归步骤将当前树节点 t 追加到路径中，直到最终找到 data 时，将最终节点追加到路径中并 returned.

二叉搜索树

二叉搜索树允许您以对数时间遍历树。这意味着可以提供近乎即时的结果，而普通 (non-search) 二叉树中的相同数据可能会使您的 cpu 陷入停顿。

# bst variant
def find(t, data):
  if not t:
    return None
  elif data < t.data:
    return find(t.left, data)
  elif data > t.data:
    return find(t.right, data)
  else:
    return t

我们也可以为二叉搜索树编写 path 变体 -

# bst variant with path
def find(t, data, path = ()):
  if not t:
    return None
  elif data < t.data:
    return find(t.left, data, (*path, t))
  elif data > t.data:
    return find(t.right, data, (*path, t))
  else:
    return (*path, t)

更多 bst

如果您想阅读更多关于二叉搜索树的内容，我还有一些关于该主题的其他答案 -

Python - 我如何 return 来自递归的值

Python - how do I return value from recurrsion

recursion