二叉树的序列化与反序列化(先序,按层序列化),包含递归图
二叉树的序列化与反序列化
序列化:将对象的状态信息转换为可以存储或传输的形式的过程
二叉树的序列化:就是将二叉树转换成字符串
二叉树的反序列化:通过字符串还原一棵二叉树,返回树的头节点.
先序序列化二叉树
上面这棵树的先序序列化结果为5!3!2!1!#!#!#!4!#!#!8!7!6!#!#!#!10!9!#!#!11!#!#!
从上图中我们可以看出在节点为空的位置使用"#!“来代替,每个节点后的数值都添加一个”!".
这样做的 目的: 为了使我们可以使用序列化后的字符串,通过反序列化还原原来的树.所以要做一些标志(也可以使用其他的特殊的符号),文章末尾会列举出几个反例,帮助大家理解.
/**
* 先序序列化
*
* @param 二叉树的根
* @return 序列化后的字符串
*/
public static String serializePer(Node head) {
StringBuilder res = new StringBuilder();
perSerialize(head, res);
return res.toString();
}
public static void perSerialize(Node head, StringBuilder res) {
if (head == null) {
res.append("#!");
return;
}
res.append(head.value + "!");
perSerialize(head.left, res);
perSerialize(head.right, res);
}
先序反序列化二叉树
/**
* 反序列化
*
* @param res : 序列化后的字符串
* @return 反序列化后的树的头节点
* 5!3!2!1!#!#!#!4!#!#!8!7!6!#!#!#!10!9!#!#!11!#!#!
*/
public static Node receiverPer(String res) {
String[] str = res.split("!");
Queue<String> queue = new LinkedList<>();
for (int i = 0; i < str.length; i++) {
queue.offer(str[i]);
}
return reconPreOrder(queue);
}
public static Node reconPreOrder(Queue<String> queue) {
String value = queue.poll();
if (value.equals("#")) {
return null;
}
Node head = new Node(Integer.valueOf(value));
head.left = reconPreOrder(queue);
head.right = reconPreOrder(queue);
return head;
}
按层序列化
**结果: 5!3!8!2!4!7!10!1!#!#!#!6!#!9!11!#!#!#!#!#!#!#!#!
按层序列化就是将"#!“和”!"补全后,逐层添加
//按层序列化
public static String perLevel(Node head) {
if (head == null) {
return "#!";
}
String str = head.value + "!";
Queue<Node> queue = new LinkedList<>();
queue.offer(head);
while (!queue.isEmpty()) {
head = queue.poll();
if (head.left != null) {
str += head.left.value + "!";
queue.offer(head.left);
} else {
str += "#!";
}
if (head.right != null) {
str += head.right.value + "!";
queue.offer(head.right);
} else {
str += "#!";
}
}
return str;
}