Ứ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

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:

• Khởi động trang 46 Chuyên đề Tin học 12: Cho cây tìm kiếm nhị phân ở Hình 1 ....

• Nhiệm vụ 2 trang 47 Chuyên đề Tin học 12: Sắp xếp mảng dùng cây tìm kiếm nhị phân ....

• Luyện tập trang 48 Chuyên đề Tin học 12: Tìm thanh gỗ theo yêu cầu ....

• 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) ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Chân trời sáng tạo hay, chi tiết khác:

• Chuyên đề Tin 12 Bài 3.1: Các khái niệm cơ bản của đồ thị

• Chuyên đề Tin 12 Bài 3.2: Biểu diễn đồ thị

• Chuyên đề Tin 12 Bài 3.3: Duyệt đồ thị theo chiều rộng

• Chuyên đề Tin 12 Bài 3.4: Duyệt đồ thị theo chiều sâu

• Chuyên đề Tin 12 Bài 3.5: Thực hành kĩ thuật duyệt đồ thị

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều

---