Thực hiện trình lặp cây có độ sâu đầu tiên bằng Python

Question

Tôi đang cố gắng triển khai một lớp trình lặp cho các cây không nhất thiết phải nhị phân trong Python. Sau khi trình vòng lặp được xây dựng bằng nút gốc của cây, chức năng next() của nó có thể được gọi lặp lại để di chuyển cây theo thứ tự chiều sâu (ví dụ: this order), cuối cùng trở về None khi không còn nút nào.

Đây là Node lớp cơ bản cho một cây:

class Node(object): 

    def __init__(self, title, children=None): 
     self.title = title 
     self.children = children or [] 
     self.visited = False 

    def __str__(self): 
     return self.title 

Như bạn thấy ở trên, tôi đã giới thiệu một tài sản visited đến các hạch cho cách tiếp cận đầu tiên của tôi, vì tôi đã không nhìn thấy một con đường xung quanh nó . Với biện pháp bổ sung của nhà nước, lớp Iterator trông như thế này:

class Iterator(object): 

    def __init__(self, root): 
     self.stack = [] 
     self.current = root 

    def next(self): 
     if self.current is None: 
      return None 

     self.stack.append(self.current) 
     self.current.visited = True 

     # Root case 
     if len(self.stack) == 1: 
      return self.current 

     while self.stack: 
      self.current = self.stack[-1] 
      for child in self.current.children: 
       if not child.visited: 
        self.current = child 
        return child 

      self.stack.pop() 

này là tất cả tốt và tốt, nhưng tôi muốn để thoát khỏi sự cần thiết của các visited bất động sản, mà không cần đến đệ quy hoặc mọi thay đổi khác đến lớp Node.

Tất cả trạng thái tôi cần phải được xử lý trong trình lặp, nhưng tôi không biết cách thực hiện điều đó. Giữ một danh sách truy cập cho toàn bộ cây là không thể mở rộng và ra khỏi câu hỏi, vì vậy phải có một cách thông minh để sử dụng ngăn xếp.

Điều đặc biệt làm tôi bối rối là - vì chức năng next(), tất nhiên, trả về, làm cách nào tôi có thể nhớ nơi mình đã ở mà không đánh dấu gì hoặc sử dụng bộ nhớ dư thừa? Trực giác, tôi nghĩ về việc lặp lại trẻ em, nhưng logic đó bị hỏng/lãng quên khi hàm next() trả về!

CẬP NHẬT - Đây là một thử nghiệm nhỏ:

tree = Node(
    'A', [ 
     Node('B', [ 
      Node('C', [ 
       Node('D') 
       ]), 
      Node('E'), 
      ]), 
     Node('F'), 
     Node('G'), 
     ]) 

iter = Iterator(tree) 

out = object() 
while out: 
    out = iter.next() 
    print out 

Answer 1

Nếu bạn thực sự phải tránh đệ quy, iterator này hoạt động:

from collections import deque 

def node_depth_first_iter(node): 
    stack = deque([node]) 
    while stack: 
     # Pop out the first element in the stack 
     node = stack.popleft() 
     yield node 
     # push children onto the front of the stack. 
     # Note that with a deque.extendleft, the first on in is the last 
     # one out, so we need to push them in reverse order. 
     stack.extendleft(reversed(node.children)) 

---

Với những gì đã nói, tôi nghĩ rằng bạn đang nghĩ về điều này quá khó. A '(recursive) máy phát điện tốt-ole cũng hiện các trick:

class Node(object): 

    def __init__(self, title, children=None): 
     self.title = title 
     self.children = children or [] 

    def __str__(self): 
     return self.title 

    def __iter__(self): 
     yield self 
     for child in self.children: 
      for node in child: 
       yield node 

cả hai vượt qua các bài kiểm tra của bạn:

expected = ['A', 'B', 'C', 'D', 'E', 'F', 'G'] 
# Test recursive generator using Node.__iter__ 
assert [str(n) for n in tree] == expected 

# test non-recursive Iterator 
assert [str(n) for n in node_depth_first_iter(tree)] == expected 

và bạn có thể dễ dàng thực hiện Node.__iter__ sử dụng hình thức không đệ quy nếu bạn thích :

def __iter__(self): 
    return node_depth_first_iter(self) 

Answer 2

Điều đó vẫn có khả năng giữ lại mọi nhãn. Tôi muốn trình biến lặp chỉ giữ một tập con của cây tại một thời điểm.

Nhưng bạn đã là giữ mọi thứ. Hãy nhớ rằng một đối tượng về bản chất là một từ điển với một mục nhập cho mỗi thuộc tính. Có self.visited = False trong các __init__ của Node có nghĩa là bạn đang lưu trữ một khóa dự phòng "visited" và False giá trị cho mỗi đối tượng Node đơn bất kể là gì. Một tập hợp, ít nhất, cũng có tiềm năng của không giữ mọi ID nút duy nhất.Hãy thử điều này:

class Iterator(object): 
    def __init__(self, root): 
     self.visited_ids = set() 
     ... 

    def next(self): 
     ... 
     #self.current.visited = True 
     self.visited_ids.add(id(self.current)) 
     ... 
       #if not child.visited: 
       if id(child) not in self.visited_ids: 

Tra cứu ID trong tập hợp phải nhanh như truy cập thuộc tính của nút. Cách duy nhất này có thể lãng phí hơn giải pháp của bạn là chi phí của chính đối tượng thiết lập (không phải là các phần tử của nó), mà chỉ là một mối quan tâm nếu bạn có nhiều trình lặp đồng thời (mà bạn rõ ràng là không, nếu không thì thuộc tính node visited couldn không hữu ích cho bạn).