Cho cây tìm kiếm nhị phân ở Hình 1.

Ở bài học trước, em đã được giới thiệu về việc giá trị các nút trong cây tìm kiếm nhị phân được sắp xếp theo một trình tự nhất định. Em hãy mô phỏng thuật toán để xuất giá trị các nút của cây tìm kiếm nhị phân trong Hình 1 theo thứ tự tăng dần.

Chương trình để giúp bác thợ mộc tìm thanh gỗ đúng với kích thước đã cho.

Code như sau:

def find_wood_plank(wood_lengths, k):

    Hàm này tìm kiếm thanh gỗ có kích thước k trong danh sách wood_lengths.

    Parameters:

    wood_lengths (list): Danh sách kích thước các thanh gỗ.

    k (int): Kích thước của thanh gỗ cần tìm.

    Returns:

    bool: True nếu tìm thấy thanh gỗ có kích thước k, False nếu không tìm thấy.

    for length in wood_lengths:

        if length == k:

           return True

    return False

# Nhập vào danh sách các kích thước thanh gỗ và kích thước cần tìm

n = int(input("Nhập số lượng thanh gỗ: "))

wood_lengths = []

print("Nhập kích thước của từng thanh gỗ:")

for _ in range(n):

   wood_lengths.append(int(input()))

k = int(input("Nhập kích thước thanh gỗ cần tìm: "))

# Kiểm tra xem có thanh gỗ có kích thước k hay không

if find_wood_plank(wood_lengths, k):

   print(f"Tìm thấy thanh gỗ có kích thước {k} cm.")

else:

   print(f"Không tìm thấy thanh gỗ có kích thước {k} cm.")

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)