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