Câu hỏi:
01/10/2024 55Cho mảng các số nguyên dương A = [9, 6, 5, 17, 10, 3, 8, 12].
a) Xây dựng cây nhị phân với mảng số nguyên dương trên.
b) Viết chương trình có sử dụng phép toán duyệt trước, duyệt giữa, duyệt sau để:
- Kiểm tra giá trị 10 có trong cây hay không?
- Kiểm tra giá trị 7 có trong cây hay không?Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
a) Xây dựng cây nhị phân với mảng số nguyên dương A = [9, 6, 5, 17, 10, 3, 8, 12]
Chúng ta sẽ xây dựng cây nhị phân tìm kiếm (BST) từ mảng A:
Phần tử đầu tiên 9 là gốc.
6 nhỏ hơn 9, đặt vào cây con trái của 9.
5 nhỏ hơn 6, đặt vào cây con trái của 6.
17 lớn hơn 9, đặt vào cây con phải của 9.
10 nhỏ hơn 17, đặt vào cây con trái của 17.
3 nhỏ hơn 5, đặt vào cây con trái của 5.
8 lớn hơn 6, đặt vào cây con phải của 6.
12 lớn hơn 10, đặt vào cây con phải của 10.
b) Viết chương trình kiểm tra giá trị trong cây và thực hiện duyệt cây:
Code:
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def insert(root, key):
if root is None:
return Node(key)
else:
if root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root
def search(root, key):
if root is None or root.val == key:
return root
if root.val < key:
return search(root.right, key)
return search(root.left, key)
def preOrder(root):
if root:
print(root.val, end=" ")
preOrder(root.left)
preOrder(root.right)
def inOrder(root):
if root:
inOrder(root.left)
print(root.val, end=" ")
inOrder(root.right)
def postOrder(root):
if root:
postOrder(root.left)
postOrder(root.right)
print(root.val, end=" ")
# Mảng số nguyên dương
A = [9, 6, 5, 17, 10, 3, 8, 12]
# Xây dựng cây nhị phân
root = None
for key in A:
root = insert(root, key
# Duyệt cây
print("Duyệt trước:")
preOrder(root)
print("\nDuyệt giữa:")
inOrder(root)
print("\nDuyệt sau:")
postOrder(root)
print()
# Kiểm tra giá trị
def check_value(root, value):
if search(root, value):
print(f"Giá trị {value} có trong cây.")
else:
print(f"Giá trị {value} không có trong cây.")
# Kiểm tra giá trị 10 và 7
check_value(root, 10)
check_value(root, 7)
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Cho cây nhị phân như Hình 1. Hãy dùng mảng một chiều để biểu diễn các giá trị trong cây nhị phân.
Câu 2:
Cho các thao tác: (1) Duyệt nút gốc; (2) Duyệt cây con trái; (3) Duyệt cây con phải. Sắp xếp thứ tự các thao tác tương ứng với các phép toán duyệt cây nhị phân:
a) Duyệt trước;
b) Duyệt giữa;
c) Duyệt sau.
Câu 3:
Cho cây nhị phân như Hình 8. Biểu diễn các giá trị trong cây nhị phân bằng mảng một chiều theo:
a) Duyệt trước;
b) Duyệt giữa;
c) Duyệt sau.
Câu 4:
Cho cây nhị phân như Hình 4.
Kết quả thực hiện phép toán duyệt cây nhị phân như sau:
3 |
4 |
1 |
2 |
8 |
Phép toán duyệt cây nhị phân cho kết quả như bảng ở trên là phép toán nào?
Câu 5:
Cho mảng số nguyên dương A = [5, 8, 7, 4, 9, 2).
a) Xây dựng cây nhị phân với mảng số nguyên dương trên.
b) Sử dụng phép toán duyệt trước, duyệt giữa, duyệt sau để xuất thứ tự các giá trị trên
cây nhị phân được xây dựng ở câu a).
Câu 6:
Cho cây nhị phân như Hình 8. Biểu diễn các giá trị trong cây nhị phân bằng mảng một chiều theo:
a) Duyệt trước;
b) Duyệt giữa;
c) Duyệt sau.
263 câu Trắc nghiệm tổng hợp ôn thi tốt nghiệp THPT môn Tin học Chủ đề F. Giải quyết vấn đề với sự trợ giúp của máy tính có đáp án
15 câu Trắc nghiệm Tin học 12 KNTT Bài 7: HTML và cấu trúc trang web
15 câu Trắc nghiệm Tin học 12 KNTT Bài 10: Tạo liên kết
15 câu Trắc nghiệm Tin học 12 KNTT Bài 8: Định dạng văn bản
15 câu Trắc nghiệm Tin học 12 KNTT Bài 11: Chèn tệp tin đa phương tiện và khung nội tuyến vào trang web
15 câu Trắc nghiệm Tin học 12 KNTT Bài 9: Tạo danh sách, bảng
15 câu Trắc nghiệm Tin học 12 Cánh diều Bài 1: Làm quen với ngôn ngữ đánh dấu siêu văn bản
Đề thi Học kì 1 Tin học 12 có đáp án (Đề 1)
về câu hỏi!