Câu hỏi:
01/10/2024 68Cho tập hợp số nguyên dương A = {28, 21, 43, 13, 23, 35, 50, 10, 15, 22, 27, 30, 40, 47, 52).
a) Viết chương trình tạo cây tìm kiếm nhị phân T biểu diễn tập hợp A.
b) Vẽ minh hoạ cây T.
c) Viết chương trình kiểm tra giá trị x = 10 có xuất hiện trong cây tìm kiếm nhị phân T hay không.
d) Viết chương trình xuất ra màn hình các giá trị của tập hợp A được sắp xếp giảm dần.
Sale Tết giảm 50% 2k7: Bộ 20 đề minh họa Toán, Lí, Hóa, Văn, Sử, Địa…. form chuẩn 2025 của Bộ giáo dục (chỉ từ 49k/cuốn).
Quảng cáo
Trả lời:
a) Viết chương trình tạo cây tìm kiếm nhị phân T biểu diễn tập hợp A
Code như sau:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return TreeNode(value)
else:
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def build_bst(values):
root = None
for value in values:
root = insert(root, value)
return root
# Tập hợp số nguyên dương A
A = {28, 21, 43, 13, 23, 35, 50, 10, 15, 22, 27, 30, 40, 47, 52}
# Tạo cây tìm kiếm nhị phân T
root = build_bst(A)
b) Vẽ minh hoạ cây T
Chúng ta sẽ lần lượt chèn các giá trị vào cây BST. Dưới đây là cách cây T sẽ trông như sau khi tất cả các giá trị đã được chèn vào:
javascript
Sao chép mã
c) Viết chương trình kiểm tra giá trị x = 10 có xuất hiện trong cây tìm kiếm nhị phân T hay không
Dưới đây là chương trình kiểm tra giá trị x = 10 có xuất hiện trong cây tìm kiếm nhị phân T hay không:
def search_bst(node, value):
if node is None:
return False
if node.value == value:
return True
elif value < node.value:
return search_bst(node.left, value)
else:
return search_bst(node.right, value)
# Kiểm tra giá trị x = 10
x = 10
if search_bst(root, x):
print(f"Giá trị {x} có trong cây.")
else:
print(f"Giá trị {x} không có trong cây.")
d) Viết chương trình xuất ra màn hình các giá trị của tập hợp A được sắp xếp giảm dần
Dưới đây là chương trình để xuất ra màn hình các giá trị của tập hợp A được sắp xếp giảm dần:
def inorder_traversal(node, result):
if node is not None:
inorder_traversal(node.left, result)
result.append(node.value)
inorder_traversal(node.right, result)
def sorted_descending_bst(root):
result = []
inorder_traversal(root, result)
return sorted(result, reverse=True)
# Xuất ra màn hình các giá trị của tập hợp A được sắp xếp giảm dần
sorted_values = sorted_descending_bst(root)
print("Các giá trị của tập hợp A được sắp xếp giảm dần:")
print(sorted_values)
Tổng hợp chương trình
Dưới đây là chương trình đầy đủ bao gồm tất cả các phần:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return TreeNode(value)
else:
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def build_bst(values):
root = None
for value in values:
root = insert(root, value)
return root
def search_bst(node, value):
if node is None:
return False
if node.value == value:
return True
elif value < node.value:
return search_bst(node.left, value)
else:
return search_bst(node.right, value)
def inorder_traversal(node, result):
if node is not None:
inorder_traversal(node.left, result)
result.append(node.value)
inorder_traversal(node.right, result)
def sorted_descending_bst(root):
result = []
inorder_traversal(root, result)
return sorted(result, reverse=True)
# Tập hợp số nguyên dương A
A = {28, 21, 43, 13, 23, 35, 50, 10, 15, 22, 27, 30, 40, 47, 52}
# Tạo cây tìm kiếm nhị phân T
root = build_bst(A)
# Kiểm tra giá trị x = 10
x = 10
if search_bst(root, x):
print(f"Giá trị {x} có trong cây.")
else:
print(f"Giá trị {x} không có trong cây.")
# Xuất ra màn hình các giá trị của tập hợp A được sắp xếp giảm dần
sorted_values = sorted_descending_bst(root)
print("Các giá trị của tập hợp A được sắp xếp giảm dần:")
print(sorted_values)
Chương trình trên thực hiện các nhiệm vụ yêu cầu từ việc tạo cây tìm kiếm nhị phân, kiểm tra giá trị x = 10, đến việc sắp xếp và xuất ra màn hình các giá trị của tập hợp A theo thứ tự giảm dần.
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Cho cây tìm kiếm nhị phân ở Hình 1.
Ở bài học trước, em đã được giới thiệu về việc giá trị các nút trong cây tìm kiếm nhị phân được sắp xếp theo một trình tự nhất định. Em hãy mô phỏng thuật toán để xuất giá trị các nút của cây tìm kiếm nhị phân trong Hình 1 theo thứ tự tăng dần.
Câu 2:
Ứng dụng cây tìm kiếm nhị phân để giải bài toán tìm kiếm
Yêu cầu: Cho cây tìm kiếm nhị phần (Hình 2) biểu diễn tập hợp số nguyên dương
A = {46, 49, 31, 45, 41, 50, 47, 28, 30, 48}.
Em hãy viết chương trình kiểm tra giá trị x = 41 có xuất hiện trong tập hợp A hay không.
Câu 3:
Tìm thanh gỗ theo yêu cầu
Tại xưởng gỗ, bác thợ mộc cần tìm một thanh gỗ có kích thước là k (cm) trong n thanh gỗ có các kích thước khác nhau để đóng tủ.
Yêu cầu: Để giúp bác thợ mộc tìm thanh gỗ đúng với kích thước đã cho. Hãy viết chương trình.
Câu 4:
Sắp xếp mảng dùng cây tìm kiếm nhị phân
Yêu cầu: Sắp xếp một mảng số nguyên a tăng dần.
Đề thi học kì 1 Tin học 12 Kết nối tri thức có đáp án- Đề 1
263 câu Trắc nghiệm tổng hợp ôn thi tốt nghiệp THPT môn Tin học Chủ đề F. Giải quyết vấn đề với sự trợ giúp của máy tính có đáp án
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 7 có đáp án
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 8 có đáp án
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 10 có đáp án
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 9 có đáp án
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 11 có đáp án
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 14 có đáp án
về câu hỏi!