Definition of serialization:
Serialization refers to the process of converting the data structure or object state into a usable format (e.g. stored as a file, buffered, or sent over the network) for subsequent recovery in the same or another computer environment. When the byte result is retrieved according to the serialization format, it can be used to produce a copy with the same semantics as the original object.
The reverse operation of extracting a data structure from a series of bytes is deserialization.
Sequential serialization and deserialization
1. Sequential serialization
Each node of the binary tree is stored one by one as a string separated by the specified separator in the way of traversal in advance. Empty nodes also need to be stored.
/**
* Sequential serialization
*
* @author Java And algorithm learning: Monday
*/
public static Queue<String> preSerial(Node head) {
Queue<String> ans = new LinkedList<>();
pre(head, ans);
return ans;
}
private static void pre(Node head, Queue<String> ans) {
if (head == null) {
ans.add(null);
} else {
ans.add(String.valueOf(head.value));
pre(head.left, ans);
pre(head.right, ans);
}
}
2. Deserialization in preorder mode
In the way of traversal in advance, the string before the specified separator is cut one by one, and the original binary tree is restored.
/**
* Deserialization in preorder mode
*
* @author Java And algorithm learning: Monday
*/
public static Node buildByPre(Queue<String> queue) {
if (queue == null || queue.size() == 0) {
return null;
}
return preB(queue);
}
private static Node preB(Queue<String> queue) {
String value = queue.poll();
if (value == null) {
return null;
}
Node head = new Node(Integer.parseInt(value));
head.left = preB(queue);
head.right = preB(queue);
return head;
}
Sequential serialization and deserialization
1. The idea and process of serialization and deserialization in post order mode are the same as that in pre order mode.
It should be noted that during deserialization, you must first reverse the order of the original serialization (the reversed order is the right and left of the head), and then deserialize in the way of the right and left of the head, because there must be a head before there are children (the child can be constructed only after the head is constructed), so the result of deserialization is correct.
/**
* Sequential serialization
*
* @author Java And algorithm learning: Monday
*/
public static Queue<String> posSerial(Node head) {
Queue<String> ans = new LinkedList<>();
pos(head, ans);
return ans;
}
public static void pos(Node head, Queue<String> ans) {
if (head == null) {
ans.add(null);
} else {
pos(head.left, ans);
pos(head.right, ans);
ans.add(String.valueOf(head.value));
}
}
/**
* Sequential deserialization
*
* @author Java And algorithm learning: Monday
*/
public static Node buildByPos(Queue<String> queue) {
if (queue == null || queue.size() == 0) {
return null;
}
Stack<String> stack = new Stack<>();
while (!queue.isEmpty()) {
stack.push(queue.poll());
}
return posB(stack);
}
public static Node posB(Stack<String> posStack) {
String value = posStack.pop();
if (value == null) {
return null;
}
Node head = new Node(Integer.parseInt(value));
head.right = posB(posStack);
head.left = posB(posStack);
return head;
}
2. Why is there no serialization in middle order?
Binary trees cannot be serialized and deserialized through middle order traversal, because two different trees may get the same middle order sequence. At this time, it is impossible to determine which binary tree the middle order sequence represents.
Serialize and deserialize hierarchically
1. Serialization
(1) Prepare a queue for putting results (putting the string value of the node) and an auxiliary queue (putting the node)
(2) Put the value of the head node into the result queue and the head node into the auxiliary queue
(3) Pop up the header node of the auxiliary queue,
1) The left child of this node is not empty. Put the value of the left child node into the result queue and the left child into the auxiliary queue; If the left child of this node is empty, put a null value into the result queue, and the auxiliary queue remains unchanged.
2) The right child of this node is not empty. Put the value of the right child node into the result queue and the right child into the auxiliary queue; If the right child of this node is empty, put a null value into the result queue, and the auxiliary queue remains unchanged.
(4) Continue with step 3 until the secondary queue is empty.
/**
* Serialize by layer
*
* @author Java And algorithm learning: Monday
*/
public static Queue<String> levelSerial(Node head) {
Queue<String> ans = new LinkedList<>();
if (head == null) {
ans.offer(null);
} else {
//Put the value of the header node into the result queue
ans.add(String.valueOf(head.value));
//Prepare a secondary queue
Queue<Node> help = new LinkedList<>();
//Put the auxiliary queue into the header node
help.offer(head);
while (!help.isEmpty()) {
Node current = help.poll();
//The left child of the auxiliary queue header node is not empty
if (current.left != null) {
//Put the left child's value into the result queue
ans.offer(String.valueOf(current.left.value));
//Put the left child in the auxiliary queue
help.offer(current.left);
} else {
//Put null into the result queue, and the auxiliary queue remains unchanged
ans.offer(null);
}
//The same goes for the right child
if (current.right != null) {
ans.offer(String.valueOf(current.right.value));
help.offer(current.right);
} else {
ans.offer(null);
}
}
}
return ans;
}
2. Deserialization
(1) Pop up the first value from the original queue and deserialize to generate the header node
(2) Prepare an auxiliary queue (for the node) and put it into the header node
(3) Pop up the first node current of the auxiliary queue, pop up a value from the original queue, and deserialize it as the left child of current; Then pop up a value from the original queue and deserialize it as the right child of current
(4) If the left child of current is not empty, it will be placed in the auxiliary queue; If the right child of current is not empty, it will be put into the auxiliary queue
(5) Continue to cycle through steps 3 and 4 until the auxiliary queue is empty
/**
* Deserialize by layer
*
* @author Java And algorithm learning: Monday
*/
public static Node buildByLevel(Queue<String> queue) {
if (queue == null || queue.size() == 0) {
return null;
}
//Deserialize build header node
Node head = generateNode(queue.poll());
//Prepare a secondary queue
Queue<Node> help = new LinkedList<>();
//Prevent only one null in the queue. If there is only one null in the queue, the whole method will end directly
if (head != null) {
//Put the auxiliary queue into the header node
help.offer(head);
}
Node current;
while (!help.isEmpty()) {
//Pop up the first node of the auxiliary queue
current = help.poll();
//Deserialize build left child
current.left = generateNode(queue.poll());
//Deserialize build right child
current.right = generateNode(queue.poll());
if (current.left != null) {
//The left child is not empty. Put the left child into the auxiliary queue
help.offer(current.left);
}
if (current.right != null) {
//The right child is not empty. Put the right child into the auxiliary queue
help.offer(current.right);
}
}
return head;
}