Câu hỏi:
01/10/2024 67Ứ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.
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Sử dụng chương trình tạo cây tìm kiếm nhị phân và chương trình con tìm kiếm
ở Bài 2.3 để thực hiện yêu cầu trên.
Mã nguồn tham khảo:
#Tìm x trên cây tìm kiếm nhị phân T gốc i
def search(T, i, x):
if i = len(T) or T[i] == None:
return False
elif T[i]== X:
return True
elif x <T[i]:
#Cây T gốc i là rỗng
“Không tìm thấy x
#Tìm thấy x
else:
return search (T, 2*1+1, x)
return search(T, 2*1+2, x)
#Tìm x trên cây con trái
#Tìm x trên cây con phải
#Thêm giá trị v vào cây tìm kiếm nhị phân T gốc i def insertTree(T, i, v):
if i>=len(T):
T.extend([None]*(i-len(T)+1))
if T[i]
== None:
T[i] = V
elif v == T[i]:
print("Đã tồn tại nút có giá trị bằng", v)
elif v<T[i]:
else:
insertTree(T, 2*i + 1, v)
insertTree(T, 2*i + 2, v)
#Tạo cây tìm kiếm nhị phân T từ mảng a def createBSTTree(T, a): for i in range(len(a)):
insertTree(T, 0, a[i])
def printTree(T):
for i in T:
if i!=None:
print(1, end=" ")
def inOrderTraversal (tree, i):
if i < len(tree) and tree[i] != None: inOrderTraversal (tree, 2*i + 1) print(tree[i], end = ')
inOrderTraversal (tree, 2*i + 2)
print("nhập danh sách các số để tạo cây: ")
a = list(map(int, input().split())) print("nhập giá trị cần tìm: ") x= int(input())
T = []
#Thêm a[i] vào cây T
#Cây gốc i khác rỗng #Duyệt cây con trái HXử lí nút gốc #Duyệt cây con phải
createBSTTree (T,a)
A printTree(T) 43. print()
print (search (T, 0,
để trời sáng tạo
inOrderTraversal (T,0)
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:
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 3:
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.
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.
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 KNTT Bài 7: HTML và cấu trúc trang web
15 câu Trắc nghiệm Tin học 12 KNTT Bài 10: Tạo liên kết
15 câu Trắc nghiệm Tin học 12 KNTT Bài 8: Định dạng văn bản
15 câu Trắc nghiệm Tin học 12 KNTT Bài 11: Chèn tệp tin đa phương tiện và khung nội tuyến vào trang web
15 câu Trắc nghiệm Tin học 12 KNTT Bài 9: Tạo danh sách, bảng
15 câu Trắc nghiệm Tin học 12 Cánh diều Bài 1: Làm quen với ngôn ngữ đánh dấu siêu văn bản
Đề thi Học kì 1 Tin học 12 có đáp án (Đề 1)
về câu hỏi!