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ụ

Trang trước Trang sau

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.

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ụ

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:

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

Trang trước Trang sau
Giải bài tập lớp 12 sách mới các môn học