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

fengjingtu

二叉树的序列化：将一棵二叉树的某种遍历方式的结果保存为字符串。

二叉树反序列化：根据一棵二叉树某种遍历方式得到的字符串，重新构建二叉树。

序列化可以基于先序，中序，后序和层次遍历的方式来进行。

如果已知中序遍历和先序遍历结果，或者中序和后序遍历结果，我们能够唯一确定一棵二叉树。如果已经先序和后序，则不能。

如果此时有一个需求：判断两棵二叉树，是否相等。我们可以把两个数遍历生成的特征序列进行比较，及中序遍历结果相同，且后序（或先序）遍历结果相同，则这两棵树相同。

另一种方法，就是使用序列化方法。我们使用任意一种遍历方式来遍历二叉树，并比较他们的结果，就可以判断他们是否相等。也就是说，一棵二叉树的任意序列化结果能够得到唯一确定二叉树。

首先，因为最终的序列化结果是字符串，所以，我们必须使用一个符号来表示分隔符，否则，我们无法知道“123”表示的是节点“1” “2” “3”，还是，“12” “3”，“1” “23”，或者“123”一个节点。

比如我们使用字符“!”来进行分隔：这样我们可以清楚的知道“12!3”表示的是：“12” “3”两个节点。

其次我们需要用一个符号来表示空节点，比如“#”，所以如果节点 “3”按照某种遍历后面的节点是空的，我们应该能得到“3!#!”。

下面是按照这种规则做出的实现：

1
2

1
2

1
2

1
2