- 二叉树被记录成文件的过程叫作二叉树的序列化
- 通过文件内容重建原来的二叉树过程叫做二叉树反序列化
思路 : 序列化:先序遍历树,将树中字符转换进字符串,空值设置为null,隔断符号设置为! 反序列化:先将!做分隔符分隔字符串为数组,装进队列,递归遍历队列,设置结点和其左右结点.
代码:
代码语言：javascript复制package com.algorithm.practice.tree;
import com.algorithm.practice.tree.traversal.PreOrderPrint;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
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 SerializeTree(Node node){
if (node==null){
return "#!";
}
String res=node.value "!";
res =SerializeTree(node.left);
res =SerializeTree(node.right);
return res;
}
public static Node ReconstructTree(String tS){
String[] nodes = tS.split("!");
if (nodes[0].equals("#")){
return null;
}
Queue<String> queue=new LinkedList<>();
for(int i=0;i<nodes.length;i )
{
queue.offer(nodes[i]);
}
return reconPreOrder(queue);
}
private static Node reconPreOrder(Queue<String> queue) {
String value=queue.poll();
if (value.equals("#")){
return null;
}
Node head=new Node(Integer.parseInt(value));
head.left=reconPreOrder(queue);
head.right=reconPreOrder(queue);
return head;
}
public static void preOrderPrint(Node head){
System.out.print("pre-order: ");
if (head!=null){
Stack<Node> stack=new Stack<>();
stack.push(head);
while (!stack.isEmpty()){
head = stack.pop();
System.out.print(head.value);
if (head.right!=null){
stack.push(head.right);
}
if (head.left!=null){
stack.push(head.left);
}
}
}
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.right.right = new Node(5);
String serializeTree = SerializeTree(head);
Node node = ReconstructTree(serializeTree);
preOrderPrint(node);
}
}
