0

我正在尝试定义一种递归方法来遍历树的所有节点。我将树定义如下：

class Tree(object):

    def __init__(self, value, lson=None, sibling=None):
        self.value = value
        if lson:
            self.lson = Tree(lson)
        else: 
            self.lson = None

        if sibling:
            self.sibling = Tree(sibling)
        else:
            self.sibling = None

    def __str__(self):
        return str(self.value)

我有以下有效的功能：

def walk_tree(t):
    # walk in order
    print t
    if t.lson:
        walk_tree(t.lson)
    if t.sibling:
        walk_tree(t.sibling)
    return t

如何将其转换为实例方法？

def walk_tree(self):
    # walk in order
    print self.value
    if self.lson:
        self.walk_tree(self.lson)
    if self.sibling:
        self.walk_tree(self.sibling)
    return self

这将导致Max recursion depth error...

一个。这是您如何实现递归方法的吗？
湾。这里有理由使用yield吗？
C。这里有理由使用@staticmethod哪个接收Tree实例？

4

1 回答 1

1

您的递归方法不是递归的。它调用一个全局 walk_tree()变量，它本身可能是递归的，也可能不是递归的。

要使方法正确递归，请在子节点上引用该方法：

def walk_tree(self):
    # walk in order
    print self.value
    if self.lson:
        self.lson.walk_tree()
    if self.sibling:
        self.sibling.walk_tree()
    return self

这只会打印值，除了顶级节点之外，它不会向初始调用者返回任何内容。

yield可以帮助有效地访问值，但您确实需要记住产生递归调用：

def walk_tree(self):
    # walk in order
    yield self.value
    if self.lson:
        for res in self.lson.walk_tree():
            yield res
    if self.sibling:
        for res in self.sibling.walk_tree():
            yield res

或者，使用 Python 3.3 或更高版本，使用yield from生成器委托：

def walk_tree(self):
    # walk in order
    yield self.value
    if self.lson:
        yield from self.lson.walk_tree()
    if self.sibling:
        yield from self.sibling.walk_tree()

静态方法只是一个命名空间函数；当然，你原来的walk_tree()全局可以被做成一个静态方法，但是除非你觉得命名空间澄清了你的 API，否则没有什么意义。

于 2014-04-27T08:54:25.853 回答