algorithm - 使用中序遍历的二叉树序列化和反序列化

Question

以下是geeksforgeeks的摘录

如果给定的二叉树是二叉搜索树，我们可以通过存储前序或后序遍历来存储它。在二叉搜索树的情况下，仅前序或后序遍历就足以存储结构信息。

问题

1. 二叉树的序列化和反序列化不能使用有序遍历吗？如果是，为什么？
2. 二叉树和 BST 序列化有什么区别？上述说法并不清楚这种区别

标签： algorithmserializationdeserializationb-tree

Answer 1

BST 的按顺序遍历会生成排序的数据列表，而不管树的外观如何。

相反，给定一个通过前序遍历产生的列表，可以重构 BST：

• 第一个元素是根。

• 按根的值拆分其余部分。BST的S保证分裂点存在，第一/第二切片分别包含左/右子树。

• 递归地将该过程应用于第一个和第二个切片。

这个过程在很大程度上依赖于 BST 的S属性。任意二叉树没有分裂点。