Trình bày thuật toán xác định giá trị * = 34 có thuộc cây tìm kiếm nhị phân

Giải Chuyên đề Tin 12 Bài 2.3: Cây tìm kiếm nhị phân - Chân trời sáng tạo

Luyện tập 2 trang 44 Chuyên đề Tin học 12: Trình bày thuật toán xác định giá trị * = 34 có thuộc cây tìm kiếm nhị phân được biểu diễn ở Hình 4b hay không.

Lời giải:

Thuật toán để xác định giá trị * = 34 có thuộc cây tìm kiếm nhị phân được biểu diễn ở Hình 4b hay không được thực hiện bằng cách duyệt cây từ gốc xuống đến khi tìm thấy giá trị hoặc đến khi không còn nút nào để duyệt.

Thuật toán như sau:

Cách 1: Sử dụng các phép toán duyệt trước, duyệt giữa, duyệt sau để xác định giá trị x = 34 có thuộc cây tìm kiếm nhị phần ở Hình 4 hay không.

Ví dụ: Sử dụng phép duyệt trước để tìm giá trị x

def insertTree(T, i, v):

if 1 >= len(T):

T.extend([None]*(i-len(T)+1))

if T[i]== None:

T[i]= v== quân thi sáng ngà

print("Đã tồn tại nút có giá trị bằng", v)

elif v<T[i]:

insertTree(T, 2*1+ 1, v)

else:

insertTree(T, 2*i +2, v)

def createBSTTree(T, a):

for v in a:

insertTree (T, 0, v)

def preorderSearch (T, i, x):

global found

if i < len(T) and T[1] != None: if T[i] == x:

found = True

return

else:

preorderSearch(T, 2*i + 1, x)

preorderSearch(T, 2*1 + 2, x)

def Search(T, x):

global found

found = False

preorderSearch(T, 0, x) return found

a =list(map (int, input().split()))

x = int(input())

T = []

createBSTTree(T, a)

found Search(T, x)

print (found)

Cách 2: Sử dụng thuật toán đệ quy search(T, i, x) để tìm kiếm x trên cây tìm kiếm nhị phân T gốc i.

Mã nguồn hàm tìm kiếm giá trị trên cây tìm kiếm nhị phân sử dụng đệ quy:

Em có thể sử dụng đệ quy hoặc vòng lặp để tìm một nút trên cây tìm kiếm nhị phần. Hàm đệ quy search(T, i, x) dùng để tìm kiếm giá trị x trên cây tim kiếm nhị phần T gốc i.

#Tìm x trên cây tìm kiếm nhị phân T gốc 1

def search(T, i, x):

if i >= len(T) or T[i] == None:

return False

X:

#Cây T gốc i là rỗng #không tìm thấy x

#Tìm thấy x

elif T[i]

return True

elif x <T[i]:

else:

return search(T, 2*1+2, x)

#Tim x trên cây con phải

return search(T, 2*1+1, x)

#Tim x trên cây con trái

Lời giải bài tập Chuyên đề Tin 12 Bài 2.3: Cây tìm kiếm nhị phân hay, chi tiết khác:

• Khởi động trang 40 Chuyên đề Tin học 12: Cho tập hợp A gồm các số nguyên dương A = (6, 14, 10, 34, 40, 30, 46, 20, 24, 22} được lưu ....

• Câu hỏi trang 41 Chuyên đề Tin học 12: Hình nào trong Hình 3 biểu diễn cây tìm kiếm nhị phân ....

• Câu hỏi trang 44 Chuyên đề Tin học 12: Cho mảng A = [5, 7, 30, 23, 34, 15]. Hãy vẽ cây tìm kiếm nhị phân biểu diễn mảng A ....

• Luyện tập 1 trang 44 Chuyên đề Tin học 12: Em hãy vẽ cây tìm kiếm nhị phân bằng cách đưa vào cây rỗng lần lượt các phần tử ....

• Vận dụng 1 trang 45 Chuyên đề Tin học 12: Cho cây tìm kiếm nhị phân như Hình 9. Em hãy thực hiện ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Chân trời sáng tạo hay, chi tiết khác:

• Chuyên đề Tin 12 Bài 2.4: Thực hành cây tìm kiếm nhị phân

• Chuyên đề Tin 12 Bài 3.1: Các khái niệm cơ bản của đồ thị

• Chuyên đề Tin 12 Bài 3.2: Biểu diễn đồ thị

• Chuyên đề Tin 12 Bài 3.3: Duyệt đồ thị theo chiều rộng

• Chuyên đề Tin 12 Bài 3.4: Duyệt đồ thị theo chiều sâu

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều
• Giải lớp 12 Kết nối tri thức (các môn học)
• Giải lớp 12 Chân trời sáng tạo (các môn học)
• Giải lớp 12 Cánh diều (các môn học)

---