0

I am trying to define a recursive method to walk all the nodes of a tree. I defined the Tree as the following:

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)

I have the following function that works:

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

How do I turn this to an instance method?

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

This will result in Max recursion depth error...

a. Is this how do you implement a recursive method?
b. Is there a justification here to use yield?
c. Is there a justification here to use @staticmethod which recieves a Tree instance?

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 に答える