Python để traversal vào một danh sách phẳng

Question

tôi đã tạo ra một phương pháp của một lớp TreeNode mà tôi muốn trả về một danh sách phẳng của một trong trật tự cây traversal

cây mẫu của tôi là:

Các theo thứ tự đầu ra traversal nên là: [1, 1, 0, 2, 1, 3, 1, 1, 0]

nhưng tôi nhận được: [2, 1, 1, 0, 1, 3, 1, 1, 0]

Đây là mã của tôi:

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 

Có ai có thể cho tôi manh mối về lý do điều này xảy ra không?

Cảm ơn Alex

Answer 1

Thay vì gọi self.left/right.in_order_list(), bạn đang gọi điện thoại self.left/right.pre_order_list().

Để thực hiện những gì bạn muốn làm một chức năng phát có thể tốt hơn (ít bộ nhớ tốn và pythonic hơn) để tích lũy các giá trị trong một danh sách:

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

Bằng cách đó, bạn don' t có để tạo ra một danh sách nếu bạn chỉ muốn để lặp qua các giá trị:

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

thuật toán các công trình như thế này: máy phát điện đầu tiên xuống đệ quy dọc theo nhánh bên trái của mỗi nút cho đến khi nó chạm một với không phụ trái nút. Sau đó, nó mang lại giá trị của nút hiện tại. Sau đó nó thực hiện tương tự trên nút con bên phải, nhưng bắt đầu từ nút hiện tại, không phải nút gốc. Nếu chúng ta giả sử không có chu kỳ trong cây và không có nhánh vô hạn, thì chắc chắn sẽ có các nút lá, tức là các nút không có nút con trái hoặc phải. Các nút IOW, mà cả hai trường hợp cơ bản (self.left/right is None) đều đạt được. Vì vậy, các cuộc gọi đệ quy sẽ trở lại, hy vọng trước khi chúng tôi hết bộ nhớ hoặc đạt đến giới hạn ngăn xếp.

Vòng lặp trên self.left/right.in_order() là cần thiết do thực tế rằng những gì các cuộc gọi đến in_order() lợi nhuận là một vì thế tên máy phát chức năng máy phát điện,. Máy phát trả lại phải cạn kiệt bằng cách nào đó, ví dụ: thông qua một vòng lặp.Trong phần thân của vòng lặp, chúng tôi thu lại các giá trị lên một cấp, trong đó chúng được tạo lại một lần nữa, cho đến khi chúng đạt đến cấp cao nhất. Ở đó chúng tôi sử dụng các giá trị.

Nếu bạn muốn lấy các nút themself thay vì chỉ trường giá trị của họ, bạn có thể làm điều đó như thế này:

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 

Bạn có thể muốn làm điều này, bởi vì không chỉ bạn vẫn có thể truy cập vào các giá trị của các nút:

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

nhưng cũng có thể bạn có thể làm bất cứ điều gì bạn muốn với các nút:

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

Answer 2

Nó có thể là một vấn đề với đối số mặc định cho r = []

Ví dụ:

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


foo() 
>>> [1] 

foo() 
>>> [1,1] 

Python được giữ cùng một danh sách trên nhiều chức năng cuộc gọi.

Cố gắng làm cho sự bắt đầu của một cái gì đó chức năng của bạn như:

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

Bạn có thể muốn gửi phần còn lại của mã của bạn, vì vậy chúng ta có thể biết điều đó có chức năng pre_order làm.

Answer 3

A) trước tiên được ghi chú bởi campos.ddc, có giá trị [] được gán giá trị cho tham số r là có vấn đề. Để biết chi tiết về tư vấn này this answer on Stackoverflow (đó là rất lỗi phổ biến)

B) có vẻ như bạn là "không tự:" là không cần thiết, nếu không có, bạn sẽ không thể gọi phương pháp in_order_list (giả sử đây là một phương pháp trong một lớp học, và không phải là một chức năng độc lập)

C) mã này có thể được đơn giản hóa:

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) Câu hỏi có khả năng "bài tập về nhà" câu hỏi, nên được dán nhãn như vậy. > :(

Answer 4

Bạn có thể viết các loại điều này thực sự gọn gàng như một máy phát điện , và tránh việc để xử lý danh sách và phụ thêm:

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 

Ví dụ:

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