Как использовать генератор для перебора листьев дерева - PullRequest
Новая
       9

Как использовать генератор для перебора листьев дерева

0 голосов
/ 21 сентября 2010

Проблема:

У меня есть три , и я хочу вернуть информацию, хранящуюся в нем.Некоторые листья имеют информацию (устанавливается как значение> 0), а некоторые нет.Я хотел бы вернуть только те листья, которые имеют значение.

Так как во всех трех листьях три на каждом узле является переменной, и ключ к каждому значению фактически состоит из пути, необходимого для достижения каждого листа.

Я пытаюсь использовать генератор для обхода дерева, но не могу заставить его работать.Что я делаю не так?

Мой модуль: 

class Node():
    '''Each leaf in the trie is a Node() class'''
    def __init__(self):
        self.children = {}
        self.value = 0

class Trie():
    '''The Trie() holds all nodes and can return a list of their values'''
    def __init__(self):
        self.root = Node()
    def add(self, key, value):
        '''Store a "value" in a position "key"'''
        node = self.root
        for digit in key:
            number = digit
            if number not in node.children:
                node.children[number] = Node()
            node = node.children[number]
        node.value = value
    def __iter__(self):
        return self.postorder(self.root)
    def postorder(self, node):
        if node:
            for child in node.children.values():
                self.postorder(child)
            # Do my printing / job related stuff here
            if node.value > 0:
                yield node.value

Пример использования: 

>>trie = Trie()
>>trie.add('foo', 3)
>>trie.add('foobar', 5)
>>trie.add('fobaz', 23)

>>for key in trie:
>>....print key
>>
3
5
23

Я знаю, что приведенный пример прост и может быть решен с помощью любогодругая структура данных.Тем не менее, для этой программы важно использовать три, так как это очень полезно для шаблонов доступа к данным.

Спасибо за помощь!

Примечание: я опустил символы новой строки в блоке кодачтобы можно было легко копировать и вставлять.

1 Ответ

2 голосов
/ 21 сентября 2010

Изменение 

self.postorder(child)

на 

for n in self.postorder(child):
    yield n

, кажется, заставляет его работать.

PS Очень полезно, чтобы вы упустили пустые строки для простотывырезать и вставить :)

...