Từ ví dụ cây nhị phân tổng quát trong Hình 10 dưới đây, em hãy lập trình thực hiện các nhiệm vụ

Giải Chuyên đề Tin 12 Bài 2: Thực hành duyệt cây nhị phân - Cánh diều

Vận dụng trang 41 Chuyên đề Tin học 12: Từ ví dụ cây nhị phân tổng quát trong Hình 10 dưới đây, em hãy lập trình thực hiện các nhiệm vụ sau:

a) Bổ sung các nút giá và xây dựng. cây nhị phân hoàn chỉnh bằng cách thêm từng nút giả vào cây. Khóa các nút nhập vào lần lượt từ bản phim, nút giả có giá trị là 0. 

b) Đưa ra danh sách các nút từ cây nhị phân vừa xây dựng theo các thủ tự trước, thứ tự sau và thứ tự giữa.

Lời giải:

Chương trình Python như sau:

class TreeNode:

   def __init__(self, value):

        self.value = value

        self.left = None

        self.right = None

def insert_node(root, value):

   if root is None:

        return TreeNode(value)

   else:

        if value < root.value:

            root.left = insert_node(root.left, value)

        else:

            root.right = insert_node(root.right, value)

   return root

def in_order_traversal(root):

   if root:

        in_order_traversal(root.left)

        print(root.value, end=" ")

        in_order_traversal(root.right)

def pre_order_traversal(root):

   if root:

        print(root.value, end=" ")

        pre_order_traversal(root.left)

        pre_order_traversal(root.right)

def post_order_traversal(root):

   if root:

        post_order_traversal(root.left)

        post_order_traversal(root.right)

        print(root.value, end=" ")

def build_perfect_binary_tree():

   root = None

   nodes = [24, 91, 17, 44, 62, 21, 67, 33, 49]

   for node in nodes:

        root = insert_node(root, node)  

   return root

def main():

   # a) Xây dựng cây nhị phân hoàn chỉnh và bổ sung các nút giả

   root = build_perfect_binary_tree()

   # b) In ra các nút theo các thứ tự trước, sau và giữa

   print("Thứ tự trước (Pre-order):")

   pre_order_traversal(root)

   print("\nThứ tự sau (Post-order):")

   post_order_traversal(root)

   print("\nThứ tự giữa (In-order):")

   in_order_traversal(root)

if __name__ == "__main__":

   main()

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Cánh diều hay, chi tiết khác:

• Chuyên đề Tin học 12 Bài 3: Cây tìm kiếm nhị phân

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

• Chuyên đề Tin học 12 Bài 1: Đồ thị, phân loại đồ thị

• Chuyên đề Tin học 12 Bài 2: Biểu diễn đồ thị trên máy tính

• Chuyên đề Tin học 12 Bài 3: Thực hành các thao tác cơ bản với đồ thị trên máy tính

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

---