假设我们要保存一个有 n 个节点的有序树的形状，每个节点最多有 2 个子节点。 如果是二叉树，我们必须使用2n位。由于在我们的情况下，我们没有左 child 或右 child ，它们是相同的，所以我们必须有一些冗余序列。 那么，我们可以用更好的方式对其进行编码吗？看起来每个节点仍然有3种情况，没有子节点、1个子节点、2个子节点，但是我们可以将其存储在少于2位的内存中吗？或者总共有一个比 2 更好的常数？
最佳答案
您也许可以存储您提到的 2n 位，然后使用 huffman coding或其他lossless data compression压缩此数据的技术。
我认为您无法实现更好的最坏情况限制，但在平均情况下 - 它应该为您节省一些空间。
关于algorithm - 如何更有效地将有序树编码为比特序列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9201578/