Serialize และ Deserialize BST ใน Python

การ Serialize คือการแปลงโครงสร้างข้อมูล (เช่น Binary Search Tree) ให้เป็นสตริงบิตเพื่อเก็บไฟล์หรือส่งผ่านเครือข่าย การ Deserialize คือกระบวนการย้อนกลับสร้างต้นไม้กลับมา

ตัวอย่าง: อินพุต [5,2,9,1,3,7] ให้ผลลัพธ์ Serialize: 5.2.9.1.3.7.N.N.N.N.N.N.N และ Deserialize (inorder): 1, 2, 3, 5, 7, 9

แนวทางการทำงาน

Serialize (BFS Level Order)

1. ใช้คิวเริ่มจาก root
2. วนลูปดึงโหนดจากคิว เก็บค่า (หรือ 'N' ถ้าเป็น None)
3. เพิ่มลูกซ้ายและขวาเข้าไปในคิว (None ก็ใส่เข้าไปด้วย)
4. เชื่อมค่าด้วยจุด (.)

Deserialize

1. แยกสตริงด้วย '.' ได้รายการค่า
2. สร้าง root จากค่าแรก
3. ใช้สแต็กเก็บโหนดแม่ วนลูปอ่านค่าคู่ๆ (left, right) สร้างโหนดลูกต่อไป

ตัวอย่างโค้ด

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

class Codec:
    def serialize(self, root):
        res = []
        queue = [root]
        while queue:
            while True and queue:
                current = queue[0]
                res.append(current)
                queue.pop(0)
                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

# ทดสอบ
def insert(temp, data):
    que = [temp]
    while que:
        temp = que[0]
        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 is not None:
        print_tree(root.left)
        print(root.data, end=', ')
        print_tree(root.right)

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

อินพุต

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

เอาต์พุต

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