数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
