问面试问题-序列化和反序列化n元树

EN

在我看来，递归是一个很好的用法。编写一个方法(子例程，函数)，写出一个节点和它下面的所有树。它将写出节点，然后写出子节点的数量(叶节点为零)，然后调用自身写入每个子节点(如果有)。现在调用树中顶部节点上的方法，您已经序列化了它。

要进行反序列化，请编写一个读入节点的方法。它将读入节点本身，读入子节点的数量，然后读入每个子节点。在流上调用它一次，它将传递给您包含所有后代节点的顶级节点-整个树。

这个故事的寓意是，递归(实际上只是获取和使用堆栈的一种方便方法)对于处理图形非常有用。比你想象的要多得多的东西都是图。

需要区分两种情况: 1.稀疏n元树和2. 稀疏n元树。在第一种情况下，假设N=5，所以树中的每个级别i将恰好(即不少于，不超过) 5^i个节点；另一方面，在第二种情况下，这个规则是无效的，因为树可以通过构造随机填充。

完整的n元树可以序列化为一个数组；简单地从完整的二叉树扩展:节点(中间和叶子)通过论坛N_i+1+c*的第i级和实际的N相互关联，其中_c是第c个子节点。采用层序遍历，树可以在字节数组中进行优化序列化(不需要更多字符，下文将读取)。Here上有一个全面的解释。

不幸的是，对于非完全n元树，正如预期的那样，上述公式不适用。因此，需要采用不同的方法。一种方法是序列化特殊字符，以指示子代的缺失，或者更好地序列化子代指针的空值。这种方法不是最优的，因为需要更多的字符(总共需要N个额外的字节)，但它是一个非常简单和可行的方法。让我们来看一个例子：

       A
     / | \ 
    B  C  D
   / \     \
  E   F     G

采用预排序遍历，将上述非完全n-ary树序列化如下

 A B E / F / / C / D G / / /

'/‘映射NULL并提供将树反序列化为原始树的能力。采用预排序遍历的方式访问树并输出上述字符数组。总共序列化了*2*N*个字节，因为在这种情况下，每个树值恰好是1个字符。作为反序列化算法，仍然可以采用前序遍历:只需很少的修改就可以识别空值映射模式，如上所述。here是一个C++代码示例。

总结，序列化和反序列化一个非完整或稀疏的n元树有点棘手，需要更多的字节来强制映射NULL。

实际上，维基百科帮助我找到了解决方案。我能够将n元树存储到数组中，并转换为byte[]，然后使用下面的公式将byte[]转换回数组。第c个子元素位于索引k*i +1+c父元素位于索引i -1/2