Tôi có một cấu trúc cây mà tôi cần chuyển đổi thành một danh sách các danh sách. Lớp cho một nút được định nghĩa là [đã loại bỏ chi tiết không liên quan]:
The class for a node is defined as [irrelevant detail removed]:
class TMoveTree: # The nodes of the valid moves tree def __init__[self, parent, data]: self._parent = parent self._children = [] self._data = data # a tuple [start, target]
Cây đại diện cho các động tác hợp lệ cho một trò chơi bảng. Trò chơi có ba con xúc xắc, do đó độ sâu tối đa của cây là 4 [1 cấp cho nút gốc và 1 cho mỗi lần chết,] và mỗi nút có thể có tối đa 15 trẻ em. Sau khi tạo ra và cắt tỉa cây, tôi có một cái cây như dưới đây:
Gốc | _____ [0, 3] & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; | _______ [0, 4] & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; | & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; | _____ [0, 5] & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; | & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; | _____ [3, 8] & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; | & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; | _____ [4, 9] & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; | & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; | _______ [3, 7] & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; | _____ [0, 5] & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; | _____ [7, 12]
|_____ [0, 3]
|_______ [0, 4]
| |_____ [0, 5]
| |_____ [3, 8]
| |_____ [4, 9]
|
|_______ [3, 7]
|_____ [0, 5]
|_____ [7, 12]
Mỗi nút chứa một động tác dưới dạng một tuple đại diện cho các vị trí bảng bắt đầu và kết thúc cho một mảnh trò chơi & nbsp; [ngoài root, có [-1, -1].] Tôi cần chuyển đổi cây này thành một danh sách Danh sách như sau:
- Mỗi nhánh phải là một danh sách các bộ dữ liệu trong nhánh đó, được đặt từ lá đến gốc
- Các danh sách được tạo từ mỗi chi nhánh được thu thập vào một danh sách, thứ tự không liên quan
Đối với cây trên, điều này phải là:
[[[-1, -1], [0,3], [0,4], [0,5]] [[-1, -1], [0,3], [0,4], [ 3,8]] [[-1, -1], [0,3], [0,4], [4,9]] [[-1, -1], [0,3], [3, 3, 7], [0,5]] [[-1, -1], [0,3], [3,7], [7,12]]]]]
[[-1,-1], [0,3], [0,4], [0,5]]
[[-1,-1], [0,3], [0,4], [3,8]]
[[-1,-1], [0,3], [0,4], [4,9]]
[[-1,-1], [0,3], [3,7], [0,5]]
[[-1,-1], [0,3], [3,7], [7,12]]
]
Tôi có chức năng sau cho đến nay:
def tree2list[self]: if len[self._children] == 0: return [self._data] else: node_list = [[self._data] + child.tree2list[] for child in self._children] return node_list
Đầu ra nào:
Output:
[[[-1, -1], [[0, 3], [[0, 4], [0, 5]], [[0, 4], [3, 8]], [[0, 4], [4, 9]]], [[0, 3], [[3, 7], [0, 5]], [[3, 7], [7, 12]]]]]Được định dạng lại cho sự rõ ràng:
[nội tuyến] [[[-1, -1], [[0, 3], [[0, 4], [0, 5]], & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; [[0, 4], [3, 8]], & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; [[0, 4], [4, 9]] & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; ], & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; [[0, 3], [[3, 7], [0, 5]], & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; [[3, 7], [7, 12]] & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; ]]] [/nội tuyến]
[[-1, -1], [[0, 3], [[0, 4], [0, 5]],
[[0, 4], [3, 8]],
[[0, 4], [4, 9]]
],
[[0, 3], [[3, 7], [0, 5]],
[[3, 7], [7, 12]]
]
]
][/inline]
Làm thế nào tôi có thể lấy chức năng 'Tree2List' của mình để xuất danh sách danh sách mong muốn?
Cảm ơn vì bất kì sự giúp đỡ
Dylan
Tôi đang cố gắng lập một danh sách tất cả các mục trong một cây tìm kiếm nhị phân. Tôi hiểu đệ quy nhưng tôi không biết làm thế nào để làm cho nó trả về từng giá trị và sau đó nối nó vào một danh sách. Tôi muốn tạo một hàm gọi là makeList[] sẽ trả về danh sách tất cả các mục trong cây của tôi. Tất cả các chức năng trong các chương trình của tôi hoạt động ngoại trừ hàm makeList[] và được đưa vào để đảm bảo mọi người đều hiểu cấu trúc cơ bản của cách tôi thiết lập cây của mình.
class Node[object]:
def __init__[self, data]:
self.data = data
self.lChild = None
self.rChild = None
class Tree[object]:
def __init__[self]:
self.root = None
def __str__[self]:
current = self.root
def isEmpty[self]:
if self.root == None:
return True
else:
return False
def insert [self, item]:
newNode = Node [item]
current = self.root
parent = self.root
if self.root == None:
self.root = newNode
else:
while current != None:
parent = current
if item < current.data:
current = current.lChild
else:
current = current.rChild
if item < parent.data:
parent.lChild = newNode
else:
parent.rChild = newNode
def inOrder[self, aNode]:
if aNode == None:
pass
if aNode != None:
self.inOrder[aNode.lChild]
print aNode.data
self.inOrder[aNode.rChild]
def makeList[self, aNode]:
a = []
self.inOrder[aNode]
a += [aNode.data]
print a
n = Tree[]
for i in [4,7,2,9,1]:
n.insert[i]
n.makeList[n.root]
Nhìn vào chức năng makeList[] của tôi, tôi có thể thấy tại sao nó không hoạt động nhưng tôi không biết làm thế nào để làm cho nó hoạt động.
CHỈNH SỬA
OK, tôi đã nhận được nó! Và tôi thậm chí còn có hai câu trả lời là:
def makeList[self, aNode, a = []]:
if aNode != None:
self.makeList[aNode.lChild, a]
a += [aNode.data]
self.makeList[aNode.rChild, a]
return a
và
def makeList2[self, aNode]:
if aNode is None:
return []
return self.makeList2[aNode.lChild] + [aNode.data] + self.makeList2[aNode.rChild]
Và nhìn lại tôi có thể thấy rằng tôi không hiểu rất rõ về đệ quy nên đã đến lúc phải đánh những cuốn sách! Có ai có tài nguyên tốt về đệ quy không?
Một câu hỏi khác, vì vậy hãy nói rằng tôi gọi hàm makeList[] của tôi. Khi Python đi qua makeList[], khi nó đến
def tree2list[self]: if len[self._children] == 0: return [self._data] else: node_list = [[self._data] + child.tree2list[] for child in self._children] return node_list1, nó có bắt đầu chạy lại chức năng trong khi nó vẫn hoàn thành chức năng
makeList[] hay mọi thứ dừng lại và nó chỉ bắt đầu lại với nó mới def tree2list[self]: if len[self._children] == 0: return [self._data] else: node_list = [[self._data] + child.tree2list[] for child in self._children] return node_list3?
Tôi hy vọng điều đó đúng.