二叉树序列化/反序列化

柔光的暖阳◎ 2022-04-22 14:36 250阅读 0赞

二叉树被记录成文件的过程，为二叉树的序列化

通过文件重新建立原来的二叉树的过程，为二叉树的反序列化

设计方案并实现。

（已知结点类型为32位整型）

思路：先序遍历实现。

因为要写入文件，我们要把二叉树序列化为一个字符串。

首先，我们要规定，一个结点结束后的标志：“！”

然后就可以通过先序遍历生成先序序列了。

但是，众所周知，只靠先序序列是无法确定一个唯一的二叉树的，原因分析如下：

比如序列1！2！3！

我们知道1是根，但是对于2，可以作为左孩子，也可以作为右孩子：

![201811261735360.png][]![2018112617355292.png][]

对于3，我们仍然无法确定，应该作为左孩子还是右孩子，情况显得更加复杂：

![20181126173727821.png][]![20181126173745503.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70][]![2018112617384090.png][]

![20181126173947552.png][]

原因：我们对于当前结点，插入新结点是无法判断插入位置，是应该作为左孩子，还是作为右孩子。

因为我们的NULL并未表示出来。

如果我们把NULL也用一个符号表示出来：

比如

![20181126173947552.png][]

1！2！\#！\#！3！\#！\#！

我们再按照先序遍历的顺序重建：

对于1，插入2时，就确定要作为左孩子，因为左孩子不为空。

然后接下来两个\#，我们就知道了2的左右孩子为空，然后重建1的右子树即可。

我们定义结点：

public static class Node {
    		public int value;
    		public Node left;
    		public Node right;
    
    		public Node(int data) {
    			this.value = data;
    		}
    	}

序列化：

public static String serialByPre(Node head) {
    		if (head == null) {
    			return "#!";
    		}
    		String res = head.value + "!";
    		res += serialByPre(head.left);
    		res += serialByPre(head.right);
    		return res;
    	}

public static Node reconByPreString(String preStr) {
            //先把字符串转化为结点序列
    		String[] values = preStr.split("!");
    		Queue<String> queue = new LinkedList<String>();
    		for (int i = 0; i != values.length; i++) {
    			queue.offer(values[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;
    	}

这样并未改变先序遍历的时空复杂度，解决了先序序列确定唯一一颗树的问题，实现了二叉树序列化和反序列化。

[201811261735360.png]: https://img-blog.csdnimg.cn/201811261735360.png
[2018112617355292.png]: /images/20220414/080304a2c10c43df9a2e229fa42d2fbe.png
[20181126173727821.png]: https://img-blog.csdnimg.cn/20181126173727821.png
[20181126173745503.png]: /images/20220414/e24fbe1fb4944da1ae258ed8c0a868c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20181126173823193.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2,size_16,color_FFFFFF,t_70
[2018112617384090.png]: /images/20220414/9459b3d9932543e6a874642b571793c5.png
[20181126173947552.png]: /images/20220414/09e854c8160048119aad72b4502e8bc5.png