在序列化 BST 时，为什么有序是必不可少的？

Question

我了解到，为了在序列化时保留 BST 的结构，需要按顺序存储树的前序或后序符号之一。

是什么使有序表示法必不可少？

Answer 1

注：重写答案，之前的版本有误。

对于一般二叉树（具有唯一元素），您的陈述是正确的。考虑这两个输入（画得不是很漂亮;-)）：

如果您使用按序遍历来序列化它们，则两者都会产生ABC. 其他遍历类型也存在类似的情况。

那么，为什么将订购和预购结合起来就足够了？

预购的序列化形状是[root][left subtree][right subtree]。根很容易识别，但你不知道左子树在哪里结束，右子树在哪里开始。

现在考虑按顺序序列化：[left subtree][root][right subtree]. 你知道根是什么（多亏了预购），所以识别左右子树真的很容易。

请注意，如果权重不是唯一的，这仍然不够。如果在上面的示例中我们更改B为A，则两种树都会[AAC]对两种遍历类型产生收益。

对于二叉搜索树，反序列化要容易得多。为什么？好吧，每个子树都有这样的特性，即左子树中的节点小于根，而右子树中的节点更大。因此，[root][left subtree][right subtree]可以轻松且明确地再次解析前序序列化。所以，总而言之，那个告诉你 BST 至少需要两种序列化方法的人是错误的（也许他也忘记了 BST 的属性）。