Ứ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ử 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)