序列化二叉树

发表于 阅读次数：

序列化简介

在程序运行的过程中，所有对象的状态（属性）都是存在内存中的，一旦程序结束，内存都会被释放，这时我们对象的信息都没了，

如果我们的程序每次执行都会改变变量，如第一次a = 1,，下一次可能是a = 2。一直下去，我们想要保存每一次执行a的信息,为了解决这个问题，序列化出现了。

  • 序列化可以帮助我们把内存中的对象的信息，保存在硬盘上。
  • 与序列化相反的是反序列化，很容易猜到，反序列化就是把硬盘上的信息，写入内存中。

了解了序列化与反序列化的概念，下面我们来试试看二叉树的序列化吧。

二叉树的序列化

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树

二叉树有四种基本的遍历方式，前序、中序、后序以及层序遍历。（不晓得的兄弟萌可以看以前的博客）

我们需要先约定好保存的格式，这里给定一个树及其遍历顺序如下：

保存的格式如下：

  • 前序遍历的保存格式
    • 1-2-4-#-#-5-#-#-3-6-#-#-7-#-#-
  • 中序遍历的保存格式
    • #-4-#-2-#-5-#-1-#-6-#-3-#-7-#-
  • 后序遍历的保存格式
    • #-#-4-#-#-5-2-#-#-6-#-#-7-3-1-
  • 层序遍历的保存格式
    • 1-2-3-4-5-6-7-#-#-#-#-#-#-#-#-

其中-代表下一个节点,#代表节点为空(Null)

其实序列化二叉树的代码和对应的遍历二叉树的十分相似，只是把它存为字符串并返回罢了。

思路

这里序列化的过程和常规的遍历过程十分相似，因此这里就不阐述了，兄弟萌可以顺便复习以下前中后序遍历。下面我们提供前序遍历和层序遍历的序列化和反序列化。

实现

前序遍历版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//序列化
public static String serialByPreOrder(Node head) {
    if(head == null)
        return "#-";
    String res = head.value + "-";
    res = res + serialByPreOrder(head.left);
    res = res + serialByPreOrder(head.right);
    return res;
}

//--------------------------------------

//反序列化
public static Node reconByPreString(String preStr) {

    String[] split = preStr.split("-");
    //这里我们使用队列，兄弟萌可以试下改用数组来写。
    Queue<String> queue = new LinkedList<>();
    for(int i = 0; i < split.length; i++) {
        queue.offer(split[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;
}

层序遍历版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/序列化
public static String serialByLevelNoRec(Node head) {
    if(head == null) return "#-";

    Queue<Node> queue = new LinkedList<>();
    String str = head.value + "-";
    queue.offer(head);
    while(!queue.isEmpty()) {
        Node poll = queue.poll();
        if(poll.left != null) {
            str += poll.left.value + "-";
            queue.offer(poll.left);
        }else {
            str += "#-";
        }
        if(poll.right != null) {
            str += poll.right.value + "-";
            queue.offer(poll.right);
        }else {
            str += "#-";
        }
    }
    return str;
}

//--------------------------------------

//反序列化
public static Node reconByLevel(String str) {
    String[] split = str.split("-");
    int index = 0;
    Queue<Node> queue = new LinkedList<>();
    Node head = generateNodeByString(split[index++]);
    if(head != null) {
        queue.offer(head);
    }
    Node node = null;
    while(!queue.isEmpty()) {
        node = queue.poll();
        node.left = generateNodeByString(split[index++]);
        node.right = generateNodeByString(split[index++]);
        if(node.left != null) {
            queue.offer(node.left);
        }
        if(node.right != null) {
            queue.offer(node.right);
        }
    }
    return head;
}

//辅助方法
public static Node generateNodeByString(String val) {
    if (val.equals("#")) {
        return null;
    }
    return new Node(Integer.valueOf(val));
}