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

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:

• Khởi động trang 37 Chuyên đề Tin học 12: Trong Bài 7, cây tìm tìm kiếm nhị phân được cài đặt bằng mảng một chiều và mỗi nút của cây ....

• Luyện tập 2 trang 40 Chuyên đề Tin học 12: Mô tả quá trình tra cứu giá tiền món Bún chả thực hiện trên cây tìm kiếm nhị phân ....

• Vận dụng 1 trang 40 Chuyên đề Tin học 12: Sử dụng cây tìm kiếm nhị phân để viết ứng dụng quản lí tài khoản ngân hàng ....

• Vận dụng 2 trang 40 Chuyên đề Tin học 12: Sử dụng cây tìm kiếm nhị phân để viết chương trình quản lí danh sách học sinh ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

• Chuyên đề Tin học 12 Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân

• Chuyên đề Tin học 12 Bài 10: Thực hành tổng hợp với cây tìm kiếm nhị phân

• Chuyên đề Tin học 12 Bài 11: Khái niệm đồ thị

• Chuyên đề Tin học 12 Bài 12: Biểu diễn đồ thị

• Chuyên đề Tin học 12 Bài 13: Thực hành thiết lập đồ thị

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều

---