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

#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

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)