Ứng dụng cây tìm kiếm nhị phân để giải bài toán tìm kiếm trang 46 Chuyên đề Tin học 12
Ứng dụng cây tìm kiếm nhị phân để giải bài toán tìm kiếm
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
Nhiệm vụ 1 trang 46 Chuyên đề Tin học 12: Ứ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.
Lời giả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)
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: