Cho 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)
Cho 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).
Giải Chuyên đề Tin 12 Bài 2.4: Thực hành cây tìm kiếm nhị phân - Chân trời sáng tạo
Vận dụng trang 48 Chuyên đề Tin học 12: Cho 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.
Lời giả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.
Lời giải bài tập Chuyên đề Tin 12 Bài 2.4: Thực hành cây tìm kiếm nhị phân hay, chi tiết khác: