序列化和反序列化二叉树

数据结构也必须能够被转换成可以存储并随后重建的格式。通过序列化过程，数据结构被转换成一系列位。从序列化序列重建数据结构的过程称为反序列化。

为了创建有效的软件，数据结构至关重要，我们经常需要交换它们。考虑共享一个二叉树；如果是进程间交互，可以直接交换树的根节点。但如果我们需要在网络上传输它，这是行不通的。我们可以通过序列化将数据结构转换为序列，以便通过网络传输或存储在内存缓冲区中。然后，在稍后进行反序列化以重建数据结构。

让我们看一个二叉树的序列化和反序列化示例。

一种简单的实现方法是跟踪两个树的遍历，并使用这两个遍历序列从头开始重建树。此外，为了序列化树并使用单个树遍历（前序或后序）恢复它，还需要保存空节点。

在深入探讨二叉树序列化和反序列化的理论和实现之前，让我们先分别研究如何序列化一棵树以及反序列化一棵树的过程。

二叉树序列化

通过以特定顺序遍历二叉树并保存相关序列，可以将其序列化。目标是能够从序列中重建树，并将树节点存档到序列中（以便能够序列化和反序列化二叉树）。现在，这可以通过以特定方式遍历树来实现，以便在反序列化时可以采用相同的方法。

前序、中序、后序以及其他类型的遍历是一些示例。

第一种技术：前序遍历

为了在重建树时识别空节点，概念是执行树的前序遍历并将空值保存为整数最小值。

前序遍历算法如下：

• 创建一个空的 ArrayList 并用序列填充它。
• 前序递归遍历树（当前、左、右）。
• 如果当前节点不为空，则添加一个最小整数值；否则，添加当前节点的值。

实施

以下是用 C++ 序列化二叉树的前序遍历实现：

C++代码

输出

Preorderseries follows as 
1 2 4 -2147483648 -2147483648 -2147483648 3 5 -2147483648 -2147483648 -2147483648

时间复杂度

此方法遍历树，并将每个节点附加到数组。时间复杂度为 **O(N)。**

空间复杂度

此方法维护大小为 H 的内部递归堆栈，并需要一个数组来存储序列化序列（二叉树的高度）。因此，空间复杂度为 **O(H+N)，** 其中

第二种技术：后序遍历

为了在重建树时识别空节点，概念是执行树的后序遍历并将空值保存为整数最小值。

后序遍历算法如下：

• 创建一个空的 ArrayList 并用序列填充它。
• 递归地以后序遍历树（左、右、当前）。
• 如果当前节点不为空，则添加一个最小整数值；否则，添加当前节点的值。

实施

以下是用 C++ 实现序列化二叉树的后序遍历：

C++ 程序

输出

Postorderseries follows as 
-2147483648 -2147483648 4 -2147483648 2 -2147483648 -2147483648 5 -2147483648 3 1

时间复杂度

此方法遍历树，并将每个节点附加到数组。时间复杂度为 **O(N)。**

空间复杂度

此方法维护大小为 H 的内部递归堆栈，并需要一个数组来存储序列化序列（二叉树的高度）。因此，空间复杂度为 **O(H+N)，** 其中

二叉树反序列化

序列化完成后，我们将获得一个序列化序列，必须从中重建原始树。如前所述，我们应该使用与序列化树时相同的遍历策略（以便能够序列化和反序列化二叉树）。通过这样做，反序列化方法能够保持原始树的状态。

第一种技术：前序遍历

目标是在遍历指定序列时，继续以正确的前序将节点添加到树中。请记住，指定序列必须等于原始树的前序遍历。否则，前序反序列化将无法重建原始树。

以下是前序遍历序列的反序列化过程。

• 从序列的开头开始。
• 创建一个包含序列当前值的节点。
• 递归地将剩余序列传递给当前节点的左子节点。
• 然后递归地将剩余序列传递给当前序列的右子节点。
• 如果序列中包含整数最小值，则在当前节点处将 null 添加到树中。

C++ 实现用于反序列化二叉树的前序遍历序列如下：

C++ 程序

输出

inorder traversal of deserialized tree follows as
4 2 1 5 3

时间复杂度

此方法遍历整个序列并为每个值生成一个新节点。由于 N 是序列的长度，因此时间复杂度为 **O(N)。**

空间复杂度

但是，此方法有效地维护了一个大小为 O(H) 的递归堆栈（其中 H 是二叉树的高度），而无需任何额外的空间。

第二种技术：后序遍历

反序列化后序遍历序列的预期过程是先构建左子节点，然后构建右子节点，最后构建当前节点。但是，如果没有先构建当前节点，我们就无法访问子节点。因此，我们向后遍历序列，遵循当前、右、左的方向。

请记住，指定序列必须等于原始树的前序遍历。否则，前序反序列化将无法重建原始树。

以下是后序遍历序列的反序列化过程。

• 从末尾开始，遍历序列。
• 创建一个包含序列当前值的节点。
• 递归地将后续序列传递给当前节点的右子节点。
• 然后将剩余序列传递给当前节点的左子节点。
• 如果序列中包含整数最小值，则在当前节点处将 null 添加到树中。

实施

以下是用 C++ 实现后序遍历序列的二叉树反序列化：

C++ 程序

输出

inorder traversal of deserialized tree follows as
4 2 1 5 3

时间复杂度

此方法遍历整个序列并为每个值生成一个新节点。由于 N 是序列的长度，因此时间复杂度为 **O(N)。**

空间复杂度

但是，此方法有效地维护了一个大小为 **O(H)** 的递归堆栈（其中 H 是二叉树的高度），而无需任何额外的空间。

序列化和反序列化的好处

• 借助序列化，数据结构可以轻松地通过网络传输或存储在内存缓冲区中。
• 序列化也用于对象和数据结构，许多 ORM 框架（如 Hibernate）都采用了这种技术。
• 序列化能够将数据结构存储到内存缓冲区中，从而可以降低平均访问时间。
• 反序列化使得确定数据结构的原始状态成为可能。
• 在这种情况下，反序列化一个对象比创建一个全新的对象要快得多。
• 这个序列化和反序列化的循环经常在分布式系统中用于在节点之间分配数据。

结论

让我们回顾一下序列化和反序列化二叉树的步骤。

• 通过序列化过程，数据结构被转换成一系列位。
• 从序列化序列重建数据结构的过程称为反序列化。
• 通过保存一个标记来表示空节点，并保存树的前序或后序遍历序列，可以序列化二叉树。
• 当从给定序列反序列化二叉树时，使用适当的遍历策略来重建树。
• 序列化和反序列化在文件存储、ORM 框架和分布式系统中都有应用。