0

这就是我在 Python 中遍历二叉树的方式

def binary_tree(root):
  if root.left:
    binary_tree(root.left)
  print root
  if root.right:
    binary_tree(root.right)

如果我需要返回遍历的路径：

def binary_tree(node, path):
  if root.left:
    binary_tree(root.left)
  path.append(root)
  if root.right:
    binary_tree(root.right)
  return path

好吧，够简单的。我对树遍历很有信心，所以我尝试以下方法。

def nary_tree(root, value):
    """return True if there is a node with value exists in root"""
    if not root: #empty tree
        return False
    if root.left:
        nary_tree(root.left, value)
    if root.data == value: #recurse up until the current node has a right child
        return True
    if root.right:
        nary_tree(root.right, value)
    return False

这不会在应该返回 True 时返回。所以我尝试调试，进入功能。我意识到我不应该仅仅通过返回一个值来逃避递归。上面的代码会多次返回True，False以防有匹配的节点，我几乎总是会得到一个False. 所以我尝试以下方法：

def nary_tree(root, value):
    """return True if there is a node with value exists in root"""
    if not root: #empty tree
        return False
    if root.left:
        return nary_tree(root.left, value)
    if root.data == value:
        #but in this case, this is never executed
        return True 
    if root.right:
        return nary_tree(root.right, value)
    return False #how was this being executed in above example then?

问题：

  1. 我有什么误解？
  2. 你将如何修复上面的代码？

我在编写递归函数方面相当自如，但我似乎仍然感到困惑。

4

1 回答 1

0

即使当前节点有数据，如果它有一个左节点，你就是从函数返回。理想情况下，这应该是这样的

def nary_tree(root, value):
    """return True if there is a node with value exists in root"""
    if not root: #empty tree
        return False
    if root.data == value:
        return True 
    if nary_tree(root.left, value):
        return True
    if nary_tree(root.right, value):
        return True
    return False #how was this being executed in above example then?
于 2013-11-15T02:28:25.653 回答