資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python 中二叉搜尋樹的序列化和反序列化
假設我們想要設計一個演算法來序列化和反序列化二叉搜尋樹。序列化是將某些東西（資料結構或物件）轉換為一系列位元的過程，以便將其儲存在檔案或記憶體緩衝區中，或透過網路連線鏈路傳輸。稍後可以重建此過程，該過程稱為反序列化。
因此，如果輸入類似於 [5,2,9,1,3,7]，則輸出將是 序列化輸出 5.2.9.1.3.7.N.N.N.N.N.N.N 反序列化輸出：1, 2, 3, 5, 7, 9, (中序遍歷)
為了解決這個問題，我們將遵循以下步驟 -
定義一個函式 serialize()。這將接收根節點
res := 一個新的列表
定義一個佇列並將根節點插入佇列
當佇列非空時，執行以下操作
當佇列非空時，執行以下操作
current := 佇列的第一個元素
將 current 附加到 res 的末尾
從佇列中刪除第一個元素
如果 current 非零，則
退出迴圈
如果 current 為空，則
退出迴圈
如果 current.left 非空，則
將 current.left 附加到佇列的末尾
否則，
將 None 附加到佇列的末尾
如果 current.right 非空，則
將 current.right 附加到佇列的末尾
否則，
將 None 附加到佇列的末尾
s:= 空字串
對於 i 從 0 到 res 的大小，執行以下操作
如果 res[i] 非零，則
s := s 連線 res[i].data
否則，
s := s 連線 "N"
如果 i 等於 res 的大小 -1，則
退出迴圈
s := s 連線 "."
返回 s
定義一個函式 deserialize()。這將接收資料
data := 使用點分隔資料後得到的部分組成的列表
stack := 一個新的列表
如果 data[0] 等於 'N'，則
返回 None
root := 建立一個值為 data[0] 的新節點
將 root 附加到 stack 的末尾
i := 1
current := 0
當 i < data 的大小，執行以下操作
left:= False
如果 data[i] 不等於 'N'，則
temp := 建立一個值為 data[i] 的新節點
stack[current].left := temp
將 temp 附加到 stack 的末尾
否則，
stack[current].left := None
i := i + 1
如果 data[i] 不等於 'N'，則
temp := 建立一個值為 data[i] 的新節點
stack[current].right := temp
將 temp 附加到 stack 的末尾
否則，
stack[current].right := None
current := current + 1
i := i + 1
返回 root
示例
讓我們看看以下實現以更好地理解 -
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))輸入
[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,
472 次瀏覽
