Serialize và Deserialize BST trong Python

Thiết kế thuật toán để serialize (chuỗi hóa) và deserialize (khôi phục) một cây tìm kiếm nhị phân (BST). Serialization chuyển cấu trúc dữ liệu thành chuỗi bit để lưu trữ hoặc truyền tải, deserialization là quá trình ngược lại.

Ví dụ, với đầu vào [5,2,9,1,3,7], đầu ra serialize là 5.2.9.1.3.7.N.N.N.N.N.N.N, deserialize cho duyệt inorder: 1, 2, 3, 5, 7, 9.

Giải pháp:

• Serialize: Duyệt BFS (level-order), dùng queue. Ghi giá trị nút hoặc N cho null, ngăn cách bằng dấu chấm.
• Deserialize: Tách chuỗi bằng dấu chấm. Dùng stack để xây dựng cây: lần lượt gán left, right cho từng nút cha.

Ví dụ triển khai

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

def insert(temp, data):
    que = [temp]
    while que:
        temp = que.pop(0)
        if not temp.left:
            temp.left = TreeNode(data) if data is not None else TreeNode(0)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            temp.right = TreeNode(data) if data is not None else TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

def print_tree(root):
    if root:
        print_tree(root.left)
        print(root.data, end=', ')
        print_tree(root.right)

class Codec:
    def serialize(self, root):
        res = []
        queue = [root]
        while queue:
            while queue:
                current = queue.pop(0)
                res.append(current)
                if current:
                    break
            if not current:
                break
            if current.left:
                queue.append(current.left)
            else:
                queue.append(None)
            if current.right:
                queue.append(current.right)
            else:
                queue.append(None)
        s = ""
        for i in range(len(res)):
            if res[i]:
                s += str(res[i].data)
            else:
                s += "N"
            if i == len(res) - 1:
                break
            s += "."
        return s
    
    def deserialize(self, data):
        data = data.split(".")
        stack = []
        if data[0] == 'N':
            return None
        root = TreeNode(int(data[0]))
        stack.append(root)
        i = 1
        current = 0
        while i < len(data):
            if data[i] != 'N':
                temp = TreeNode(int(data[i]))
                stack[current].left = temp
                stack.append(temp)
            else:
                stack[current].left = None
            i += 1
            if data[i] != 'N':
                temp = TreeNode(int(data[i]))
                stack[current].right = temp
                stack.append(temp)
            else:
                stack[current].right = None
            current += 1
            i += 1
        return root

ob = Codec()
root = make_tree([5,2,9,1,3,7])
ser = ob.serialize(root)
print('Serialization:', ser)
print_tree(ob.deserialize(ser))

Đầu vào

[5,2,9,1,3,7]

Đầu ra

Serialization: 5.2.9.1.3.7.N.N.N.N.N.N.N
1, 2, 3, 5, 7, 9,