二叉树的序列化和反序列化
发布日期:2021-08-19 19:59:55 浏览次数:2 分类:技术文章

本文共 2867 字,大约阅读时间需要 9 分钟。

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

给定一个二叉树头节点head,并已知二叉树节点值的类型为32位整型。设计一种二叉树序列化,和反序列化方案,并且代码实现。

 

 

方法一,先序遍历下的序列化过程,首先假设徐立华的结果字符串为str,初始str=“”, 先序遍历二叉树,如果遇到null节点,就在str末尾加上“#”  节点不存在,“!”表示一个值的结束。如果遇到不为空的节点,假设节点值为3,就在str的末尾加上 3!。

package TT;public class Test200 {	public class Node{		public int value;		public Node left;		public Node right;				public Node(int data){			this.value=data;		}	}		  public String serialByPre(Node head){	  if(head==null){		  return "#!";	  }	  String res = head.value+"!";	  res += serialByPre(head.left);	  res += serialByPre(head.right);	  return res;  }	}

  接下来,通过先序遍历序列化的结果字符串str,重构二叉树的过程,反序列化。

方法二、通过层遍历实现序列化和反序列化

  初始时 str=“空”  然后实现二叉树的按层遍历,具体方式是利用队列结构,也就是宽度遍历图的常见方式。

 

package TT;import java.util.LinkedList;import java.util.Queue;public class Test200 {	public class Node{		public int value;		public Node left;		public Node right;				public Node(int data){			this.value=data;		}	}	public String serialBylevel(Node head){	if(head == null){		return "#!";	}	String res = head.value+"!";	Queue
queue = new LinkedList
(); 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; } }

  

先序遍历的反序列化其实就是重做先序遍历,遇到“#”就生成null节点,结束生成后续子树的过程

package TT;import java.util.LinkedList;import java.util.Queue;public class Test200 {	public class Node{		public int value;		public Node left;		public Node right;				public Node(int data){			this.value=data;		}	}	public String serialBylevel(Node head){	if(head == null){		return "#!";	}	String res = head.value+"!";	Queue
queue = new LinkedList
(); 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; } public Node reconByLevelString(String levelStr){ String[] values = levelStr.split("!"); int index = 0; Node head = generateNodeByString(values[index++]); Queue
queue = new LinkedList
(); 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 Node generateNodeByString(String val){ if(val.equals("#")){ return null; } return new Node(Integer.valueOf(val));}}

  

 

转载于:https://www.cnblogs.com/toov5/p/7541871.html

转载地址:https://blog.csdn.net/weixin_30951743/article/details/95890012 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:MySQL高可用
下一篇:Java7的新特性

发表评论

最新留言

表示我来过!
[***.240.166.169]2024年03月23日 19时40分25秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

如何修改手机屏幕显示的长宽比例_屏幕分辨率 尺寸 比例 长宽 如何计算 2019-04-21
mysql 的版本 命名规则_MySQL版本和命名规则 2019-04-21
java 验证码校验_JavaWeb验证码校验功能代码实例 2019-04-21
php curl 输出到文件,PHP 利用CURL(HTTP)实现服务器上传文件至另一服务器 2019-04-21
PHP字符串运算结果,PHP运算符(二)"字符串运算符"实例详解 2019-04-21
PHP实现 bcrypt,如何使php中的bcrypt和Java中的jbcrypt兼容 2019-04-21
php8安全,PHP八大安全函数解析 2019-04-21
php基础语法了解和熟悉的表现,PHP第二课 了解PHP的基本语法以及目录结构 2019-04-21
matlab中lag函数用法,MATLAB movavg函数用法 2019-04-21
matlab变形监测,基于matlab的变形监测数据处理与分析_毕业设计论文 2019-04-21
opencv matlab编程,在Matlab中调用OpenCV函数 | 学步园 2019-04-21
c语言文件wt,c语言,wt和rt中的t是什么意思 2019-04-21
c语言运行几进制,【C语言】求已知等式在几进制条件下成立 2019-04-21
电梯运行仿真c语言代码,电梯调度算法模拟(示例代码) 2019-04-21
android组件动态接收数据库,Android开发——fragment中数据传递与刷新UI(更改控件)... 2019-04-21
云麦小米华为体脂秤怎么样_云康宝和华为智能体脂秤对比评测,实际体验告诉你哪款更好... 2019-04-21
linux 条件判断 取非_Linux awk 系列文章之 awk 多重条件判断 2019-04-21
c语言中如何将字符串的元素一个一个取出_C语言中常用的字符串操作函数 2019-04-21
2d游戏地图编辑器_王者荣耀:新版本爆料!地图编辑器“天工”即将开测,游戏怎么玩由你定!... 2019-04-21
.net framework服务启动后停止_dos命令net图文教程,start启动系统服务stop停止服务批处理脚本... 2019-04-21