Câu hỏi:
11/10/2026 1
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.
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.
Trả lời:
Giải bởi Vietjack
Để 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
Để 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
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
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:
a) Nếu thực hiện thuật toán duyệt giữa (trái – gốc – phải) thì nút đầu tiên được duyệt là nút nào?
b) Nút cuối cùng được duyệt là nút nào?
c) Thứ tự các nút được duyệt theo thuật toán duyệt giữa sẽ theo thứ tự nào? Em có nhận xét gì về kết quả đạt được? Giải thích vì sao.
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:
a) Nếu thực hiện thuật toán duyệt giữa (trái – gốc – phải) thì nút đầu tiên được duyệt là nút nào?
b) Nút cuối cùng được duyệt là nút nào?
c) Thứ tự các nút được duyệt theo thuật toán duyệt giữa sẽ theo thứ tự nào? Em có nhận xét gì về kết quả đạt được? Giải thích vì sao.
Câu 2:
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 và sự khác biệt khi thực hiện các thuật toán này so với các thuật toán duyệt cây nhị phân đã học trong Bài 6.
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 và sự khác biệt khi thực hiện các thuật toán này so với các thuật toán duyệt cây nhị phân đã học trong Bài 6.
Câu 3:
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 và thực hiện thuật toán duyệt giữa trên cây T. Em hãy cho biết kết quả duyệt là dãy các khoá có thứ tự như thế nào.
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 và thực hiện thuật toán duyệt giữa trên cây T. Em hãy cho biết kết quả duyệt là dãy các khoá có thứ tự như thế nào.
Câu 4:
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á thể hiện trên màn hình như thế nào?
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á thể hiện trên màn hình như thế nào?
Câu 5:
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).
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).
Câu 6:
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 theo thứ tự tăng dần thì cần sửa lại chương trình sắp xếp trên như thế nào?
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 theo thứ tự tăng dần thì cần sửa lại chương trình sắp xếp trên như thế nào?
Câu 7:
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 là bao nhiêu?
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 là bao nhiêu?
Câu 8:
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(T) tính giá trị khoá nhỏ nhất và lớn nhất của cây tìm kiếm nhị phân T.
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(T) tính giá trị khoá nhỏ nhất và lớn nhất của cây tìm kiếm nhị phân T.
Câu 10:
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 sắp xếp lại dãy A theo thứ tự tăng dần hoặc giảm dần.
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 sắp xếp lại dãy A theo thứ tự tăng dần hoặc giảm dần.
Câu hỏi mới nhất
Xem thêm »-
-
-
-
Trong CSDL QL_ThuVien, hãy xác định khóa chính của bảng MƯỢN SÁCH sau. Biết rằng trong một ngày quy định không được mượn một cuốn sách nhiều lần.
Số thẻ Mã số sách Ngày mượn Ngày trả TV-02
TO-012
5/9/2015
30/9/2015
TV-04
TN-103
12/9/2015
15/9/2015
TV-02
TN-102
24/9/2015
5/10/2015
TV-02
TO-012
5/10/2015
...
...
...
...
-
-
-
-
-
-