Python w celu przechodzenia do płaskiej listy

Question

Utworzyłem metodę klasy TreeNode, że ja chce powrócić płaską listę in zamówienia przechodzenie drzewa

Moja próbka jest drzewo:

in kolejności wyświetlania przejścia powinny być: [1, 1, 0, 2, 1, 3, 1, 1, 0]

ale dostaję: [2, 1, 1, 0, 1, 3, 1, 1, 0]

Oto mój kod:

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 

Czy ktoś jest w stanie dać mi wskazówkę, dlaczego tak się dzieje?

Dzięki Alex

Answer 1

Zamiast wywoływać self.left/right.in_order_list(), dzwonisz self.left/right.pre_order_list().

Aby osiągnąć to, co chcesz zrobić funkcję generator mogłoby być lepsze (mniej pamięci czasochłonne i bardziej pythonic) niż gromadzenie wartości w liście:

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()) 

ten sposób don” t trzeba utworzyć listę, jeśli chcesz tylko iteracyjne nad wartościami:

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

algorytm działa tak: generator pierwszy schodzi rekurencyjnie wzdłuż lewej gałęzi każdym węźle, dopóki nie natrafi jednego bez lewego pod- węzeł. Następnie generuje wartość bieżącego węzła. Potem robi to samo na prawym pod-węźle, ale zaczynając od bieżącego węzła, a nie węzła głównego. Jeśli założymy, że w drzewie nie ma cykli i nie ma nieskończonych gałęzi, to z pewnością będą to węzły liścia, tj. Węzły bez lewego lub prawego pod-węzła. Węzły IOW, dla których osiągnięto oba podstawowe przypadki (self.left/right is None). Dlatego rekurencyjne wywołania powrócą, miejmy nadzieję, zanim skończy nam się pamięć lub osiągniemy limit stosu.

Pętla nad self.left/right.in_order() jest to konieczne ze względu na fakt, że to, co wezwanie do in_order() zwrotów jest generator, stąd nazwa generator funkcyjny. Zwrócony generator musi zostać jakoś wyczerpany, np. przez pętlę.W ciele pętli ponownie podnosimy wartości do góry o jeden poziom, na którym są ponownie ponawiane, aż osiągną najwyższy poziom. Tam używamy wartości.

Jeśli chcesz pobrać węzły samym sobą, a nie tylko pól ich wartości, można zrobić to tak:

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 

Prawdopodobnie chcesz to zrobić, ponieważ nie tylko można nadal uzyskać dostęp do wartości węzły:

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

ale również możesz robić, co chcesz z węzłami:

for node in tree.in_order(): 
    whatever(node.some_other_attribute) 

Answer 2

To może być problem z domyślnym argumentem dla R = []

Przykład:

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


foo() 
>>> [1] 

foo() 
>>> [1,1] 

Python jest utrzymanie tej samej listy na wielu wywołań funkcji.

Spróbuj podejmowania rozpoczęcia swojej funkcji coś takiego:

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

Możesz też dodawać resztę swojego kodu, dzięki czemu wiemy, co robi, że funkcja pre_order.

Answer 3

A) po pierwsze, jak odnotowano w campos.ddc, przypisanie wartości [] powoduje, że wartość parametru r jest problematyczna. Dokładne informacje na ten skonsultować this answer on Stackoverflow (jest to bardzo wspólny bug)

B) wydaje swój „jeśli ja jest None:” test jest zbędny, jeśli samo było nikogo, nie byłby w stanie wywołać metoda in_order_list (zakładając, że jest to metoda w klasie, a nie samodzielna funkcja)

C) Kod może zostać uproszczona:

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) pytania, które prawdopodobnie "Homework" pytania, należy być oznaczony jako taki. > :(

Answer 4

Można pisać takie rzeczy naprawdę zgrabnie jako generatora i uniknąć konieczności obsługi list i dołączanie:

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 

Na przykład:

>>> 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]