Câu hỏi:
10/10/2026 3
Cho 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 nhị phân hoàn chỉnh đã biến đổi hay không?
Ví dụ:
Dãy [10, 7, 0, 5, None, 3] là biểu diễn của cây nhị phân hoàn chỉnh đã biến đổi. Dãy [1, 6, None, 2, 3, None, 4] không là biểu diễn của cây nhị phân tổng quát nào.
Cho 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 nhị phân hoàn chỉnh đã biến đổi hay không?
Ví dụ:
Dãy [10, 7, 0, 5, None, 3] là biểu diễn của cây nhị phân hoàn chỉnh đã biến đổi. Dãy [1, 6, None, 2, 3, None, 4] không là biểu diễn của cây nhị phân tổng quát nào.
Trả lời:
Giải bởi Vietjack
Để kiểm tra xem một dãy đã cho có phải là biểu diễn của một cây nhị phân hoàn chỉnh đã biến đổi hay không, chúng ta có thể sử dụng một số quy tắc sau:\
- Dãy đó phải là biểu diễn của một cây nhị phân, tức là mỗi phần tử của dãy đều có thể là một nút hoặc None.
- Đối với mỗi nút trong dãy, nút trái của nó (nếu có) phải nằm ở vị trí 2*i + 1 trong dãy, và nút phải của nó (nếu có) phải nằm ở vị trí 2*i + 2 trong dãy, với i là vị trí của nút trong dãy (bắt đầu từ 0).
Dựa trên các quy tắc trên có thể viết chương trình như sau:
def is_complete_binary_tree(arr):
# Kiểm tra dãy có phải là biểu diễn của một cây nhị phân không
for i in range(len(arr)):
if arr[i] is not None:
# Kiểm tra nếu nút trái không vượt quá độ dài của dãy
left_child_index = 2 * i + 1
if left_child_index < len(arr) and arr[left_child_index] is None:
return False
# Kiểm tra nếu nút phải không vượt quá độ dài của dãy
right_child_index = 2 * i + 2
if right_child_index < len(arr) and arr[right_child_index] is None:
return False
return True
# Ví dụ
arr1 = [10, 7, 0, 5, None, 3]
arr2 = [1, 6, None, 2, 3, None, 4]
if is_complete_binary_tree(arr1):
print("Dãy arr1 là biểu diễn của một cây nhị phân hoàn chỉnh đã biến đổi.")
else:
print("Dãy arr1 không là biểu diễn của một cây nhị phân hoàn chỉnh đã biến đổi.")
if is_complete_binary_tree(arr2):
print("Dãy arr2 là biểu diễn của một cây nhị phân hoàn chỉnh đã biến đổi.")
else:
print("Dãy arr2 không là biểu diễn của một cây nhị phân hoàn chỉnh đã biến đổi.")
Để kiểm tra xem một dãy đã cho có phải là biểu diễn của một cây nhị phân hoàn chỉnh đã biến đổi hay không, chúng ta có thể sử dụng một số quy tắc sau:\
- Dãy đó phải là biểu diễn của một cây nhị phân, tức là mỗi phần tử của dãy đều có thể là một nút hoặc None.
- Đối với mỗi nút trong dãy, nút trái của nó (nếu có) phải nằm ở vị trí 2*i + 1 trong dãy, và nút phải của nó (nếu có) phải nằm ở vị trí 2*i + 2 trong dãy, với i là vị trí của nút trong dãy (bắt đầu từ 0).
Dựa trên các quy tắc trên có thể viết chương trình như sau:
def is_complete_binary_tree(arr):
# Kiểm tra dãy có phải là biểu diễn của một cây nhị phân không
for i in range(len(arr)):
if arr[i] is not None:
# Kiểm tra nếu nút trái không vượt quá độ dài của dãy
left_child_index = 2 * i + 1
if left_child_index < len(arr) and arr[left_child_index] is None:
return False
# Kiểm tra nếu nút phải không vượt quá độ dài của dãy
right_child_index = 2 * i + 2
if right_child_index < len(arr) and arr[right_child_index] is None:
return False
return True
# Ví dụ
arr1 = [10, 7, 0, 5, None, 3]
arr2 = [1, 6, None, 2, 3, None, 4]
if is_complete_binary_tree(arr1):
print("Dãy arr1 là biểu diễn của một cây nhị phân hoàn chỉnh đã biến đổi.")
else:
print("Dãy arr1 không là biểu diễn của một cây nhị phân hoàn chỉnh đã biến đổi.")
if is_complete_binary_tree(arr2):
print("Dãy arr2 là biểu diễn của một cây nhị phân hoàn chỉnh đã biến đổi.")
else:
print("Dãy arr2 không là biểu diễn của một cây nhị phân hoàn chỉnh đã biến đổi.")
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
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?
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 2:
Tìm hiểu và thảo luận về tổ chức dữ liệu của cây nhị phân và tìm kiếm cây nhị phân.
Tìm hiểu và thảo luận về tổ chức dữ liệu của cây nhị phân và tìm kiếm cây nhị phân.
Câu 4:
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.
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.
Câu 5:
Bài toán: cho cây tìm kiếm nhị phân T. Yêu cầu chèn khoá v vào cây T sao cho sau khi cho sau khi chèn khoá v thì cây T vẫn là cây tìm kiếm nhị phân.
Quan sát, thảo luận, tìm hiểu thuật toán tìm kiếm khoá 7 trên cây tìm kiếm nhị phân và cách chèn khoá 7 vào cây này.
Bài toán: cho cây tìm kiếm nhị phân T. Yêu cầu chèn khoá v vào cây T sao cho sau khi cho sau khi chèn khoá v thì cây T vẫn là cây tìm kiếm nhị phân.
Quan sát, thảo luận, tìm hiểu thuật toán tìm kiếm khoá 7 trên cây tìm kiếm nhị phân và cách chèn khoá 7 vào cây này.
Câu 6:
Cho trước dãy các số A = [10, 1, 2, 11, 8, 15, 20, 9, 0].
Hãy mô tả và vẽ sơ đồ cây nhị phân biểu diễn dãy số trên sau khi thực hiện thao tác chèn như đã mô tả trong hoạt động.
Cho trước dãy các số A = [10, 1, 2, 11, 8, 15, 20, 9, 0].
Hãy mô tả và vẽ sơ đồ cây nhị phân biểu diễn dãy số trên sau khi thực hiện thao tác chèn như đã mô tả trong hoạt động.
Câu 7:
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?
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 8:
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â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 9:
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.
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 10:
Nếu dãy số được đưa vào cây tìm kiếm nhị phân là tăng dần (hoặc giảm dần) thì cây tìm kiếm nhị phân tương ứng có dạng như thế nào?
Nếu dãy số được đưa vào cây tìm kiếm nhị phân là tăng dần (hoặc giảm dần) thì cây tìm kiếm nhị phân tương ứng có dạng như thế nào?
Câu 11:
Dữ liệu đầu vào là danh sách học sinh trong lớp và điểm trung bình các môn. Danh sách được cho trong tệp văn bản có dạng như bảng bên.
Viết chương trình đọc tập dữ liệu đầu vào trên và liên tục thực hiện các thao tác sau:
a) Nhập thêm vào danh sách học sinh và điểm trung bình.
b) Tìm kiếm với yêu cầu nhập họ tên học sinh và đưa ra kết quả họ tên học sinh, điểm trung bình hoặc thông báo "không tìm thấy".
Chương trình kết thúc khi nhập vào một xâu rỗng. Yêu cầu giải bài này bằng cây tìm kiếm nhị phân.
Dữ liệu đầu vào là danh sách học sinh trong lớp và điểm trung bình các môn. Danh sách được cho trong tệp văn bản có dạng như bảng bên.
Viết chương trình đọc tập dữ liệu đầu vào trên và liên tục thực hiện các thao tác sau:
a) Nhập thêm vào danh sách học sinh và điểm trung bình.
b) Tìm kiếm với yêu cầu nhập họ tên học sinh và đưa ra kết quả họ tên học sinh, điểm trung bình hoặc thông báo "không tìm thấy".
Chương trình kết thúc khi nhập vào một xâu rỗng. Yêu cầu giải bài này bằng cây tìm kiếm nhị phân.
Câu 12:
Viết hàm chèn khoá v vào cây tìm kiếm nhị phân T sử dụng kĩ thuật đệ quy.
Viết hàm chèn khoá v vào cây tìm kiếm nhị phân T sử dụng kĩ thuật đệ quy.
Câu 13:
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.
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 hỏi mới nhất
Xem thêm »-
-
-
-
Trong CSDL QL_ThuVien, hãy xác định khóa chính của bảng MƯỢN SÁCH sau. Biết rằng trong một ngày quy định không được mượn một cuốn sách nhiều lần.
Số thẻ Mã số sách Ngày mượn Ngày trả TV-02
TO-012
5/9/2015
30/9/2015
TV-04
TN-103
12/9/2015
15/9/2015
TV-02
TN-102
24/9/2015
5/10/2015
TV-02
TO-012
5/10/2015
...
...
...
...
-
-
-
-
-
-