0%

二叉树序列化和反序列化

发表于 分类于
本文字数： 阅读时长 ≈

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

二叉树记录成文件(一般是字符串形式)的过程叫做序列化，通过文件内容重构出一颗二叉树的过程叫做二叉树的反序列化。

方法一：通过先序遍历实现序列化和反序列化
序列化：

1
2
3
4
5
6
7
8
9
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
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class SerialByPre {
    //序列化代码
	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 void main(String[] args) {
		// TODO Auto-generated method stub
		Node head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.left.right= new Node(5);
		head.right.left= new Node(6);
		head.right.right= new Node(7);
		String str = serialByPre(head);
		System.out.println(str);
		
	}
}

反序列化：
反序列化函数：

1
2
3
4
5
6
7
8
public static Node reconByPreString (String preStr) {
	String[] strs = preStr.split("_");
	Queue<String> queue = new LinkedList<String>();
	for (int i = 0; i < strs.length; i++) {
		queue.offer(strs[i]);
	}
	return reconPreOrder(queue);
}

reconPreNode函数：
作用是从一个字符串重构出一棵二叉树

1
2
3
4
5
6
7
8
9
10
   public static Node reconPreNode(Queue<String> queue) {
	String value = queue.poll();
	if (value.equals("#")) {
		return null;
	}
	Node head = new Node(Integer.valueOf(value));
	head.left = reconPreNode(queue);
	head.right = reconPreNode(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
public static String serialByLevel (Node head) {
    if (head == null) {
        return "#_";
    }
    String res = head.value + "_";
    Queue<Node> queue = new LinkedList<Node>();
    queue.offer(head);
    while (!queue.isEmpty()) {
        head = queue.poll();
        if (head.left != null) {
            res += head.left.value + "_";
            queue.offer(head.left);
        } else {
            res += "#_";
        }
        if (head.right != null) {
            res += head.right.value + "_";
            queue.offer(head.right);
        } else {
            res += "#_";
        }
    }
    return res;
}
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
   public static Node reconByLevelString(String levelStr) {
	String[] values = levelStr.split("_");
	int index = 0;
	Node head = generateNodeByString(values[index++]);
	Queue<Node> queue = new LinkedList<Node>();
	if (head != null) {
		queue.offer(head);
	}
	Node node = null;
	while (!queue.isEmpty()) {
		node = queue.poll();
		node.left = generateNodeByString(values[index++]);
		node.right = generateNodeByString(values[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));
}

以上方法二是按层序列化二叉树和反序列化构造出一颗二叉树的代码。