algorithm - 如何更有效地将有序树编码为位序列

Question

假设我们要保存一个有n个节点的有序树的形状，每个节点最多有2个子节点。如果是二叉树，我们必须使用2n位。由于在我们的情况下，我们没有左 child 或右 child ，它们是相同的，所以我们必须有一些冗余序列。那么，我们可以用更好的方式对其进行编码吗？貌似每个节点还有3个case，没有 child ，有一个 child ，有两个 child ，但是能不能用不到2位存储呢？或者总的来说有一个比 2 更好的常数？

Answer 1

您可以像您提到的那样存储 2n 位，然后使用 huffman coding或其他lossless data compression压缩此数据的技术。

我不认为你可以达到更好的最坏情况限制，但在平均情况下 - 它应该为你节省一些空间。