2

私はPythonの初心者で、ジェネレーター、特にyieldステートメントを使用して頭を悩ませようとしています。キーとデータを格納する古典的な Tree クラスを書いて遊んでみます。

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