Python - Thuật toán duyệt cây
Traversal là một quá trình để truy cập tất cả các nút của một cây và có thể in ra 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 ta luôn bắt đầu từ nút gốc (đầu). Tức là chúng ta không thể truy cập ngẫu nhiên vào một nút trong cây. Có ba cách mà chúng tôi sử dụng để đi qua một cái cây -
- Traversal theo thứ tự
- Đặt hàng trước Traversal
- Giao dịch sau đơn đặt hàng
Traversal theo thứ tự
Trong phương pháp duyệt này, cây con bên trái được truy cập đầu tiên, sau đó đến gốc và sau đó là cây con bên phải. Chúng ta nê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 Node để tạo các trình giữ chỗ cho nút gốc cũng như các nút trái và phải. Sau đó, chúng ta tạo một hàm chèn để thêm dữ liệu vào cây. Cuối cùng, logic duyệt Inorder được thực hiện bằng cách tạo một danh sách trống và thêm nút bên trái trước, sau đó 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 truyền Inorder. 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 duyệt 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 đoạn mã trên được thực thi, nó tạo ra kết quả sau:
[10, 14, 19, 27, 31, 35, 42]Đặt hàng trước Traversal
Trong phương pháp duyệt này, nút gốc được truy cập đầu tiên, sau đó đến 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 Node để tạo các trình giữ chỗ cho nút gốc cũng như các nút trái và phải. Sau đó, chúng ta tạo một hàm chèn để thêm dữ liệu vào cây. Cuối cùng, logic duyệt theo thứ tự trước được thực hiện bằng cách tạo một danh sách trống và thêm nút gốc trước, sau đó là nút bên trái. Cuối cùng, nút bên phải được thêm vào để hoàn tất quá trình đặt hàng 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 duyệt 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 đoạn mã trên được thực thi, nó tạo ra kết quả sau:
[27, 14, 10, 19, 35, 31, 42]Giao dịch 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 đó có tên. Đầu tiên chúng ta duyệt qua cây con bên trái, sau đó đến 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 Node để tạo các trình giữ chỗ cho nút gốc cũng như các nút trái và phải. Sau đó, chúng ta tạo một hàm chèn để thêm dữ liệu vào cây. Cuối cùng, logic duyệt theo thứ tự sau được thực hiện bằng cách tạo một danh sách trống và thêm nút bên trái trước, sau đó 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 quá trình truyền đơn hàng Sau. 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 duyệt 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 đoạn mã trên được thực thi, nó tạo ra kết quả sau:
[10, 19, 14, 31, 42, 35, 27]