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
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?
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 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 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?
Lời giải:
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, bạn có thể sửa lại chương trình sắp xếp trên để thay vì trả về dãy số mới, nó sẽ in trực tiếp các phần tử theo thứ tự tăng dần trong quá trình duyệt cây.
Cài đặt lại hàm để in trực tiếp
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 để in các phần tử theo thứ tự tăng dần
def in_order_traversal_and_print(root):
if root:
in_order_traversal_and_print(root.left)
print(root.val, end=' ')
in_order_traversal_and_print(root.right)
4. Hàm chính để sắp xếp và in dãy A
def BSTSortAndPrint(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 để in các phần tử theo thứ tự tăng dần
in_order_traversal_and_print(root)
print() # Thêm dòng mới sau khi in xong
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: