二叉树序列化和反序列化

发表于 | 分类于

看了左程云老师的算法课，记录学习过程，整理思路和形成系统认识。

题目：二叉树序列化和反序列化（算法课第五课）

二叉树被记录成文件的过程叫做二叉树的序列化，通过文件内容重建原来的二叉树的过程叫做二叉树的反序列化。

#表示这个节点为空，节点值不存在，_(后面代码用！)表示一个值的结束

image

分析

树结构

1
2
3
4
5
6
7
8
9
public static class Node {
    public int value;
    public Node left;
    public Node right;

    public Node(int data) {
        this.value = data;
    }
}

前序遍历序列化

1
2
3
4
5
6
7
8
9
public static String serialByPre(Node head) {
    if (head == null) {
        return "#!";
    }
    String res = head.value + "!";
    res += serialByPre(head.left);
    res += serialByPre(head.right);
    return res;
}

前序遍历反序列化

把结果字符串str变成字符串类型的数组，记为values,数组代表一棵二叉树先序遍历的节点顺序。

  1. 分割
  2. 还原数组
  3. 按照先序顺序还原

例如：

str=”12!3!#!#!#!”,生成的values为‘12’，‘3’，‘#’，‘#’，‘#’，然后用values[0..4]按照先序遍历的顺序建立整棵树。

1，遇到“12”，生成节点值12的节点（head） 然后用values[1..4]建立节点12的左子树

2，遇到‘3’,生成节点值为3的节点，它是节点12的左孩子，然后用values[2..4]建立节点3的左子树

3，遇到‘#’，生成null节点，它是节点3的左孩子，该节点为null，所以这个节点没有后续建立子树过程。回到节点3后，用values[3..4]建立节点3的右子树

4，遇到“#”生成null节点，它是节点3的右孩子，该节点为null，所以这个节点没有后续建立子树过程。回到节点3后，再回到节点1，用values[4]建立节点1的右子树。

5，遇到“#”，生成null节点，它是节点1的右孩子，该节点为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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.util.LinkedList;
import java.util.Queue;

public class SerializeAndReconstructTree {
	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;
	}

	public static void main(String[] args) {
		//		  	10
		//		  /	   \
		//       20     30
		//      /     /    \ 
		//     40    50    60
		Node head = new Node(10);
		head.left = new Node(20);
		head.left.left = new Node(40);
		head.right = new Node(30);
		head.right.left = new Node(50);
		head.right.right = new Node(60);
		String res = serialByPre(head);
		System.out.println(res);
		System.out.println(head.value==reconByPreString(res).value);
	}
}

输出：

1
2
10!20!40!#!#!#!30!50!#!#!60!#!#!
true
> >