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

Vận dụng

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 chi tiết:

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()