Python đặt hàng cây

Cây là một cấu trúc dữ liệu phi tuyến tính trong đó các nút được kết nối theo cách phân cấp. Mỗi cây có một nút gốc đánh dấu điểm truy cập của tất cả các nút khác trong cây. Vì vậy, Cây được hình thành từ một nút gốc và 0 hoặc nhiều nút con. Các cây được phân loại thành các loại khác nhau trên cơ sở cấu trúc và loại dữ liệu của chúng. Chúng là Cây nhị phân, Cây tìm kiếm nhị phân, Cây AVL, Cây B, Cây B+, Cây biểu thức, v.v.

Hình dưới đây cho thấy cấu trúc của Cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân là cây nhị phân đặc biệt bao gồm 0, 1 hoặc 2 nút con và tuân theo các quy tắc nhất định khi chèn giá trị vào nút. Cây tìm kiếm nhị phân là cây nhị phân trong đó tất cả các nút tuân theo các thuộc tính được đề cập bên dưới

1. Tất cả các nút ở bên trái của nút hiện tại có giá trị nhỏ hơn nút hiện tại
2. Tất cả các nút ở bên phải của nút hiện tại có giá trị lớn hơn nút hiện tại

CONG ĐỌC. Các toán tử Python được giải thích chi tiết bằng các ví dụ

Ở đây, chúng ta sẽ xem cách triển khai cây tìm kiếm nhị phân từ đầu trong Python

Tạo một nút

Để tạo Cấu trúc dữ liệu cây Python nhị phân, trước tiên chúng ta sẽ phải tạo một lớp Nút đại diện cho một nút. Lớp Node này sẽ có 3 biến lớp. Biến bên trái trỏ đến nút con bên trái, biến bên phải trỏ đến nút con bên phải và biến dữ liệu chứa giá trị thực cho nút đó. Đoạn mã dưới đây cho thấy lớp đại diện cho một nút

# Implementing Python Tree Data Structure
# Creating a class for node object
class Node[object]:
    # Initializing to None
    def __init__[self]:
        self.left = None
        self.right = None
        self.data = None

Triển khai chèn vào cây tìm kiếm nhị phân

Để chèn một nút vào cây tìm kiếm nhị phân, chúng ta cần đảm bảo rằng không có thuộc tính nào của cây tìm kiếm nhị phân bị vi phạm khi chèn nút

Ở đây, mỗi lệnh gọi phương thức chèn sẽ chèn một nút vào cây tìm kiếm nhị phân. Lệnh gọi chèn đầu tiên sẽ biến nút đó thành nút gốc. Tất cả các lần chèn khác sẽ diễn ra khi xem xét giá trị của nút gốc.
Mã bên dưới hiển thị chức năng chèn đặt nút vào cây sao cho không thuộc tính nào của cây tìm kiếm nhị phân bị vi phạm.

# Implementing Python Tree Data Structure
# Creating a class for node object
class Node[object]:
    # Initializing to None
    def __init__[self]:
        self.left = None
        self.right = None
        self.data = None

# Inserting a node in Binary search tree
def insertion[val]:
    # Condition if this is a first node then it will be considered as a root
    if[root.data==None]:
        print[val," Inserted as root"]
        root.data=val
    # Else part will be executed for all the other insertions
    else:
        # Pointer to move around tree to search for a place of new node
        p=root
        
        # Creating a new node and writing a value in the data part
        n = Node[]
        n.data=val
        
        # Iterating to search for an appropriate place of new node
        while[1]:
            # if val is less than the current node p indicates that new node will be inserted on left subtree
            if[val