Dựa trên hàm BSTSort(A) đã biết, viết chương trình sắp xếp dãy số giảm dần theo kĩ thuật sử dụng cây tìm kiếm nhị phân.

Để sắp xếp dãy số theo thứ tự giảm dần bằng cách sử dụng cây tìm kiếm nhị phân (BST), chúng ta cần thực hiện duyệt ngược (reverse in-order traversal) trên cây. Điều này có nghĩa là chúng ta sẽ duyệt cây theo thứ tự: cây con phải, nút gốc, cây con trái.

Cài đặt hàm BSTSort để sắp xếp giảm dần

1. Định nghĩa cấu trúc nút cây BST

class TreeNode:

    def __init__(self, key):

        self.left = None

        self.right = None

        self.val = key

2. Hàm chèn một phần tử vào BST

def insert(root, key):

    if root is None:

        return TreeNode(key)

    else:

        if root.val < key:

            root.right = insert(root.right, key)

        else:

            root.left = insert(root.left, key)

    return root

3. Hàm duyệt ngược để lấy thứ tự giảm dần

def reverse_in_order_traversal(root, result):

    if root:

        reverse_in_order_traversal(root.right, result)

        result.append(root.val)

        reverse_in_order_traversal(root.left, result)

4. Hàm chính để sắp xếp dãy A theo thứ tự giảm dần

def BSTSortDescending(A):

    if not A:

        return []

    # Bước 1: Tạo cây tìm kiếm nhị phân từ dãy A

    root = None

    for key in A:

        root = insert(root, key)

    # Bước 2: Duyệt cây để lấy kết quả sắp xếp giảm dần

    sorted_result = []

    return sorted_result