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
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.
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
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 sử dụng cây tìm kiếm nhị phân.
Lời giải:
Để 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
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: