Câu hỏi:
13/07/2024 461
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.
Quảng cáo
Trả lời:
Giải bởi Vietjack
Sơ đồ có dạng như sau:
![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. (ảnh 1)](https://video.vietjack.com/upload2/quiz_source1/2024/06/17-1719395681.jpg)
Số 10 là gốc.
1 < 10. Chèn sang nút con bên trái số 10.
2 < 10 & 2 > 1. Chèn sang nút con bên phải số 1.
11 > 10. Chèn sang nút con bên phải số 10.
8 < 10 & 8 > 1 & 8 > 2. Chèn sang nút con bên phải số 2.
15 > 10 & 15 > 11. Chèn sang nút con bên phải số 11.
20 > 10 & 20 > 11 & 20 > 15. Chèn sang nút con bên phải số 15.
9 < 10 & 9 > 1 & 9 > 2 & 9 > 8. Chèn sang nút con bên phải số 8.
0 < 10 & 0 < 1 & 0 < 2. Chèn sang nút con bên trái số 2 (Cũng có thể là số 1, 8, 9).
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:
- Sổ tay Ngữ Văn 12 (chương trình mới) ( 18.000₫ )
- Sổ tay dẫn chứng nghị luận xã hội năm 2025 (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₫ )
- Bộ đề thi tốt nghiệp 2025 các môn Toán, Lí, Hóa, Văn, Anh, Sinh, Sử, Địa, KTPL (có đáp án chi tiết) ( 36.000₫ )
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
Nếu dãy số được chèn 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 sẽ có dạng như một cây cân bằng.
Lời giải
Sử dụng một cây tìm kiếm nhị phân (Binary Search Tree - BST) để lưu trữ và thao tác với danh sách học sinh và điểm trung bình của họ. Chương trình sẽ bao gồm các chức năng sau:
1. Đọc dữ liệu đầu vào từ tệp Data.inp.
2. Thêm học sinh mới vào cây tìm kiếm nhị phân.
3. Tìm kiếm học sinh theo tên và đưa ra điểm trung bình của họ.
4. Chương trình kết thúc khi nhập vào một chuỗi rỗng.
Dưới đây là hướng dẫn các bước triển khai chi tiết:
* Bước 1: Định nghĩa cấu trúc của cây tìm kiếm nhị phân
Chúng ta sẽ tạo một lớp Node để biểu diễn mỗi nút trong cây và một lớp BinarySearchTree để thực hiện các thao tác trên cây.
class Node:
def __init__(self, name, score):
self.name = name
self.score = score
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, name, score):
new_node = Node(name, score)
if self.root is None:
self.root = new_node
else:
self._insert(self.root, new_node)
def _insert(self, current, new_node):
if new_node.name < current.name:
if current.left is None:
current.left = new_node
else:
self._insert(current.left, new_node)
elif new_node.name > current.name:
if current.right is None:
current.right = new_node
else:
self._insert(current.right, new_node)
def search(self, name):
return self._search(self.root, name)
def _search(self, current, name):
if current is None:
return None
if name == current.name:
return current
elif name < current.name:
return self._search(current.left, name)
else:
return self._search(current.right, name)
* Bước 2: Đọc dữ liệu từ tệp Data.inp và khởi tạo cây tìm kiếm nhị phân
def load_data(filename):
bst = BinarySearchTree()
with open(filename, 'r', encoding='utf8') as file:
for line in file:
parts = line.strip().split(maxsplit=1)
name = parts[0] + " " + parts[1]
score = float(parts[2])
bst.insert(name, score)
return bst
bst = load_data("Data.inp")
* Bước 3: Thực hiện các thao tác thêm học sinh và tìm kiếm
def main():
bst = load_data("Data.inp")
while True:
print("Chọn thao tác:")
print("1. Thêm học sinh")
print("2. Tìm kiếm học sinh")
print("Nhập chuỗi rỗng để kết thúc chương trình.")
choice = input("Nhập lựa chọn: ").strip()
if choice == "":
break
elif choice == "1":
name = input("Nhập họ tên học sinh: ").strip()
if name == "":
break
try:
score = float(input("Nhập điểm trung bình: ").strip())
bst.insert(name, score)
print(f"Đã thêm học sinh {name} với điểm trung bình {score}")
except ValueError:
print("Điểm trung bình phải là một số.")
elif choice == "2":
name = input("Nhập họ tên học sinh cần tìm: ").strip()
if name == "":
break
result = bst.search(name)
if result:
print(f"Học sinh: {result.name}, Điểm trung bình: {result.score}")
else:
print("Không tìm thấy học sinh này.")
else:
print("Lựa chọn không hợp lệ. Vui lòng chọn lại.")
if __name__ == "__main__":
main()
*Giải thích:
1. Cấu trúc cây tìm kiếm nhị phân:
- Node: Lớp biểu diễn một nút trong cây, bao gồm tên học sinh, điểm trung bình, và các nút con trái/phải.
- BinarySearchTree: Lớp chứa các phương thức để chèn (insert) và tìm kiếm (search) các nút trong cây.
2. Đọc dữ liệu:
- load_data(filename): Hàm này đọc dữ liệu từ tệp Data.inp và chèn từng học sinh vào cây tìm kiếm nhị phân.
3. Thao tác thêm và tìm kiếm:
- main(): Hàm chính thực hiện vòng lặp để cho phép người dùng thêm học sinh và tìm kiếm học sinh theo tên. Khi nhập vào chuỗi rỗng, chương trình sẽ kết thúc.
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:
-
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 Cánh diều Giới thiệu trí tuệ nhân tạo có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 23 có đáp án
-
Bộ 3 đề thi cuối kì 2 Tin 12 Kết nối tri thức có đáp án - Đề 2
-
Bộ 3 đề thi cuối kì 2 Tin 12 Chân trời sáng tạo có đáp án - Đề 3
-
Bộ 3 đề thi cuối kì 2 Tin 12 Kết nối tri thức có đáp án - Đề 1
-
Bộ 3 đề thi cuối kì 2 Tin 12 Cánh diều có đáp án - Đề 2
-
Bộ 3 đề thi cuối kì 2 Tin 12 Chân trời sáng tạo có đáp án - Đề 2