Java教程

【算法】二叉树的序列化与反序列化

本文主要是介绍【算法】二叉树的序列化与反序列化,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

序列化(serialization)在计算机科学的数据处理中,是指将数据结构或对象状态转换成可取用格式(例如存成文件,存于缓冲,或经由网络中发送),以留待后续在相同或另一台计算机环境中,能恢复原先状态的过程。从一系列字节提取数据结构的反向操作,是反序列化(也称为解编组、deserialization、unmarshalling)。

二叉树的序列化:一棵二叉树变成字符串形式。

二叉树的反序列化:从字符串形式变成一棵唯一确定的树。

public class SerializeAndReconstructTree {
    private static final String SEP = "_"; //分隔符
    private static final String NULL = "#"; //代表空节点的字符

    /*
    前序遍历序列化二叉树
    */
    public static String serialByPre(Node head) {
        StringBuilder res = new StringBuilder(""); //用于拼接字符串
        serialByPre(head, res);
        return res.toString();
    }
    //递归前序遍历的过程中完成序列化
    private static void serialByPre(Node head, StringBuilder res) {
        if (head == null) { //边界条件
            res.append(NULL).append(SEP);
            return;
        }
        res.append(head.value).append(SEP);
        serialByPre(head.left, res);
        serialByPre(head.right, res);
    }
    /*
    基于前序遍历序列化字符串反序列化
    */
    public static Node reconByPreString(String preStr) {
        String[] values = preStr.split(SEP);
        Queue<String> queue = new LinkedList<>(Arrays.asList(values));
        return reconByPreOrder(queue);
    }
    private static Node reconByPreOrder(Queue<String> queue) {
        if (queue.isEmpty()) {
            return null;
        }
        String value = queue.poll();
        if (value.equals(NULL)) {
            return null;
        }
        Node head = new Node(Integer.valueOf(value));
        head.left = reconByPreOrder(queue);
        head.right = reconByPreOrder(queue);
        return head;
    }

    /*
    后续遍历序列化
    */
    public static String serialByPos(Node head) {
        StringBuilder res = new StringBuilder();
        serialByPos(head, res);
        return res.toString();
    }
    private static void serialByPos(Node head, StringBuilder res) {
        if (head == null) {
            res.append(NULL).append(SEP);
            return;
        }
        serialByPos(head.left, res);
        serialByPos(head.right, res);
        res.append(head.value).append(SEP);
    }

    /*
    基于后续序列化字符串反序列化
    */
    public static Node reconByPosString(String posStr) {
        String[] values = posStr.split(SEP);
        LinkedList<String> list = new LinkedList<>(Arrays.asList(values));
        return reconByPosOrder(list);
    }
    //后续遍历是左右根,根节点在最后,所以要从后往前取出元素构建二叉树,而且要先建右子树再建左子树
    private static Node reconByPosOrder(LinkedList<String> list) {
        if (list.isEmpty()) {
            return null;
        }
        String value = list.removeLast(); //从后往前取出元素
        if (value.equals(NULL)) {
            return null;
        }
        Node head = new Node(Integer.valueOf(value));
        head.right = reconByPosOrder(list);
        head.left = reconByPosOrder(list);
        return head;
    }

    /*
    中序遍历序列化
    */
    public static String serialByIn(Node head) {
        StringBuilder res = new StringBuilder();
        serialByIn(head, res);
        return res.toString();
    }
    private static void serialByIn(Node head, StringBuilder res) {
        if (head == null) {
            res.append(NULL).append(SEP);
            return;
        }
        serialByIn(head.left, res);
        res.append(head.value).append(SEP);
        serialByIn(head.right, res);
    }

    /*
    层次遍历序列化
    */
    public static String serialByLevel(Node head) {
        StringBuilder res = new StringBuilder();
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            if (cur == null) {
                res.append(NULL).append(SEP);
                continue;
            }
            res.append(cur.value).append(SEP);
            queue.add(cur.left);
            queue.add(cur.right);
        }
        return res.toString();
    }
    /*
    基于层次序列化字符串反序列化
    */
    public static Node reconByLevelStr(String levelStr) {
        if (levelStr.isEmpty()) {
            return null;
        }
        String[] values = levelStr.split(SEP);
        if (values[0].equals(NULL)) {
            return null;
        }
        Node head = new Node(Integer.valueOf(values[0])); //层次遍历序列中第一个值是根节点值
        Queue<Node> queue = new LinkedList<>(); //记录父节点
        queue.add(head);
        for (int i = 1; i < values.length; i++) {
            Node parent = queue.poll(); //取出父节点
            String left = values[i++]; //取出父节点对应左孩子值
            if (!left.equals(NULL)) {
                parent.left = new Node(Integer.valueOf(left));
                queue.add(parent.left);
            } else {
                parent.left = null;
            }
            String right = values[i]; //取出父节点对应右孩子值
            if (!right.equals(NULL)) {
                parent.right = new Node(Integer.valueOf(right));
                queue.add(parent.right);
            } else {
                parent.right = null;
            }
        }
        return head;
    }
}

需要注意的是中序序列化的字符串不能反序列化,因为中序遍历的字符串确定不了根节点的位置。

例如对于下面两个二叉树而言

image-20220124001555835

对应的中序序列化结果均为 #_4_#_2_#_1_#_3_#_5_#_

序列化结果不能唯一确定一棵二叉树,所以不能反序列化。

应用:判断一棵二叉树是不是另一棵二叉树的子树。

这篇关于【算法】二叉树的序列化与反序列化的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!