0

我有一个递归方法，用于遍历红黑树，并存储各种节点信息（在 list 中storage）。

def _walk (self, storage, func, starting_node) :
    if starting_node is not self._nil :
        self._walk(storage, func, starting_node.left)
        storage.append(func(starting_node))
        self._walk(storage, func, starting_node.right)

但是，我想重新实现这个方法，以便它构建一个生成器（据我了解，这应该可以节省时间和内存）。这样做的“最佳”方式是什么？

4

2 回答 2

2

首先将动作与行走脱钩

def _walk (self, starting_node) :
    if starting_node is not self._nil :
        for x in self._walk(starting_node.left):
            yield x
        yield starting_node
        for x in self._walk(starting_node.right):
            yield x

def traverse(self):
    starting_node = ???     # maybe these are passed as
    func = ???              # parameters to traverse
    for node in self._walk(starting_node):
        yield func(node)

traverse大致相当于

imap(func, self._walk(starting_node))

或者这个生成器表达式

(func(x) for x in self._walk(starting_node))

您可以通过手动优化尾递归来减少使用的堆栈量

def _walk (self, starting_node) :
    while starting_node is not self._nil :
        for x in self._walk(starting_node.left):
            yield x
        yield starting_node
        starting_node = starting_node.right
于 2012-11-05T03:44:52.457 回答
2 
def _walk (self, func, starting_node) :
    if starting_node is not self._nil :
        for x in self._walk(func, starting_node.left) :
            yield x
        yield func(starting_node)
        for x in self._walk(func, starting_node.right) :
            yield x
于 2012-11-05T03:49:52.697 回答