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]