Viết lại hàm BSTSort(A) thực hiện sắp xếp dãy số A theo thứ tự tăng dần

Giải Chuyên đề Tin 12 Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân - Kết nối tri thức

Câu hỏi 1 trang 45 Chuyên đề Tin học 12: Viết lại hàm BSTSort(A) thực hiện sắp xếp dãy số A theo thứ tự tăng dần nhưng kết quả không cập nhật vào A. Hàm trả lại dãy số mới là dãy vừa được sắp xếp (gồm các phần tử của dãy A).

Lời giải:

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 giữa để lấy thứ tự tăng dần

def in_order_traversal(root, result):

    if root:

        in_order_traversal(root.left, result)

        result.append(root.val)

        in_order_traversal(root.right, result)

4. Hàm chính để sắp xếp dãy A

def BSTSort(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

    sorted_result = []

    in_order_traversal(root, sorted_result)

    return sorted_result

Lời giải bài tập Chuyên đề Tin 12 Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân hay, ngắn gọn khác:

• Khởi động trang 41 Chuyên đề Tin học 12: Quan sát cây tìm kiếm nhị phân trong hình 9.1, cùng trao đổi, thảo luận các câu hỏi sau ....

• Hoạt động 1 trang 41 Chuyên đề Tin học 12: Quan sát cách cài đặt các thuật toán duyệt trên cây tìm kiếm nhị phân và trao đổi về ý nghĩa ....

• Câu hỏi 1 trang 43 Chuyên đề Tin học 12: Cho trước dãy số A = [2,1,9,0,2,1,5]. Tạo cây tìm kiếm nhị phân T từ dãy A ....

• Câu hỏi 2 trang 43 Chuyên đề Tin học 12: Với cây T như Câu 1, nếu thực hiện thuật toán duyệt ngược thì thứ tự các khoá ....

• Hoạt động 2 trang 43 Chuyên đề Tin học 12: Trao đổi, thảo luận để giải bài toán sau: Cho trước dãy số A. Thiết kế thuật toán ....

• Câu hỏi 2 trang 45 Chuyên đề Tin học 12: Nếu không cần cập nhật vào dãy A mà chỉ cần in ra màn hình các phần tử của A ....

• Luyện tập 1 trang 45 Chuyên đề Tin học 12: 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 ....

• Luyện tập 2 trang 45 Chuyên đề Tin học 12: Thuật toán sắp xếp dãy sử dụng cây tìm kiếm nhị phân có độ phức tạp thời gian ....

• Vận dụng 1 trang 45 Chuyên đề Tin học 12: Dựa trên tính chất của cây tìm kiếm nhị phân, hãy viết hàm minimum(T) và maximum ....

• Vận dụng 2 trang 45 Chuyên đề Tin học 12: Viết hàm height(T) tính chiều cao của cây tìm kiếm nhị phân T ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

• Chuyên đề Tin học 12 Bài 10: Thực hành tổng hợp với cây tìm kiếm nhị phân

• Chuyên đề Tin học 12 Bài 11: Khái niệm đồ thị

• Chuyên đề Tin học 12 Bài 12: Biểu diễn đồ thị

• Chuyên đề Tin học 12 Bài 13: Thực hành thiết lập đồ thị

• Chuyên đề Tin học 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều

---