Câu hỏi:

01/10/2024 127

Ứ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.

Xem lời giải

Câu hỏi trong đề: Chuyên đề Tin 12 CTST Bài 2.4. Thực hành cây tìm kiếm nhị phân !!

Bắt đầu thi

Quảng cáo

Trả lời:

Giải bởi Vietjack

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)

Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay

Sách thầy cô Vietjack biên soạn:

Xem thêm »

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1

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.

Xem đáp án

Lời giải

Để 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, bạn có thể sử dụng thuật toán duyệt giữa (in-order traversal). Thuật toán này sẽ duyệt qua các nút theo trình tự: nút con bên trái, nút gốc, và nút con bên phải. Dưới đây là các bước cụ thể:

Bắt đầu từ nút gốc (38), di chuyển xuống nút con bên trái (17).

Từ nút 17, tiếp tục di chuyển xuống nút con bên trái nhất (15), đây là nút không có con bên trái nên in giá trị 15.

Quay trở lại nút 17 và in giá trị 17.

Di chuyển đến nút con bên phải của nút 17 (24) và in giá trị 24.

Quay trở lại nút gốc 38 và in giá trị 38.

Di chuyển đến nút con bên phải của nút gốc (49), rồi di chuyển xuống nút con bên trái của nó (42) và in giá trị 42.

Cuối cùng, in giá trị của nút 49.

Kết quả của thuật toán duyệt giữa sẽ là dãy số theo thứ tự tăng dần: 15, 17, 24, 38, 42, 49. Đây là cách mà các giá trị nút được xuất ra một cách có trật tự từ cây tìm kiếm nhị phân.

Câu 2