Câu hỏi:
26/06/2024 15Cho trước dãy A bao gồm các số nguyên và các giá trị None. Viết chương trình kiểm tra xem A có phải là biểu diễn của một cây tìm kiếm nhị phân hay không.
Ví dụ:
Dãy [5, 3, 6, None, 4, None, 10] là biểu diễn của cây tim kiếm nhị phân.
Dãy [2, 1, 5, None, 3, 4, 10] không là biểu diễn của cây tìm kiếm nhị phân (mặc dù dãy này là biểu diễn của cây nhị phân hoàn chỉnh đã biến đổi).
Siêu phẩm 30 đề thi thử THPT quốc gia 2024 do thầy cô VietJack biên soạn, chỉ từ 100k trên Shopee Mall.
Quảng cáo
Trả lời:
Để kiểm tra xem một dãy đã cho có phải là biểu diễn của một cây tìm kiếm nhị phân hay không, có thể sử dụng một thuật toán kiểm tra tính chất của cây tìm kiếm nhị phân.
Một cây tìm kiếm nhị phân có tính chất sau:
Dựa trên các tính chất trên chương trình sẽ được viết như sau:
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def is_binary_search_tree(arr):
def helper(index, min_val, max_val):
if index >= len(arr) or arr[index] is None:
return True
if min_val < arr[index] < max_val:
left_child_index = 2 * index + 1
right_child_index = 2 * index + 2
return (helper(left_child_index, min_val, arr[index]) and
helper(right_child_index, arr[index], max_val))
else:
return False
return helper(0, float('-inf'), float('inf'))
# Ví dụ
arr1 = [5, 3, 6, None, 4, None, 10]
arr2 = [2, 1, 5, None, 3, 4, 10]
if is_binary_search_tree(arr1):
print("Dãy arr1 là biểu diễn của một cây tìm kiếm nhị phân.")
else:
print("Dãy arr1 không là biểu diễn của một cây tìm kiếm nhị phân.")
if is_binary_search_tree(arr2):
print("Dãy arr2 là biểu diễn của một cây tìm kiếm nhị phân.")
else:
print("Dãy arr2 không là biểu diễn của một cây tìm kiếm nhị phân.")
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 2:
Thay đổi thứ tự chèn các phần tử vào cây nhị phân có tạo ra các cây tìm kiếm nhị phân khác nhau hay không? Cho ví dụ minh họa.
Câu 3:
Khi nào việc tìm kiếm trên cây tìm kiếm nhị phân là:
a) nhanh nhất?
b) chậm nhất?
Câu 4:
Với cây nhị phân đã có ở Câu 1, em hãy vẽ sơ đồ cây sau khi chèn khoá 14 và cho biết vị trí của khoá này ở trong cây.
Câu 5:
Cây tìm kiếm nhị phân T được thiết lập bằng cách chèn lần lượt các phần tử 3, 1, 6, 5, 0, 2, 4. Dùng sơ đồ mô tả các bước tìm kiếm giá trị khóa là:
a) 4 b) 10 c) 0
Câu 6:
Quan sát các cây nhị phân sau, em có nhận xét gì về giá trị của các nút trên cây?
Câu 7:
Từ các khóa 1, 2, 3 có thể tạo ra được bao nhiêu cây tìm kiếm nhị phân? Hãy vẽ sơ đồ mô tả các cây này.
về câu hỏi!