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

前言

本文主要介绍二叉树的序列化与反序列化。

正文

先来看下什么是二叉树的序列化，一棵二叉树生成后在计算机的内存里不一定是在一块连续的内存空间中，各个节点是用指针指向的内存地址连起来的。

序列化指的是把内存中这个二叉树通过某种方式存在磁盘中、数据库中、转成JSON形式等。

相反，反序列化是指从磁盘中、数据库中、转成JSON形式读取到内存中。

一个二叉树在序列化后，再通过反序列化要保证前后结构一模一样，不能改变二叉树的结构。

本次介绍的序列化指的是将一个二叉树转为字符串的过程，反序列化指的是将一个字符串还原成二叉树的过程。

思路分析

序列化过程

把一个二叉树进行序列化简单的方式就是采用先序遍历的方式，关于怎么对二叉树进行先序遍历，之前已经介绍过了，不清楚的小伙伴可以查看这篇文章：juejin.cn/post/722115…。

采用先序遍历进行序列化，需要注意的是在遍历的时候，空节点不能忽略的，需要用一个特殊符号来标记下来。

在转成字符串的过程，节点间采用逗号（或其他符号）分隔。

例如，上图二叉树先序遍历的结果为：a->b->d->e->c，那么转成字符串形式应该为：“a,b,d,null,null,e,null,null,c,null,null”。

反序列化过程

在反序列化的时候，先把字符串用逗号分隔，分隔后会得到一个数组，然后对数组进行for循环遍历，如果有值则创建一个节点，如果没有值则说明是一个空节点。

在反序列化时，从第一个值开始先创建头结点，依次创建左节点，直到遇到null值，就开始创建右节点，如果遇到两个null，说明这个节点既没有左节点又没有右节点，也就是该切换到父节点的右节点了。

如图中的d节点，他的两个子节点都为null，之后就是节点e了。

代码实现

为了方便起见，我们把序列化的结果放到一个队列中。

先看下序列化的过程，节点定义代码如下：

public class Node {
   public int value;
   public Node left;
   public Node right;
}

序列化代码逻辑实现：

public Queue<String> preSerial(Node head) {
   Queue<String> ans = new LinkedList<>();
   pres(head, ans);
   return ans;
}

public void pres(Node head, Queue<String> ans) {
   if (head == null) {
      ans.add(null);
  	  return;
   }
   // 先处理头结点
   ans.add(String.valueOf(head.value));
   // 处理左结点
   pres(head.left, ans);
   // 处理有结点
   pres(head.right, ans);
}

实现方式依然采用的是递归方式，递归处理的时候安装先序遍历的方式，先添加头结点，然后处理左节点，最后处理右节点。

再来看下反序列化的过程：

public Node buildPreQueue(Queue<String> prelist) {
   if (prelist == null || prelist.size() == 0) {
      return null;
   }
   return preb(prelist);
}

public Node preb(Queue<String> prelist) {
   String value = prelist.poll();
   if (value == null) {
      return null;
   }
   // 先创建头结点
   Node head = new Node(Integer.valueOf(value));
   // 处理左节点
   head.left = preb(prelist);
	 // 处理右节点
   head.right = preb(prelist);
   return head;
}

序列化过程也可以安装后序的遍历方式实现，但是不能按照中序的遍历方式实现，因为不同的二叉树中序遍历的结果可能是一样的，如下：

这两个二叉树的中序遍历结果都是b->a，序列化的结果也都是“null,b,null,a,null”，所以通过中序遍历是不能还原会原来的样子的。

总结

本文主要介绍二叉树的序列化与反序列化，在序列化时可以采用先序遍历和后序遍历，而不能采用中序遍历，因为有可能不同的二叉树中序遍历结果是一样的。

除了采用先序、后序遍历方式之外，还可以采用按层遍历，思路也和先序遍历类似，这里就不介绍了。