当前栏目
我们一起聊聊序列化二叉树
前言
有一颗二叉树,将它转换成特定规则的字符串就称之为序列化,将序列化后的字符串按照序列化时的规则还原成二叉树就称之为反序列化。
那么如何实现二叉树与字符串之间的相互转换呢?本文就跟大家分享下这个问题的解决方案,欢迎各位感兴趣的开发者阅读本文。
实现思路
在文章重建二叉树中,我们学会了利用前序遍历序列和中序遍历序列将一个字符串构建成一颗二叉树。这个思路有两个缺点:
- 二叉树中不能有数值重复的节点
- 只有当两个序列中所有的数据都读出来后才能开始反序列化(如果两个序列中的数据都是从一个流里读出来的,那么就需要等待比教长的时间)
其实,当我们用前序遍历来读取二叉树时,得到的序列是从根节点开始的,那么反序列化时在根节点读取出来之后就可以开始了。当我们在序列化的时候可能会遇到空节点,我们用一个特殊的字符来标记它(例如"$")。节点值之间的连接也需要用特殊字符标记(例如",")。
序列化的规则捋清楚后,我们举个例子来验证下是否可行,如下所示(一颗二叉树):
根据上面定义的规则,我们使用前序遍历得到的序列为:1,2,4,$,$,$,3,5,$,$,6,$,$。
经过验证,上述方法成功的实现了树的序列化。接下来我们以字符串1,2,4,$,$,$,3,5,$,$,6,$,$为例分析如何反序列化二叉树。
第一个读出的数字是1。由于前序遍历是从根节点开始的,这是根节点的值。紧接着读出的数字是2,根据前序遍历的规则,这是根节点的左子节点的值。同样的,接下来的数字4是值为2的节点的左子节点。
接着从序列化字符串里读出两个字符"$",这表明节点4的左、右子节点均为空,因此它是一个叶节点。
接下来返回至节点2,重建它的右子节点。继续读取字符,下一个字符是"$",这表明节点2的右子节点为空。这个节点的左、右子树都已经构建完毕。
接下来返回至根节点,反序列化根节点的右子树。
下一个序列化字符串中读取出来的数字是3,因此根节点的右子树的值为3。它的左子节点是一个值为5的叶节点,因为接下来的三个字符是"5,$,$"。
同样,它的右子节点是值为6的叶节点,因为最后3个字符是"6,$,$"。
字符串中的所有字符已读取完毕,序列化流程结束,树也完成重建,如下图所示(去掉了分析思路时所画的辅助线)
实现代码
经过前面的分析,我们已经得到了完整的思路,接下来我们来看下代码的实现。
序列化二叉树
我们利用前序遍历即可完成二叉树的序列化。
反序列化
我们序列化的时候用的前序遍历,同样的在反序列化的时候也要使用前序遍历。反序列的时候稍微麻烦些,需要先把字符串中的每个字符放到数组中。随后再按照我们前面的分析:
- 定义一个全局变量across用来表示当前读取到了第几个字符(已走步长)
- 递归执行构建函数时,已走步长先自增。
- 根节点的左子树一定是紧根其后的字符,所以从index+1位置开始继续执行递归函数直至遇到"$"字符为止
- 根节点的右子树一定是紧根在它左子树之后的字符,所以从across位置开始继续执行递归函数直至遇到"$"字符为止
- 构建函数接受两个参数:字符数组、当前读取的字符索引
- 从字符数组中读取当前字符索引位置的值,构建根节点
- 左、右子树都构建完毕后,将构建好的根节点返回就得到了一颗完整的树
测试用例
我们用文章开头所列举的例子来验证下上述代码能否正确的解决问题。
执行结果如下所示。
示例代码
本文用到的代码完整版请移步:
- SerializedBinaryTree.ts
- SerializedBinaryTree-test.ts
相关文章
- Java-Jsp是什么原理又是什么
- Java-Jsp的一些语法与指令
- js正则表达式转义字符-4. 正则表达式的使用
- js正则表达式转义字符-【JavaScript正则表达式RegExp】
- 【全网最全】springboot整合JSR303参数校验与全局异常处理
- 安装typescript环境并开启VSCode自动监视编译ts文件为js文件
- 正则表达式语法-JavaScript中的正则表达式详解
- js 数组去除重复数据-5 个提升你 JS 编码水平的实例
- js 数组去除重复数据-Vue.js开发移动端经验总结
- React.js基础知识总结一
- React.js简单轮播图组件封装
- React.js基础知识 函数组件和类组件(二)
- js for in for of 的区别
- js正则表达式基础知识
- parcel打包Vue.js零配置
- javascript学习之Pointfree是什么
- javascript学习之函数组合
- javascript中柯里化
- javascript的纯函数,纯函数怎么定义
- javascript必须要知道的闭包,怎么调试闭包