Hướng dẫn how do you traverse through a tree in python? - làm thế nào để bạn đi qua một cái cây trong python?

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

Traversal đặt hàng trước

Traversal sau đơn đặt hàng

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))

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.

[10, 14, 19, 27, 31, 35, 42]

Traversal đặt hàng trước

Traversal sau đơ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.

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))

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.

[27, 14, 10, 19, 35, 31, 42]

Traversal sau đơ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()

# 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))

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.

[10, 19, 14, 31, 42, 35, 27]

Những cách khác nhau để đi qua cây là gì?

4 cách để đi qua một cây nhị phân là gì?

Nó có nghĩa là gì để đi qua một cái cây?