Python - Cây nhị phân

Cây đại diện cho các nút được kết nối bởi các cạnh. Nó là một cấu trúc dữ liệu phi tuyến tính. Nó có các thuộc tính sau.

• Một nút được đánh dấu là nút gốc.
• Mọi nút khác với nút gốc đều được liên kết với một nút cha.
• Mỗi nút có thể có một số hỗn hợp của nút chid.

Chúng tôi tạo cấu trúc dữ liệu dạng cây trong python bằng cách sử dụng nút hệ điều hành khái niệm đã thảo luận trước đó. Chúng tôi chỉ định một nút làm nút gốc và sau đó thêm các nút khác làm nút con. Dưới đây là chương trình để tạo nút gốc.

Tạo gốc

Chúng tôi chỉ tạo một lớp Node và thêm gán giá trị cho nút. Nó trở thành cây chỉ có một nút gốc.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data


    def PrintTree(self):
        print(self.data)

root = Node(10)

root.PrintTree()

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

10

Chèn vào cây

Để chèn vào một cây, chúng ta sử dụng cùng một lớp nút đã tạo ở trên và thêm một phương thức chèn vào nó Phương thức insert so sánh giá trị của nút với nút cha và quyết định thêm nó làm nút trái hay nút phải. Cuối cùng, phương thức PrintTree được sử dụng để in cây.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
# Compare the new value with the parent node
        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()

# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)

root.PrintTree()

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau:

3 6 12 14

Đi ngang qua cây

Cây có thể được duyệt qua bằng cách quyết định trình tự truy cập mỗi nút. Như chúng ta có thể thấy rõ ràng, chúng ta có thể bắt đầu tại một nút sau đó truy cập vào cây con bên trái đầu tiên và cây con bên phải tiếp theo. Hoặc chúng ta cũng có thể thăm cây con bên phải trước và cây con bên trái tiếp theo. Theo đó, có nhiều tên gọi khác nhau cho các phương pháp truyền tải cây này. Chúng ta nghiên cứu chúng chi tiết trong chương thực hiện các thuật toán duyệt cây ở đây. Thuật toán duyệt cây