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

đầu ra

Quảng cáo

10  Inserted as root
5  Inserted on left of  10
20  Inserted on right of 10
30  Inserted on right of 20
25  Inserted on left of  30
2  Inserted on left of  5

CONG ĐỌC. Có thể sao chép chuỗi trong Python không?

Inorder Traversal trên cây tìm kiếm nhị phân

Duyệt qua một cây có nghĩa là lặp qua tất cả các nút theo trình tự nào đó. Vì cây không phải là cấu trúc dữ liệu tuyến tính nên sẽ có nhiều hơn một nút tiếp theo có thể có từ một nút hiện tại, vì vậy một số nút sẽ được lưu trữ để chúng ta có thể truy cập chúng sau này. Inorder traversal là một trong những phương pháp duyệt cây theo chiều sâu. Ở đây, trong khi duyệt qua một cây, bất cứ khi nào chúng ta gặp một nút lần đầu tiên, chúng ta duyệt đệ quy sang cây con bên trái của nó trước khi in nút hiện tại, sau đó duyệt đệ quy sang cây con bên phải của nó sau đó

Khi việc chèn được thực hiện trong cây tìm kiếm nhị phân, chúng ta có thể thêm hàm đệ quy được cung cấp bên dưới để duyệt qua cây theo trình tự thứ tự

# Implementing Python Tree Data Structure
# Function for inorder traversal of tree
def inorder(node):
    if node:
	# Traversing left subtree
        inorder(node.left)
	# Visiting node
        print(node.data)
	# Traversing right subtree
        inorder(node.right)

đầu ra

2
5
10
20
25
30

Traversal sắp xếp trước trên cây tìm kiếm nhị phân

Ở đây, khi duyệt qua một cây, bất cứ khi nào chúng ta đi qua một nút lần đầu tiên, chúng ta sẽ truy cập vào nút đó, sau đó chúng ta duyệt đệ quy đến cây con bên trái của nó và sau đó duyệt đệ quy đến cây con bên phải của nó sau đó

Khi việc chèn được thực hiện trong cây tìm kiếm nhị phân, chúng ta có thể thêm hàm đệ quy được cung cấp bên dưới để duyệt qua cây theo thứ tự sắp xếp trước

# Implementing Python Tree Data Structure
# Function for preorder traversal of tree
def preorder(node):
    if node:
	# Visiting node
        print(node.data)
        # Traversing left subtree
        inorder(node.left)
	# Traversing right subtree
        inorder(node.right)

đầu ra

Quảng cáo

10
5
2
20
30
25

CŨNG ĐỌC. Ví dụ về số lượng ngẫu nhiên. rand(). hàm randint()

Postorder Traversal trên cây tìm kiếm nhị phân

Như tên gợi ý, chúng ta sẽ thăm nút sau khi cây con bên trái và cây con bên phải của nó đã được thăm. Trong khi duyệt một cây, bất cứ khi nào chúng ta gặp một nút lần đầu tiên, chúng ta duyệt đệ quy sang cây con bên trái của nó và sau đó duyệt đệ quy sang cây con bên phải của nó và cuối cùng là duyệt nút

Khi việc chèn được thực hiện trong cây tìm kiếm nhị phân, chúng ta có thể thêm hàm đệ quy được cung cấp bên dưới để duyệt qua cây theo trình tự sau

# Implementing Python Tree Data Structure
# Function for postorder traversal of tree
def postorder(node):
    if node:
	# Traversing left subtree
        inorder(node.left)
	# Traversing right subtree
        inorder(node.right)
        # Visiting node
        print(node.data)

đầu ra