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

标签: # 二叉树  二叉树

二叉数序列化

二叉树的序列化是指:把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串,从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改,序列化的结果是一个字符串,序列化时通过某种符号表示空节点(#),以 _ 表示一个结点值的结束(value_)。
下图是先序序列化的示意图:
在这里插入图片描述

二叉树的反序列化

二叉树的反序列化是指:根据某种遍历顺序得到的序列化字符串结果str,重构二叉树。

先序序列化代码

public static String serialByPre(Node root){
    if (root==null){
        return "#_";
    }
    String res=root.value+"_";
    res+=serialByPre(root.left);
    res+=serialByPre(root.right);
    return res;
}

先序反序列化代码

public static Node reconByPreString(String preStr){
    String[] values=preStr.split("_");
    Queue<String> queue=new LinkedList<>();
    for (String s:values){
        queue.offer(s);
    }
    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 String serialByLevel(Node root){
    if (root == null){
        return "#_";
    }
    String res=root.value+"_";
    Queue<Node> queue=new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()){
        root=queue.poll();
        if (root.left!=null){
            res+=root.left.value+"_";
            queue.offer(root.left);
        }else {
            res+="#_";
        }
        if (root.right!=null){
            res+=root.right.value+"_";
            queue.offer(root.right);
        }else {
            res+="#_";
        }
    }
    return res;
}

层次反序列化代码

public static Node reconByLevelString(String levelStr){
    String[] values=levelStr.split("_");
    Queue<Node> queue=new LinkedList<>();
    int index=0;
    Node root=getNodeByString(values[index++]);
    if (root!=null){
        queue.offer(root);
    }
    Node node=null;
    while (!queue.isEmpty()){
        node=queue.poll();
        node.left=getNodeByString(values[index++]);
        node.right=getNodeByString(values[index++]);
        if (node.left!=null){
            queue.offer(node.left);
        }
        if (node.right!=null){
            queue.offer(node.right);
        }
    }
    return root;
}
版权声明:本文为coffee_dount原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/coffee_dount/article/details/105989153

智能推荐

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

猜你喜欢

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...

力扣困难难度 第4题 寻找两个正序数组的中位数

先看一眼题 我的思路: 设置下标i,j分别用于遍历两个数组,初始值均为0,直到找到两个数组中从小到大的第第length/2个数为止结束循环,length为两个数组长度之和。 ·每次比较nums[i]nums[j],如果前者小则i++,否则j++ ·循环结束时,如果count已经达到length/2,则说明已经找到了中位数,[注意:此时有可能正好其中一个数组遍历完了!所以...

[国家集训队]小Z的袜子(莫队)

[国家集训队]小Z的袜子 题目描述 作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命…… 具体来说,小Z把这NN只袜子从1到NN编号,然后从编号LL到RR(LL 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同...

服务器配置(五) 服务器使用tomcat配置https全过程

一.了解服务器配置https协议 HTTPS,是以安全为目标的HTTP通道,简单讲是HTTP的安全版。即HTTP下加入SSL层,HTTPS的安全基础是SSL,因此加密的详细内容就需要SSL。 配置HTTPS就需要证书,证书通过权威的CA机构付费获得的证书才能被互联网承认,我们将其放在服务器上面,配置好后,就可以进行https通信了。 通过https访问的网站,在地址前可以看到安全两个字,点击可以查...

SQL语言——基本概念、操作数据库、表、表记录、数据库备份与恢复、外键约束

SQL语言 1.基本概念 1.1 SQL SQL–Structured Query Language, 结构化查询语言,是关系型数据库通用的操作语言。 是一种非过程性语言。 由美国国家标准局(ANSI)与国际标准化组织(ISO)制定SQL标准。各大数据库厂商都对其做了实现。所以我们只要学会了SQL语言,就可以操作各大关系型数据库了。 为加强SQL的语言能力,各厂商增强了过程性语言的特征...