Chương trình Python tìm phần tử nhỏ nhất và lớn nhất trong cây tìm kiếm nhị phân

Khi cần tìm phần tử nhỏ nhất và lớn nhất trong một cây tìm kiếm nhị phân (Binary Search Tree), ta tạo một lớp cây nhị phân và định nghĩa các phương thức thêm phần tử, tìm kiếm nút cụ thể. Một thể hiện của lớp được tạo và sử dụng các phương thức này.

Ví dụ

class BST_Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None

    def insert_elem(self, node):
        if self.key > node.key:
            if self.left is None:
                self.left = node
                node.parent = self
            else:
                self.left.insert_elem(node)
        elif self.key < node.key:
            if self.right is None:
                self.right = node
                node.parent = self
            else:
                self.right.insert_elem(node)

    def search_node(self, key):
        if self.key > key:
            if self.left is not None:
                return self.left.search_node(key)
            else:
                return None
        elif self.key < key:
            if self.right is not None:
                return self.right.search_node(key)
            else:
                return None
        return self

class BSTree:
    def __init__(self):
        self.root = None

    def add_elem(self, key):
        new_node = BST_Node(key)
        if self.root is None:
            self.root = new_node
        else:
            self.root.insert_elem(new_node)

    def search_node(self, key):
        if self.root is not None:
            return self.root.search_node(key)

    def get_smallest_elem(self):
        if self.root is not None:
            current = self.root
            while current.left is not None:
                current = current.left
            return current.key

    def get_largest_elem(self):
        if self.root is not None:
            current = self.root
            while current.right is not None:
                current = current.right
            return current.key

my_instance = BSTree()
print('Menu (Giả sử không có khóa trùng)')
print('add ')
print('smallest')
print('largest')
print('quit')

while True:
    my_input = input('Thao tác bạn muốn thực hiện? ').split()
    operation = my_input[0].strip().lower()
    if operation == 'add':
        key = int(my_input[1])
        my_instance.add_elem(key)
    if operation == 'smallest':
        smallest = my_instance.get_smallest_elem()
        print('Phần tử nhỏ nhất là: {}'.format(smallest))
    if operation == 'largest':
        largest = my_instance.get_largest_elem()
        print('Phần tử lớn nhất là: {}'.format(largest))
    elif operation == 'quit':
        break

Kết quả

Menu (Giả sử không có khóa trùng)
add 
smallest
largest
quit
Thao tác bạn muốn thực hiện? add 5
Thao tác bạn muốn thực hiện? add 8
Thao tác bạn muốn thực hiện? add 11
Thao tác bạn muốn thực hiện? add 0
Thao tác bạn muốn thực hiện? add 3
Thao tác bạn muốn thực hiện? smallest
Phần tử nhỏ nhất là: 0
Thao tác bạn muốn thực hiện? largest
Phần tử lớn nhất là: 11
Thao tác bạn muốn thực hiện? quit

Giải thích

• Lớp BST_Node với các thuộc tính cần thiết được tạo.

• Phương thức __init__ thiết lập nút trái, phải, cha là None.

• Phương thức insert_elem chèn phần tử vào cây nhị phân.

• Phương thức search_node tìm kiếm nút cụ thể trong cây.

• Lớp BSTree được định nghĩa, gốc (root) đặt là None.

• Phương thức add_elem thêm phần tử vào cây.

• Phương thức search_node tìm kiếm nút cụ thể.

• Phương thức get_smallest_elem lấy nút nhỏ nhất (nhánh trái nhất).

• Phương thức get_largest_elem lấy nút lớn nhất (nhánh phải nhất).

• Một đối tượng của lớp BSTree được tạo.

• Dựa trên thao tác người dùng chọn, thực hiện tương ứng.