2

我是 Python 的初学者，并试图了解生成器，特别是使用 yield 语句。通过编写一些存储键和数据的经典树类来玩耍。

#!/usr/bin/env python3

class Tree:
    def __init__(self, key, data):
        "Create a new Tree object with empty L & R subtrees."
        self.key = key
        # store passed data
        self.data = data
        self.left = self.right = None

    def insert(self, key, data):
        "Insert a new element and data into the tree in the correct position."
        if key < self.key:
            if self.left:
                self.left.insert(key,data)
            else:
                self.left = Tree(key, data)
        elif key > self.key:
            if self.right:
                self.right.insert(key, data)
            else:
                self.right = Tree(key, data)
        else:
            raise ValueError("Attempt to insert duplicate value")

    def walk(self):
        "Generate the keys and data from the tree in sorted order."
        if self.left:
            for n in self.left.walk():
                yield n
        # change output to include data
        yield self.key,self.data
        if self.right:
            for n in self.right.walk():
                yield n

到目前为止，这工作得很好。现在我正在尝试实现一个 find() 函数，该函数遍历树并返回找到的键的数据。

def find(self, key):
    if self.left:
        for n in self.left.find(key):
            yield n

    if self.right:
        for n in self.right.find(key):
            yield n

    if self.key == key:
        yield self.data

KeyError该功能有效 - 但如果在树中找不到密钥，我想提出 a 。我试图绕开它，但在使用 yield 语句时我没有看到一个（简单的）方法来做到这一点。具体来说，我似乎无法想出一种方法来真正知道树什么时候已经完全行走并且仍然没有找到钥匙。

提前致谢！

4

2 回答 2

2

我注意到这find并没有使用树已排序的事实。这个实现怎么样：

def find(self, key):
    if key == self.key:
        return self.data
    if key < self.key and self.left:
        return self.left.find(key)
    if key > self.key and self.right:
        return self.right.find(key)
    raise KeyError("No such thing")
于 2012-06-20T16:04:18.013 回答
1

将当前的 find() 重命名为 _find()，然后：

def find(self, key):
    gen = self._find(key)
    try:
        yield gen.next()
    except StopIteration:
        raise KeyError(key)
    for item in gen:
        yield item
于 2012-06-20T15:55:59.473 回答