Python中二叉树的序列化和反序列化

序列化是指当我们必须将树数据结构存储在文件中时所使用的过程。之后，我们可以根据需要恢复此树。唯一的条件是必须保持树的结构。反序列化是序列化的完全相反的过程。当我们必须从文件中恢复树时使用它。

根据树的类型，可以更改序列化过程以简化该过程。

例如，如果二叉树是二叉搜索树，那么我们可以使用[前序遍历和后序遍历来存储二叉搜索树。我们可以使用前序或后序遍历来检索二叉搜索树的完整结构。

然而，如果给定的二叉树是完全二叉树，我们可以使用层序遍历来获取树的结构。在完全二叉树中，所有层都已完全填充，确保层序遍历是完整的，并且不会有任何空节点。我们知道第一个节点将是根节点，然后接下来的节点将是下一个级别的节点。由于条件在于完全二叉树中的级别，因此层序遍历是最合适的。

如果给定的二叉树是满二叉树，则只需前序遍历。满二叉树是指每个节点恰好有 2 个子节点的树。我们可以跟踪节点是内部节点还是叶节点。

我们通常需要前序和中序遍历来构造完整的通用二叉树。但是，我们可以节省空间，只存储前序遍历。为了进行遍历，我们需要知道哪里有空节点。为了达到此目的，我们可以使用#。

因此，我们将首先存储所有带有所有子节点的节点。对于空节点，我们将使用#。最后，我们将此遍历保存在文件中。

代码

输出

Serialized tree:
2,18,14,#,#,1,12,#,#,4,#,#,20,#,#

Inorder traversal of the deserialized tree:
14 18 12 1 4 2 20

上述解决方案还需要多少额外空间？

在键很大或与之对应的数据项很大的情况下，以下技术（需要 n+1 个标记，其中 n 是键的数量）可能比存储键两次的简单选项更可取。

我们还能做些什么来优化它吗？

有许多方法可以优化上述答案。更详细地检查上面的序列化树会发现每个叶节点都需要两个标记。添加一个不同的位到每个节点以指示它是内部节点还是外部节点是一种简单的优化方法。

这样，由于可以通过附加位区分叶节点，因此我们可以避免为每个叶节点存储两个标记。

对于只有一个子节点的内部节点，仍然需要一个标记。

例如，在下图中，符号'表示一个内部节点设置位，而字母 '/' 表示一个 NULL 标记。

代码

输出

The deserialized N-Ary tree from file is
1 2 5 6 1 1 3 4 7 8 9 1 0

时间复杂度：此程序的 time complexity 为 O(N)，其中 n 是节点数。

辅助空间：此程序的 space complexity 为 O(H + N)。