Giả sử chúng ta muốn thiết kế một thuật toán để tuần tự hóa và giải mã hóa một cây tìm kiếm nhị phân. Serialization là quá trình chuyển đổi một thứ gì đó (cấu trúc dữ liệu hoặc đối tượng) thành một chuỗi các bit để nó có thể được lưu trữ trong tệp hoặc bộ đệm bộ nhớ, hoặc được truyền qua một liên kết kết nối mạng. Quá trình này có thể được tạo lại sau khi quá trình giải mã hóa.
Vì vậy, nếu đầu vào giống như [5,2,9,1,3,7], thì đầu ra sẽ là Đầu ra được tuần tự hóa 5.2.9.1.3.7.N.N.N.N.N.N.N Đầu ra được hủy số hóa:1, 2, 3, 5, 7, 9, (inorder traversal)
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Định nghĩa một hàm serialize (). Điều này sẽ bắt nguồn từ gốc
-
res:=một danh sách mới
-
xác định một hàng đợi và chèn thư mục gốc
-
trong khi hàng đợi không trống, thực hiện
-
trong khi hàng đợi không trống, thực hiện
-
hiện tại:=queue [0]
-
chèn dòng điện vào cuối res
-
xóa phần tử đầu tiên khỏi hàng đợi
-
nếu dòng điện khác 0 thì
-
đi ra từ vòng lặp
-
-
-
nếu hiện tại là null thì
-
đi ra từ vòng lặp
-
-
nếu current.left không phải là null thì
-
chèn current.left vào cuối hàng đợi
-
-
nếu không,
-
chèn Không vào cuối hàng đợi
-
-
nếu current.right không phải là null, thì
-
chèn current.right vào cuối hàng đợi
-
-
nếu không,
-
chèn Không vào cuối hàng đợi
-
-
-
s:=chuỗi trống
-
đối với tôi trong phạm vi 0 đến kích thước của res, hãy làm
-
nếu res [i] khác 0 thì
-
s:=s nối res [i] .data
-
-
nếu không,
-
s:=s nối "N"
-
-
nếu tôi giống với kích thước của res -1, thì
-
đi ra từ vòng lặp
-
-
s:=s nối "."
-
-
trả lại s
-
Định nghĩa một hàm deserialize (). Thao tác này sẽ lấy dữ liệu
-
data:=danh sách các phần sau khi phân chia dữ liệu bằng cách sử dụng dấu chấm
-
stack:=một danh sách mới
-
nếu dữ liệu [0] giống với 'N' thì
-
trả lại Không có
-
-
root:=tạo một nút mới với dữ liệu dữ liệu [0]
-
chèn root vào cuối ngăn xếp
-
i:=1
-
hiện tại:=0
-
while i
-
left:=Sai
-
nếu dữ liệu [i] không giống với 'N', thì
-
temp:=tạo một nút mới với dữ liệu dữ liệu [i]
-
ngăn xếp [hiện tại] .left:=temp
-
chèn nhiệt độ vào cuối ngăn xếp
-
-
nếu không,
-
stack [current] .left:=Không có
-
-
i:=i + 1
-
nếu dữ liệu [i] không giống với 'N', thì
-
temp:=tạo một nút mới với dữ liệu dữ liệu [i]
-
ngăn xếp [hiện tại] .right:=temp
-
chèn nhiệt độ vào cuối ngăn xếp
-
-
nếu không,
-
stack [current] .right:=Không có
-
-
hiện tại:=current + 1
-
i:=i + 1
-
-
trả về thư mục gốc
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def insert(temp,data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = 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):
#print using inorder traversal
if root is not None:
print_tree(root.left)
print(root.data, end = ', ')
print_tree(root.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):
left= False
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,