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

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

• 序列化： 就是将在内存中构建的二叉树，怎么使用文件进行存储（一般变成字符串进行处理）；
• 反序列化： 就是将文件中序列化的二叉树取出重新还原成二叉树；
• 二叉树的序列化要注意的两个点如下：
  • 每序列化一个结点数值之后都应该加上一个结束符表示一个结点序列化的终止，如!或者 _ 等等。
  • 不能忽视空结点的存在，可以使用一个占位符如#表示空结点的序列化。

解决方案：

• 方案一：使用先序遍历、中序遍历、后续遍历其中之一，同样反序列化也应该使用对应的同样方式；
• 方案二：使用按层序列化；

举个栗子：这里以先序遍历方法作为测试，下面为测试树的结构：

先序遍历结果：1_2_4_#_#_5_#_#_3_6_#_#_7_#_#_ 其中：#表示该结点为空，_表示值的结束符，这两个都可以使用其他符号进行代替；如果不使用 # 来表示空节点就无法表示整个树中结点值都是一样的情况； 反序列化：从数组的第一个元素开始，因为是先序遍历，因此该结点一定是根节点，然后开始搭建左子树，1 的左孩子是 2，2 的左孩子是 4，然后是 #，则 4 的左孩子没有，返回到节点 4，下一个还是# ，则 4 的右孩子也没有，则回到 2，。。。。

按层序列化：上面图片中的二叉树按层遍历的结果为：1_2_3_4_#_#_5_#_#_#_#_

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null){
            return "null,";
        }
        String res = root.val + ",";
        res += serialize(root.left);
        res += serialize(root.right);
        return res;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] datas = data.split(",");
        Queue<String> queue =new LinkedList<String>();
        for(int i = 0;i < datas.length;i++){
            queue.offer(datas[i]);
        }
        return reconPreOrder(queue);
    }

    public TreeNode reconPreOrder(Queue<String> queue){
        String val = queue.poll();
        if(val.equals("null")){
            return null;
        }
        TreeNode node = new TreeNode(Integer.valueOf(val));
        node.left = reconPreOrder(queue);
        node.right = reconPreOrder(queue);
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));