Chương trình Python chuyển cây nhị phân thành danh sách liên kết đôi

Khi cần chuyển cây nhị phân (binary tree) thành danh sách liên kết đôi, ta dùng duyệt in-order (left, root, right) để nối các nút theo thứ tự tăng dần (nếu cây BST).

Ví dụ

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

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

    def convert_tree_to_list(self, node_val):
        if node_val is None:
            return
        self.convert_tree_to_list(node_val.left)
        if self.head is None:
            self.head = self.tail = node_val
        else:
            self.tail.right = node_val
            node_val.left = self.tail
            self.tail = node_val
        self.convert_tree_to_list(node_val.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 = binary_tree_to_list()
print("Xây dựng cây nhị phân")
my_instance.root = Node(10)
my_instance.root.left = Node(14)
my_instance.root.right = Node(17)
my_instance.root.left.left = Node(22)
my_instance.root.left.right = Node(29)
my_instance.root.right.left = Node(45)
my_instance.root.right.right = Node(80)
my_instance.convert_tree_to_list(my_instance.root)
my_instance.print_it()

Kết quả

Xây dựng cây nhị phân
Các nút:
22
14
29
10
45
17
80

Giải thích

• Lớp Node cho cây nhị phân (left, right).
• Lớp binary_tree_to_list quản lý head, tail danh sách liên kết đôi.
• convert_tree_to_list duyệt in-order: đệ quy left, xử lý node hiện tại (nối vào tail), đệ quy right.
• Xử lý node: nếu head None -> head=tail=node; else tail.right=node, node.left=tail, tail=node.
• Kết quả là danh sách liên kết đôi theo thứ tự in-order của cây.