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

名字是乱打的

发布于 2022-05-13 01:49:50

20600

代码可运行

文章被收录于专栏：软件工程软件工程

运行总次数：0

代码可运行

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

思路 : 序列化:先序遍历树,将树中字符转换进字符串,空值设置为null,隔断符号设置为! 反序列化:先将!做分隔符分隔字符串为数组,装进队列,递归遍历队列,设置结点和其左右结点.

代码:

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);

    }

}