我们一起聊聊序列化二叉树

有一颗二叉树，将它转换成特定规则的字符串就称之为序列化，将序列化后的字符串按照序列化时的规则还原成二叉树就称之为反序列化。,那么如何实现二叉树与字符串之间的相互转换呢？本文就跟大家分享下这个问题的解决方案，欢迎各位感兴趣的开发者阅读本文。,在文章重建二叉树中，我们学会了利用前序遍历序列和中序遍历序列将一个字符串构建成一颗二叉树。这个思路有两个缺点：,其实，当我们用前序遍历来读取二叉树时，得到的序列是从根节点开始的，那么反序列化时在根节点读取出来之后就可以开始了。当我们在序列化的时候可能会遇到空节点，我们用一个特殊的字符来标记它（例如”$”）。节点值之间的连接也需要用特殊字符标记（例如”,”）。,序列化的规则捋清楚后，我们举个例子来验证下是否可行，如下所示（一颗二叉树）：,,根据上面定义的规则，我们使用前序遍历得到的序列为：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,$,$”。,,字符串中的所有字符已读取完毕，序列化流程结束，树也完成重建，如下图所示（去掉了分析思路时所画的辅助线）,,经过前面的分析，我们已经得到了完整的思路，接下来我们来看下代码的实现。,我们利用前序遍历即可完成二叉树的序列化。,我们序列化的时候用的前序遍历，同样的在反序列化的时候也要使用前序遍历。反序列的时候稍微麻烦些，需要先把字符串中的每个字符放到数组中。随后再按照我们前面的分析：,我们用文章开头所列举的例子来验证下上述代码能否正确的解决问题。,执行结果如下所示。,,本文用到的代码完整版请移步：