Ứ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

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)