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

序列化的定义:
序列化(serialization)是指将数据结构或对象状态转换成可取用格式(例如存成文件,存于缓冲,或经由网络中发送),以留待后续在相同或另一台计算机环境中,能恢复原先状态的过程。依照序列化格式重新获取字节的结果时,可以利用它来产生与原始对象相同语义的副本。
从一系列字节提取数据结构的反向操作,是反序列化。
先序方式序列化和反序列化 1、先序方式序列化 按先序遍历的方式,挨个将二叉树的各个节点,存储为一个以指定分隔符分隔的字符串,为空的节点也需要存储。

/** * 先序方式序列化 * * @author Java和算法学习:周一 */ public static Queue preSerial(Node head) { Queue ans = new LinkedList<>(); pre(head, ans); return ans; }private static void pre(Node head, Queue ans) { if (head == null) { ans.add(null); } else { ans.add(String.valueOf(head.value)); pre(head.left, ans); pre(head.right, ans); } }

2、先序方式反序列化 按先序遍历的方式,挨个以指定分隔符切分之前的字符串,还原为原始二叉树。
/** * 先序方式反序列化 * * @author Java和算法学习:周一 */ public static Node buildByPre(Queue queue) { if (queue == null || queue.size() == 0) { return null; } return preB(queue); }private static Node preB(Queue queue) { String value = https://www.it610.com/article/queue.poll(); if (value == null) { return null; } Node head = new Node(Integer.parseInt(value)); head.left = preB(queue); head.right = preB(queue); return head; }

后序方式序列化和反序列化 1、后序方式序列化和反序列化和先序方式的思路和过程是一样的。 【二叉树的序列化和反序列化】需要注意的是在反序列化时,得先把原始序列化的顺序颠倒一下(颠倒后的顺序即是头右左),再以头右左的方式进行反序列化,因为要先有头才有孩子(先构造头才能构造孩子),这样反序列化的结果才是对的。
/** * 后序方式序列化 * * @author Java和算法学习:周一 */ public static Queue posSerial(Node head) { Queue ans = new LinkedList<>(); pos(head, ans); return ans; }public static void pos(Node head, Queue ans) { if (head == null) { ans.add(null); } else { pos(head.left, ans); pos(head.right, ans); ans.add(String.valueOf(head.value)); } }

/** * 后序方式反序列化 * * @author Java和算法学习:周一 */ public static Node buildByPos(Queue queue) { if (queue == null || queue.size() == 0) { return null; } Stack stack = new Stack<>(); while (!queue.isEmpty()) { stack.push(queue.poll()); } return posB(stack); }public static Node posB(Stack posStack) { String value = https://www.it610.com/article/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、为啥没有中序方式的序列化? 二叉树无法通过中序遍历的方式实现序列化和反序列化,因为不同的两棵树,可能得到同样的中序序列,这时候就无法确定此中序序列代表哪个二叉树了。
按层方式序列化和反序列化 1、序列化 (1)准备一个放结果的队列(放的是节点的字符串值),准备一个辅助队列(放的是节点)
(2)往结果队列放入头节点的值,往辅助队列放入头节点
(3)弹出辅助队列的头节点,
1)此节点左孩子不为空,往结果队列放入左孩子节点的值,往辅助队列放入左孩子;如果此节点左孩子为空,往结果队列放入null值,辅助队列不变。
2)此节点右孩子不为空,往结果队列放入右孩子节点的值,往辅助队列放入右孩子;如果此节点右孩子为空,往结果队列放入null值,辅助队列不变。
(4)一直执行第3步,直到辅助队列为空。
/** * 按层方式序列化 * * @author Java和算法学习:周一 */ public static Queue levelSerial(Node head) { Queue ans = new LinkedList<>(); if (head == null) { ans.offer(null); } else { // 往结果队列放入头节点的值 ans.add(String.valueOf(head.value)); // 准备一个辅助队列 Queue help = new LinkedList<>(); // 辅助队列放入头节点 help.offer(head); while (!help.isEmpty()) { Node current = help.poll(); // 辅助队列头节点的左孩子不为空 if (current.left != null) { // 往结果队列放左孩子的值 ans.offer(String.valueOf(current.left.value)); // 往辅助队列放左孩子 help.offer(current.left); } else { // 往结果队列放null,辅助队列不变 ans.offer(null); }// 右孩子同理 if (current.right != null) { ans.offer(String.valueOf(current.right.value)); help.offer(current.right); } else { ans.offer(null); } } } return ans; }

2、反序列化 (1)从原队列弹出第一个值,反序列化生成头节点
(2)准备一个辅助队列(放的是节点),放入头节点
(3)弹出辅助队列的第一个节点current,从原队列里弹出一个值,反序列化做为current的左孩子;再从原队列里弹出一个值,反序列化做为current的右孩子
(4)current的左孩子不是空,则放入辅助队列;current的右孩子不是空,则放入辅助队列
(5)一直循环执行3、4步,直到辅助队列为空
/** * 按层方式反序列化 * * @author Java和算法学习:周一 */ public static Node buildByLevel(Queue queue) { if (queue == null || queue.size() == 0) { return null; } // 反序列化构建头节点 Node head = generateNode(queue.poll()); // 准备一个辅助队列 Queue help = new LinkedList<>(); // 防止队列里就只有一个null,如果队列里就只有一个null,则整个方法就直接结束了 if (head != null) { // 辅助队列放入头节点 help.offer(head); } Node current; while (!help.isEmpty()) { // 弹出辅助队列的第一个节点 current = help.poll(); // 反序列化构建左孩子 current.left = generateNode(queue.poll()); // 反序列化构建右孩子 current.right = generateNode(queue.poll()); if (current.left != null) { // 左孩子不为空,往辅助队列放入左孩子 help.offer(current.left); } if (current.right != null) { // 右孩子不为空,往辅助队列放入右孩子 help.offer(current.right); } } return head; }

本文所有代码地址:https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/SerializeAndDeserializeTree.java

    推荐阅读