Итератор python через дерево со списком детей

Ответ 1

Похоже, вы хотите, чтобы итератор действовал как обход дерева. Изучите модуль itertools, и вы действительно можете пойти туда.

from itertools import chain, imap

class t:
  def __init__(self, value):
    self.value = value
    self.children = []
  def __iter__(self):
    "implement the iterator protocol"
    for v in chain(*imap(iter, self.children)):
      yield v
    yield self.value

root = t(0)
root.children.append(t(1))
root.children.append(t(2))
root.children[1].children.append(t(3))
print list(iter(root))   # -> [1, 3, 2, 0]
print list(iter(root.children[1]))  # -> [3, 2]

РЕДАКТИРОВАТЬ. Ниже приведена первоначальная реализация. Он имеет проблемы с производительностью; Я бы удалил его, но было бы неправильно удалить контент, который был принят. Он будет полностью пересекать всю структуру, создавая объекты-генераторы O(N*log[M](N)) (для сбалансированного дерева с коэффициентом ветвления M, содержащим N total elements), прежде чем давать какие-либо значения. Но он дает желаемый результат простым выражением.

(Вышеприведенная реализация посещает области дерева по требованию и имеет только объекты-генераторы O(M+log[M](N)) в памяти одновременно. В обеих реализациях ожидаются только O(log[M](N)) уровни вложенных генераторов.)

from itertools import chain

def isingle(item):
  "iterator that yields only a single value then stops, for chaining"
  yield item

class t:
  # copy __init__ from above
  def __iter__(self):
    "implement the iterator protocol"
    return chain(*(map(iter, self.children) + [isingle(self.value)]))

Ответ 2

Из кода, который вы опубликовали, ясно, что то, что вам не хватает, это то, что делает генератор, и как __iter__ и next должны вести себя

Итак, давайте начнем с протокола итератора. объект итерабельен, если он возвращает итератор, когда вызывается его метод __iter__, а итератор - это объект, который имеет метод next, который может быть вызван ноль или более раз и в конечном итоге должен поднять StopIteration.

Не для некоторых видов объектов не характерны их собственные итераторы (которые имеют __iter__ return self), но обычно это ограничивается объектами, которые каким-то образом сами представляют собой позицию внутри чего-то. Например, встроенный объект file является его собственным итератором, потому что файлы имеют внутреннюю позицию поиска (с которыми вы можете манипулировать с помощью file.seek() и file.tell()). Другие объекты, которые представляют совокупность коллекции, например list, возвращают нечто иное, чем они сами.

Итак, ваше дерево действительно больше похоже на последнее, а не на первое; У него нет атрибута позиции, который представляет, с какими node он включен; все узлы одновременно, поэтому он, вероятно, не должен иметь метод next(); __iter__ нужно вернуть что-то еще.

Что приводит нас к генераторам. Когда нормальная функция содержит инструкцию yield, она автоматически не является функцией вообще, она является генератором. Разница в том, что когда вы вызываете функцию, ее тело выполняется (и, возможно, возвращает значение). Когда вы вызываете генератор, он возвращается немедленно, без выполнения всего тела; вместо этого вы получаете итератор! когда вы перебираете это, тело функции вызывается; переходя к следующему yield каждый раз, пока он окончательно не вернется.

Итак, все вместе,

class t:
    def __init__(self):
        self.l = []
        self.a = 0

    def __iter__(self):
        # first, yield everthing every one of the child nodes would yield.
        for child in self.l:
            for item in child:
                # the two for loops is because there multiple children, and we need to iterate
                # over each one.
                yield item

        # finally, yield self
        yield self

Но, поскольку то, что мы делаем, это итерация последовательности итераторов (а также еще одна вещь, я), itertools.chain, как в принятом ответе, действительно имеет большой смысл.

Ответ 3

Мое первое предложение состоит в том, чтобы изменить название вашего класса с более четким, следуя PEP-8. Было немного сложно управлять именем класса, например t:

class Tree:
    def __init__(self, i):
        self.l = []
        self.a = 0
        for ii in range(i):
            self.a = ii
            self.l.append(Tree(i-1))

Теперь вы должны изменить метод __iter__(), чтобы вернуть следующий элемент в self, а не self сам - каламбур не предназначен:) Метод __iter__() должен возвращать итератор исходному объекту, а не самого объекта:

def __iter__(self):
    return next(self)

Теперь идет сложная часть: метод next(). Мне всегда трудно писать рекурсивные итераторы, но это не так уж и невозможно: для каждого потомка, итерации по нему и получения итерированного значения:

def next(self):
    for i in self.l:
        for ii in i:
            yield ii
    yield self

Поскольку метод рекурсивный, он заботится о том, чтобы уступить все потомки. Когда метод next() вызывается на листе node (a node без детей), он просто вернет сам node. OTOH, когда вызывается с node с детьми, он будет называть себя для каждого ребенка и возвращает возвращаемое значение. Это означает, что он будет вызван детьми детей и т.д. До тех пор, пока узлы листьев не будут. После вызова всех потомков a node, что означает, что все потомки были уступлены, он должен дать свое значение, поэтому вы должны получить исходный node.

Теперь ваша функция printall() должна работать безупречно:

if __name__ == "__main__":
t = Tree(6)
t.printall()

Некоторые окончательные соображения:

• Всегда делайте, чтобы ваши классы расширяли object:

  класс Дерево (объект)::

• Бьюсь об заклад, вы хотите написать метод __init__(), подобный приведенному ниже:

  def __init__(self, i):
      self.l = []
      self.a = i
      for ii in range(i):
          self.l.append(Tree(i-1))
  

• Решение wberry лучше, потому что оно более кратким и, вероятно, более эффективным. Тем не менее, я думаю, что OP изучает деревья, рекурсию и т.д., Поэтому я думал, что более жесткое кодирование будет поучительным:)