khoahoc.vietjack.com
Xin chào! Vào học

Câu hỏi:

13/07/2024 408 Lưu

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ụ sau:  (ảnh 1)

Quảng cáo

Trả lời:

verified Giải bởi Vietjack

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


 

Dành cho bạn Hot

Lớp 12 Vật lý
208 người thi tuần này

Trắc nghiệm Mô hình động học phân tử chất khí lớp 12 (có đáp án)

15 câu 1.9 K lượt thi Thi ngay →
Lớp 12 Tiếng Anh
133 người thi tuần này

Đề cương ôn tập giữa kì 1 Tiếng Anh 12 Global Success có đáp án

45 câu 1.3 K lượt thi Thi ngay →
Lớp 12 Sinh học
189 người thi tuần này

10 câu trắc nghiệm Sinh học 12 Kết nối tri thức Bài 8 có đáp án

10 câu 2 K lượt thi Thi ngay →
Lớp 12 Lịch sử
2,190 người thi tuần này

20 câu trắc nghiệm Lịch sử 12 Kết nối tri thức Bài 1 có đáp án

20 câu 22.4 K lượt thi Thi ngay →
Lớp 12 Địa lý
364 người thi tuần này

20 câu Trắc nghiệm Địa lý 12 Kết nối tri thức Bài 2 có đáp án

25 câu 6 K lượt thi Thi ngay →
Lớp 12 Tin học
556 người thi tuần này

15 câu Trắc nghiệm Tin học 12 Bài 1. Làm quen với Trí tuệ nhân tạo (có đáp án)

15 câu 13.2 K lượt thi Thi ngay →
Lớp 12 Giáo dục Kinh tế và Pháp luật
634 người thi tuần này

15 câu Trắc nghiệm KTPL 12 Bài 1 (có đáp án)

15 câu 8.9 K lượt thi Thi ngay →