Vẽ cây tìm kiếm nhị phân ứng với tệp menu.inp trong nhiệm vụ thực hành
Vẽ cây tìm kiếm nhị phân ứng với tệp menu.inp trong nhiệm vụ thực hành, lưu ý mỗi nút gồm hai thuộc tính name và price.
Giải Chuyên đề Tin 12 Bài 8: Thực hành cây tim kiếm nhị phân - Kết nối tri thức
Luyện tập 1 trang 40 Chuyên đề Tin học 12: Vẽ cây tìm kiếm nhị phân ứng với tệp menu.inp trong nhiệm vụ thực hành, lưu ý mỗi nút gồm hai thuộc tính name và price.
Lời giải:
Để vẽ cây tìm kiếm nhị phân ứng với dữ liệu từ tệp menu.inp, trước tiên chúng ta cần đọc dữ liệu từ tệp và chèn mỗi mục vào cây. Sau đó, chúng ta có thể sử dụng các công cụ vẽ đồ thị để hiển thị cây.
Dưới đây là mã Python mẫu để thực hiện điều này:
import matplotlib.pyplot as plt
from queue import Queue
class MenuItem:
def __init__(self, name, price):
self.name = name
self.price = price
self.left = None
self.right = None
def insert(root, name, price):
if root is None:
return MenuItem(name, price)
if name < root.name:
root.left = insert(root.left, name, price)
elif name > root.name:
root.right = insert(root.right, name, price)
return root
def build_binary_search_tree(filename):
root = None
with open(filename, 'r') as file:
for line in file:
name, price = line.strip().split(', ')
price = int(price)
root = insert(root, name, price)
return root
def plot_binary_search_tree(root):
if root is None:
return
node_queue = Queue()
node_queue.put(root)
while not node_queue.empty():
current_level_size = node_queue.qsize()
for _ in range(current_level_size):
node = node_queue.get()
if node.left:
node_queue.put(node.left)
plt.plot([node.val, node.left.val], [node.price, node.left.price], color='black')
if node.right:
node_queue.put(node.right)
plt.plot([node.val, node.right.val], [node.price, node.right.price], color='black')
plt.scatter(node.val, node.price, color='red')
plt.text(node.val, node.price, node.name, fontsize=9, ha='center')
plt.xlabel('Name')
plt.ylabel('Price')
plt.title('Binary Search Tree Representation of Menu')
plt.grid()
plt.show()
# Tạo cây tìm kiếm nhị phân từ tệp menu.inp
root = build_binary_search_tree('menu.inp')
# Vẽ cây tìm kiếm nhị phân
plot_binary_search_tree(root)
Chú thích trong chương trình này:
- Chúng ta định nghĩa lớp MenuItem để đại diện cho các nút trong cây. Mỗi nút có hai thuộc tính là name và price.
- Hàm insert được sử dụng để chèn một mục vào cây tìm kiếm nhị phân.
- Hàm build_binary_search_tree đọc dữ liệu từ tệp menu.inp và xây dựng cây tìm kiếm nhị phân từ các mục đó.
- Hàm plot_binary_search_tree được sử dụng để vẽ cây tìm kiếm nhị phân bằng cách sử dụng thư viện matplotlib.
Lời giải bài tập Chuyên đề Tin 12 Bài 8: Thực hành cây tim kiếm nhị phân hay, ngắn gọn khác: