0%

二叉树的序列化和反序列化

读前福利:几百本互联网技术书籍送给大家https://mp.weixin.qq.com/s/dFqVQ2qJxvQ0YrIlPISJuw


【0】

前言

偶然看到的一个题目!!~

通常我们面对关于二叉树的题目会是对树的各种操作,而该题目是对整棵树进行序列化存储,然后再反序列化出来,返回二叉树原本的样子。当然最后要返回树的头结点 head ~~~

【1】

题目

二叉树的序列化和反序列化

序列化:即在生成一棵二叉树以后,按照文本的格式存储到文件中,即为二叉树的序列化

反序列化:将序列化后的二叉树,按照序列化的规则,对其进行解析出原来二叉树的格式,并且返回头结点

下图对应前序遍历的序列化结果 6!88!10!#!#!#!92!11!22!#!#!9!#!#!12!#!#! :

【2】

解决方案

1. 构造树结点类

这块就用 Python 来举例

1
2
3
4
5
class TreeNode:
def __init__(self, value):
self.val = value # 存储结点值
self.left = None # 指向左子树
self.right = None # 指向右子树

然后手动构造二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if __name__ == "__main__":
# 新建节点
node_A = TreeNode("6")
node_B = TreeNode("88")
node_C = TreeNode("92")
node_D = TreeNode("10")
node_E = TreeNode("11")
node_F = TreeNode("12")
node_G = TreeNode("22")
node_H = TreeNode("9")

# 构建二叉树
# 6
# / \
# 88 92
# / / \
# 10 11 12
# / \
# 22 9

2. 二叉树的序列化

第一,序列化二叉树,在序列化的同时,每遍历一个值,在该值后面加!(叹号),空节点用#(井号)表示

! (叹号) 的作用是:表示该节点内容结束,例如:如果不加!(叹号),88表示8还是88,就会有歧义了

(井号) 的作用是:表示结点为空结点,为了保持逻辑一致性,空节点也也用#!表示。其实也可以直接用#表示

第二,我们采用二叉树的前序遍历进行序列化

综合上述两方面,我们可以得到序列化后的内容应该为

1
先序序列化:6!88!10!#!#!#!92!11!22!#!#!9!#!#!12!#!#!

下面看代码:

1
2
3
4
5
6
7
def serialize_by_pre_order_traverse(self, root):
if root is None:
self.serialize_string += "#!"
return None
self.serialize_string += root.val+"!"
self.serialize_by_pre_order_traverse(root.left)
self.serialize_by_pre_order_traverse(root.right)

递归进行遍历的同时,每遍历一个结点值,就在结点值后面加 “!” (叹号),每遍历到空结点的时候,自动填 “#” (井号) 并且加 “!” (叹号)

3. 二叉树的反序列化

反序列化的重点在于构造二叉树,如果有构造二叉树的思路,那么反序列化会很简单就可以实现

第一,由于序列化后每个结点是以 “!” (叹号) 隔开的,所以需要将序列化好的结果按照 “!” 分割,存储成数组的形式

下面代码将序列化字符串分割为数组 items_tree_node

1
2
3
4
5
6
7
8
9
10
# 先序实现反序列化
def deserialize_by_pre_order_traverse(self, serialize_string):
items_tree_node = []
items = serialize_string.split("!")[0:-1]
# 将各个结点值放置到 list 中
for item in items:
items_tree_node.append(item)
# print(items_tree_node)
# 构造二叉树
return self.create_tree(items_tree_node)

第二,将数组按照前序遍历的方式,进行构造二叉树

1
2
3
4
5
6
7
8
9
10
def create_tree(self, item_tree_node):
if len(item_tree_node) <= 0:
return None
item = item_tree_node.pop(0)
root = None
if item != '#':
root = TreeNode(item)
root.left = self.create_tree(item_tree_node)
root.right = self.create_tree(item_tree_node)
return root

代码

至此,所有的思路都已简述完毕

依据前序遍历的思路,进行了序列化和反序列化的构造

序列化:依据前序遍历每个结点,每个结点用 “!” (叹号) 分割,空结点用 “#” (井号) 表示

反序列化:将序列化好的结果,按照 “!” (叹号) 分割存储为数组,然后依据前序遍历进行二叉树的构造

最后,将上述所有的代码进行整理之后:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
# -*- coding:utf-8 -*-
# !/usr/bin/env python

# 树结点类
class TreeNode:
def __init__(self, value):
self.val = value
self.left = None
self.right = None


class TreeSerializeAndDeserialize(object):

def __init__(self):
# 二叉树序列化后字符串结果
self.serialize_string = ""
# 二叉树反序列化字符串结果
self.deserialize_head = None

def print_tree_pre_order_traverse(self, head):
if head is None:
return None
print(head.val, end=" ")
self.print_tree_pre_order_traverse(head.left)
self.print_tree_pre_order_traverse(head.right)

def create_tree(self, item_tree_node):
if len(item_tree_node) <= 0:
return None
item = item_tree_node.pop(0)
root = None
if item != '#':
root = TreeNode(item)
root.left = self.create_tree(item_tree_node)
root.right = self.create_tree(item_tree_node)
return root

# 先序实现序列化
def serialize_by_pre_order_traverse(self, root):
# 说明:序列化二叉树,在序列化的同时,每遍历一个值,在该值后面加!(叹号),空节点用#(井号)表示
# !(叹号) 的作用是:表示该节点内容结束,例如:如果不加!(叹号),88表示8还是88,就会有歧义了
# #(井号) 的作用是:表示结点为空结点,为了保持逻辑一致性,空节点也也用#!表示。其实也可以直接用#表示
# 二叉树结构:
# 6
# / \
# 88 92
# / / \
# 10 11 12
# / \
# 22 9
# 先序序列化:6!88!10!#!#!#!92!11!22!#!#!9!#!#!12!#!#!
if root is None:
self.serialize_string += "#!"
return None
self.serialize_string += root.val+"!"
self.serialize_by_pre_order_traverse(root.left)
self.serialize_by_pre_order_traverse(root.right)

# 先序实现反序列化
def deserialize_by_pre_order_traverse(self, serialize_string):
items_tree_node = []
items = serialize_string.split("!")[0:-1]
# 将各个结点值放置到 list 中
for item in items:
items_tree_node.append(item)
# print(items_tree_node)
# 构造二叉树
return self.create_tree(items_tree_node)


if __name__ == "__main__":
# 新建节点
node_A = TreeNode("6")
node_B = TreeNode("88")
node_C = TreeNode("92")
node_D = TreeNode("10")
node_E = TreeNode("11")
node_F = TreeNode("12")
node_G = TreeNode("22")
node_H = TreeNode("9")

# 构建二叉树
# 6
# / \
# 88 92
# / / \
# 10 11 12
# / \
# 22 9

node_A.left, node_A.right = node_B, node_C
node_B.left = node_D
node_C.left, node_C.right = node_E, node_F
node_E.left, node_E.right = node_G, node_H

serialize_res = ""
# 实例化类
TS = TreeSerializeAndDeserialize()
print("\n先序遍历树结构: ")
TS.print_tree_pre_order_traverse(node_A)

# 利用先序遍历进行序列化
TS.serialize_by_pre_order_traverse(node_A)
print("\n通过先序遍历进行序列化:\n", TS.serialize_string)

# 利用先序遍历进行反序列化
print("通过先序遍历进行反序列化:")
TS.deserialize_head = TS.deserialize_by_pre_order_traverse(TS.serialize_string)
TS.print_tree_pre_order_traverse(TS.deserialize_head)

执行之后的结果:

1
2
3
4
5
6
先序遍历树结构: 
6 88 10 92 11 22 9 12
通过先序遍历进行序列化:
6!88!10!#!#!#!92!11!22!#!#!9!#!#!12!#!#!
通过先序遍历进行反序列化:
6 88 10 92 11 22 9 12

最后

在这里给大家准备了几百本的互联网技术类书籍,需要的来下载吧!点击获取
有任何问题,欢迎随时交流!!!

------ 全文结束------