Cho đến nay tôi có
def tree_iterate[]:
parent, current = None, self.root
lst = []
while current is not None:
if current.left not None:
lst.append[current.item]
parent, current = current, current.left
if current.right not None:
lst.append[current.item]
parent, current = current, current.right
[Xin lỗi về khoảng cách tôi khá mới về điều này]
Tôi không hoàn toàn chắc chắn làm thế nào để lặp lại ở cả hai bên của cây khi dòng điện bên trái và phải, mà không sử dụng đệ quy. Mục tiêu chính của tôi là có một danh sách tất cả các nút trong BSTenter code here này
Đã hỏi ngày 31 tháng 3 năm 2014 lúc 1:55Mar 31, 2014 at 1:55
1
Để có được một danh sách tất cả các nút trong BST lặp đi lặp lại, hãy sử dụng tìm kiếm đầu tiên [BFS]. Lưu ý rằng điều này sẽ không cung cấp cho bạn các nút theo thứ tự được sắp xếp:
queue = [root]
result = []
while queue:
l = queue.pop[0]
result.append[l]
if l.left != None:
queue.append[l.left]
if l.right!= None:
queue.append[l.right]
Nếu bạn muốn các nút theo thứ tự được sắp xếp, bạn sẽ cần mô phỏng việc chuyển đổi hàng đầu bằng cách sử dụng ngăn xếp:
result = []
stack = [root]
while stack:
stack[-1].visited = True
if stack[-1].left != None and not stack[-1].left.visited:
stack.append[stack[-1].left]
else:
node = stack.pop[]
result.append[node]
if stack[-1].right != None:
stack.append[stack[-1].right]
Đã trả lời ngày 31 tháng 3 năm 2014 lúc 2:17Mar 31, 2014 at 2:17
spinlokspinlokspinlok
3,48316 Huy hiệu bạc25 Huy hiệu đồng16 silver badges25 bronze badges
Traversal là một quá trình để truy cập tất cả các nút của cây và cũng có thể in các giá trị của chúng. Bởi vì, tất cả các nút được kết nối thông qua các cạnh [liên kết], chúng tôi luôn bắt đầu từ nút gốc [đầu]. Đó là, chúng ta không thể truy cập ngẫu nhiên một nút trong cây. Có ba cách mà chúng ta sử dụng để đi qua một cây -
- Theo đơn đặt hàng
- Traversal đặt hàng trước
- Traversal sau đơn đặt hàng
Theo đơn đặt hàng
Trong phương pháp truyền tải này, cây con bên trái được truy cập trước, sau đó là gốc và sau đó là cây con bên phải. Chúng ta nên luôn luôn nhớ rằng mọi nút có thể đại diện cho chính một cây con.
Trong chương trình Python dưới đây, chúng tôi sử dụng lớp nút để tạo chủ sở hữu vị trí cho nút gốc cũng như các nút trái và bên phải. Sau đó, chúng tôi tạo một chức năng chèn để thêm dữ liệu vào cây. Cuối cùng, logic chuyển đổi hàng đầu được triển khai bằng cách tạo một danh sách trống và thêm nút bên trái trước đó là nút gốc hoặc nút cha. Cuối cùng, nút bên trái được thêm vào để hoàn thành việc chuyển đổi thứ tự. Xin lưu ý rằng quá trình này được lặp lại cho mỗi cây con cho đến khi tất cả các nút được đi qua.
class Node:
def __init__[self, data]:
self.left = None
self.right = None
self.data = data
# Insert Node
def insert[self, data]:
if self.data:
if data < self.data:
if self.left is None:
self.left = Node[data]
else:
self.left.insert[data]
elif data > self.data:
if self.right is None:
self.right = Node[data]
else:
self.right.insert[data]
else:
self.data = data
# Print the Tree
def PrintTree[self]:
if self.left:
self.left.PrintTree[]
print[ self.data],
if self.right:
self.right.PrintTree[]
# Inorder traversal
# Left -> Root -> Right
def inorderTraversal[self, root]:
res = []
if root:
res = self.inorderTraversal[root.left]
res.append[root.data]
res = res + self.inorderTraversal[root.right]
return res
root = Node[27]
root.insert[14]
root.insert[35]
root.insert[10]
root.insert[19]
root.insert[31]
root.insert[42]
print[root.inorderTraversal[root]]
Khi mã trên được thực thi, nó sẽ tạo ra kết quả sau -
[10, 14, 19, 27, 31, 35, 42]
Traversal đặt hàng trước
Trong phương thức truyền tải này, nút gốc được truy cập trước, sau đó là cây con bên trái và cuối cùng là cây con bên phải.
Trong chương trình Python dưới đây, chúng tôi sử dụng lớp nút để tạo chủ sở hữu vị trí cho nút gốc cũng như các nút trái và bên phải. Sau đó, chúng tôi tạo một chức năng chèn để thêm dữ liệu vào cây. Cuối cùng, logic chuyển đổi trước được triển khai bằng cách tạo một danh sách trống và thêm nút gốc trước đó là nút bên trái. Cuối cùng, nút bên phải được thêm vào để hoàn thành việc chuyển giao trước. Xin lưu ý rằng quá trình này được lặp lại cho mỗi cây con cho đến khi tất cả các nút được đi qua.
class Node:
def __init__[self, data]:
self.left = None
self.right = None
self.data = data
# Insert Node
def insert[self, data]:
if self.data:
if data < self.data:
if self.left is None:
self.left = Node[data]
else:
self.left.insert[data]
elif data > self.data:
if self.right is None:
self.right = Node[data]
else:
self.right.insert[data]
else:
self.data = data
# Print the Tree
def PrintTree[self]:
if self.left:
self.left.PrintTree[]
print[ self.data],
if self.right:
self.right.PrintTree[]
# Preorder traversal
# Root -> Left ->Right
def PreorderTraversal[self, root]:
res = []
if root:
res.append[root.data]
res = res + self.PreorderTraversal[root.left]
res = res + self.PreorderTraversal[root.right]
return res
root = Node[27]
root.insert[14]
root.insert[35]
root.insert[10]
root.insert[19]
root.insert[31]
root.insert[42]
print[root.PreorderTraversal[root]]
Khi mã trên được thực thi, nó sẽ tạo ra kết quả sau -
[27, 14, 10, 19, 35, 31, 42]
Traversal sau đơn đặt hàng
Trong phương thức truyền tải này, nút gốc được truy cập cuối cùng, do đó tên. Đầu tiên chúng tôi đi qua cây con bên trái, sau đó là cây con bên phải và cuối cùng là nút gốc.
Trong chương trình Python dưới đây, chúng tôi sử dụng lớp nút để tạo chủ sở hữu vị trí cho nút gốc cũng như các nút trái và bên phải. Sau đó, chúng tôi tạo một chức năng chèn để thêm dữ liệu vào cây. Cuối cùng, logic truyền tải sau đơn đặt hàng được triển khai bằng cách tạo một danh sách trống và thêm nút bên trái trước tiên là nút bên phải. Cuối cùng, nút gốc hoặc nút cha được thêm vào để hoàn thành việc chuyển đổi sau đơn đặt hàng. Xin lưu ý rằng quá trình này được lặp lại cho mỗi cây con cho đến khi tất cả các nút được đi qua.
class Node:
def __init__[self, data]:
self.left = None
self.right = None
self.data = data
# Insert Node
def insert[self, data]:
if self.data:
if data < self.data:
if self.left is None:
self.left = Node[data]
else:
self.left.insert[data]
elif data > self.data:
if self.right is None:
self.right = Node[data]
else:
self.right.insert[data]
else:
self.data = data
# Print the Tree
def PrintTree[self]:
if self.left:
self.left.PrintTree[]
print[ self.data],
if self.right:
self.right.PrintTree[]
# Postorder traversal
# Left ->Right -> Root
def PostorderTraversal[self, root]:
res = []
if root:
res = self.PostorderTraversal[root.left]
res = res + self.PostorderTraversal[root.right]
res.append[root.data]
return res
root = Node[27]
root.insert[14]
root.insert[35]
root.insert[10]
root.insert[19]
root.insert[31]
root.insert[42]
print[root.PostorderTraversal[root]]
Khi mã trên được thực thi, nó sẽ tạo ra kết quả sau -
[10, 19, 14, 31, 42, 35, 27]