Chương trình Python tạo danh sách liên kết đôi từ cây ternary

Khi cần chuyển đổi cây ternary (mỗi nút có 3 con: left, mid, right) thành danh sách liên kết đôi, ta dùng duyệt đệ quy (pre-order: root, left, mid, right) và nối các nút thành danh sách.

Ví dụ

class Node:
    def __init__(self, my_data):
        self.right = None
        self.data = my_data
        self.left = None
        self.mid = None

class ternary_tree_to_list:
    def __init__(self):
        self.root = None
        self.head = None
        self.tail = None

    def convert_ternary_tree_to_list(self, node_val):
        if node_val is None:
            return
        left = node_val.left
        mid = node_val.mid
        right = node_val.right
        if self.head is None:
            self.head = self.tail = node_val
            node_val.mid = None
            self.head.left = None
            self.head.right = None
        else:
            self.tail.right = node_val
            node_val.left = self.tail
            node_val.mid = None
            self.tail = node_val
            self.tail.right = None
        self.convert_ternary_tree_to_list(left)
        self.convert_ternary_tree_to_list(mid)
        self.convert_ternary_tree_to_list(right)

    def print_it(self):
        curr = self.head
        if self.head is None:
            print("Danh sách rỗng")
            return
        print("Các nút:")
        while curr is not None:
            print(curr.data)
            curr = curr.right

my_instance = ternary_tree_to_list()
print("Xây dựng cây ternary")
my_instance.root = Node(10)
my_instance.root.left = Node(14)
my_instance.root.mid = Node(24)
my_instance.root.right = Node(17)
my_instance.root.left.left = Node(22)
my_instance.root.left.mid = Node(23)
my_instance.root.mid.left = Node(24)
my_instance.root.mid.mid = Node(28)
my_instance.root.mid.right = Node(30)
my_instance.root.right.left = Node(45)
my_instance.root.right.mid = Node(50)
my_instance.root.right.right = Node(80)
my_instance.convert_ternary_tree_to_list(my_instance.root)
my_instance.print_it()

Kết quả

Xây dựng cây ternary
Các nút:
10
14
22
23
24
24
28
30
17
45
50
80

Giải thích

• Lớp Node cho cây ternary (left, mid, right).
• Lớp ternary_tree_to_list có head, tail cho danh sách liên kết đôi.
• convert_ternary_tree_to_list duyệt pre-order: xử lý nút hiện tại (nối vào tail), sau đó đệ quy left, mid, right.
• Khi thêm nút đầu tiên, head=tail=node, left=right=mid=None.
• Các nút sau: tail.right = node, node.left = tail, node.mid=None, tail=node.
• In danh sách sau chuyển đổi.