Python в порядке обхода в плоский список - PullRequest
Новая
       15

Python в порядке обхода в плоский список

6 голосов
/ 24 февраля 2012

Я создал метод класса TreeNode, который хочу вернуть плоский список обхода дерева заказов

Мой пример дерева:

Sample tree data

Вывод порядка следования должен быть: [1, 1, 0, 2, 1, 3, 1, 1, 0]

но я получаю: [2, 1, 1, 0, 1, 3, 1, 1, 0]

Вот мой код: 

def in_order_list(self, r = []):
    hasLeft = self.left is not None
    hasRight = self.right is not None
    if self is None:
        return
    else:
        if hasLeft:
            self.left.in_order_list(r)
        r.append(self.value)
        if hasRight:
            self.right.in_order_list(r)
    return r

Кто-нибудь сможет подсказать мне, почему это происходит?

Спасибо, Алекс

Ответы [ 4 ]

4 голосов
/ 24 февраля 2012

Вместо того, чтобы звонить self.left/right.in_order_list(), вы звоните self.left/right.pre_order_list().

Чтобы выполнить то, что вы хотите сделать, функция генератора может быть лучше (менее потребляет память и более питонна), чем накапливать значения в списке: 

class Tree(object):
    ...
    def in_order(self):
        if self.left is not None:
            for value in self.left.in_order():
                yield value
        yield self.value  #  <-- yielding the value of the node, not the node itself
        if self.right is not None:
            for value in self.right.in_order():
                yield value

...

tree = Tree(...)

in_order_values = list(tree.in_order())

Таким образом, вам не нужно создавать список, если вы хотите перебирать только значения: 

for value in tree.in_order():
    ...

Алгоритм работает следующим образом: генератор сначала рекурсивно спускается вдоль левой ветви каждого узла, пока не достигнет одного без левого подузла. Затем он возвращает значение текущего узла. После этого он делает то же самое на правом подузле, но начинается с текущего узла, а не с корневого узла. Если мы предположим, что в дереве нет циклов и бесконечных ветвей, то определенно будут листовые узлы, то есть узлы без левого или правого подузла. Узлы IOW, для которых достигаются оба базовых случая (self.left/right is None). Поэтому рекурсивные вызовы вернутся, надеюсь, до того, как у нас не хватит памяти или не достигнет предела стека.

Цикл по self.left/right.in_order() необходим в связи с тем, что возвращаемый вызов in_order() является генератором, отсюда и название функция генератора . Возвращенный генератор должен быть как-то исчерпан, например, через петлю. В теле цикла мы заново выводим значения на один уровень, где они снова возвращаются, пока не достигнут верхнего уровня. Там мы используем значения.

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

class Tree(object):
    ...
    def in_order(self):
        if self.left is not None:
            for node in self.left.in_order():
                yield node
        yield self  #  <-- yielding the node itself
        if self.right is not None:
            for node in self.right.in_order():
                yield node

Вероятно, вы захотите сделать это, потому что вы не только можете получить доступ к значениям узлов: 

for node in tree.in_order():
    do_something_with(node.value)

но вы также можете делать с узлами все, что захотите: 

for node in tree.in_order():
    whatever(node.some_other_attribute)
2 голосов
/ 24 февраля 2012

Вы можете писать такие вещи действительно аккуратно, как генератор , и избежать необходимости обрабатывать списки и добавлять: 

 def in_order(tree):
    if tree is None: return

    for value in in_order(tree.left): yield value
    yield tree.value
    for value in in_order(tree.right): yield value

Например: 

>>> class Node(object):
...     def __init__(self, value, left=None, right=None):
...             self.value, self.left, self.right = value, left, right
... 
>>> x = Node(3)
>>> x.left = Node(2)
>>> x.left.left = Node(1)
>>> x.left.left.left = Node(1)
>>> x.left.left.right = Node(0)
>>> x.left.right = Node(1)
>>> x.right = Node(1)
>>> x.right.left = Node(1)
>>> x.right.right = Node(0)
>>> 
>>> in_order(x)
<generator object in_order at 0xb742dbbc>
>>> list(in_order(x))
[1, 1, 0, 2, 1, 3, 1, 1, 0]
2 голосов
/ 24 февраля 2012

Это может быть проблема с аргументом по умолчанию для r = []

Пример: 

def foo(list=[]):
    list.append(1)
    print list


foo()
>>> [1]

foo()
>>> [1,1]

Python сохраняет один и тот же список для нескольких вызовов функций.

Попробуйте сделать запуск вашей функции примерно таким: 

def in_order_list(self, r=None):
    if r is None:
        r = []

Возможно, вы захотите опубликовать оставшуюся часть кода, чтобы мы могли знать, что делает эта функция pre_order.

1 голос
/ 24 февраля 2012

A) во-первых, как отмечается в campos.ddc, присвоение [] значения параметру r проблематично. Подробнее об этом см. этот ответ по Stackoverflow (это очень распространенная ошибка)

B) может показаться, что ваш тест "if self is None:" является избыточным, если self является None, вы не сможете вызывать метод in_order_list (при условии, что это метод в классе, а не отдельный функция)

C) Код может быть упрощен: 

def in_order_list(self, r = None):
    if not r:
        r = []
    if self.left:
        self.left.in_order_list(r)
    r.append(self.value)
    if self.right:
        self.right.in_order_list(r)

D) Вопросы, которые, вероятно, являются «домашними», должны быть помечены как таковые. >: (* ​​1013 *

...