Câu hỏi:
01/10/2024 130
Cho 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?
Cho 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?Quảng cáo
Trả lời:
Giải bởi Vietjack
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)
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:
- 250+ Công thức giải nhanh môn Toán 12 (chương trình mới) ( 18.000₫ )
- Sổ tay Địa Lí 12 (chương trình mới) ( 18.000₫ )
- Sổ tay lớp 12 các môn Toán, Lí, Hóa, Văn, Sử, Địa, KTPL (chương trình mới) ( 36.000₫ )
- Tuyển tập 30 đề thi đánh giá năng lực Đại học Quốc gia Hà Nội, TP Hồ Chí Minh (2 cuốn) ( 150.000₫ )
Bình luận
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
Mảng một chiều để biểu diễn các giá trị trong cây nhị phân như sau:
[2, 24, 11, None, 3, 8, 9]
Lời giải
Cách biểu diễn các giá trị của cây bằng mảng một chiều theo ba phép duyệt:
a) Duyệt trước (Pre-order): Thăm nút gốc trước, sau đó là cây con bên trái và cuối cùng là cây con bên phải. [20,24,14,None,None,None,None,None,None,None,None]
b) Duyệt giữa (In-order): Thăm cây con bên trái trước, sau đó là nút gốc và cuối cùng là cây con bên phải. None,None,None,None]
c) Duyệt sau (Post-order): Thăm cây con bên trái trước, sau đó là cây con bên phải và kết thúc ở nút gốc. [None]
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
🔥 Đề thi HOT:
-
Bộ 3 đề thi cuối kì 2 Tin 12 Cánh diều có đáp án - Đề 1
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 23 có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 19 có đáp án
-
Bộ 3 đề thi cuối kì 2 Tin 12 Kết nối tri thức có đáp án - Đề 1
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Mô hình và các giao thức mạng có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 24 có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 25 có đáp án
-
Trắc nghiệm tổng hợp Tin học năm 2023 có đáp án (Phần 1)
Hãy Đăng nhập hoặc Tạo tài khoản để gửi bình luận
-
-
Bình luận