在 Python 中序列化和反序列化 BST
假设我们想设计一种算法来序列化和反序列化二叉搜索树。序列化是将某些东西(数据结构或对象)转换为位序列的过程，以便可以将其存储在文件或内存缓冲区中，或通过网络连接链路传输。稍后可以重建该过程，即反序列化。
因此，如果输入为 [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 := 队列[0]
在 res 末尾插入 current 节点
从队列中删除第一个元素
如果 current 节点非零，则
退出循环
如果 current 为 null，则
退出循环
如果 current.left 不为 null，则
在队列末尾插入 current.left
否则，
在队列末尾插入 None
如果 current.right 不为 null，则
在队列末尾插入 current.right
否则，
在队列末尾插入 None
s:= 空字符串
对于 i 在 0 到 res 大小范围内的情况，执行
如果 res[i] 非零，则
s := s 连接 res[i].data
否则，
s := s 连接 "N"
如果 i 与 res -1 的大小相同，则
退出循环
s := s 连接 "."
return s
定义一个函数 deserialize() 。这将获取数据
data := 使用点划分数据后的部分列表
stack := 一个新列表
如果 data[0] 与 'N' 相同，则
返回 None
root := 使用数据 data[0] 创建一个新节点
在 stack 末尾插入 root
i := 1
current := 0
while i <数据大小，执行
left:= False
如果 data[i] 与 'N' 不同，则
temp := 使用数据 data[i] 创建新节点
stack[current].left := temp
在堆栈末尾插入 temp
否则，
stack[current].left := None
i := i + 1
如果 data[i] 与 'N' 不同，则
temp := 使用数据 data[i] 创建一个新节点
stack[current].right := temp
在 stack 末尾插入 temp
否则，
stack[current].right := None
current := current + 1
i := i + 1
return 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,
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
