不完全二叉树作为数组
Incomplete Binary Tree as Array
在大学里，我们被问到如何将不完整的二叉树保存到数组中。
对于顶点的左侧 child 索引为 2i+1，对于顶点的右侧 child 索引为 2i+2。 floor((i − 1)/2) 对于 parent 节点。
现在的第一个问题是我们将如何表示 "missing" 个顶点。
我认为这可以通过将 "null" 保存到数组中来实现。有没有更好的解决方案？
第二个问题我显然不知道该回答什么。有人问为什么实际上没有人会这样做，如果我们从第一个问题开始解决问题，就会出现严重的问题。
感谢您的帮助。
如何表示缺失顶点的答案取决于您的语言。在 Java 中，如果您的数组是对象之一，那么您当然可以使用 null。如果它是一个基元数组，那么您需要某种可以表示 null 的标记值。如前所述，使用数组来表示不完整的二叉树可能会造成浪费，具体取决于树的结构。
第二个问题的答案很可能就是上面的内存问题。话虽如此，还有其他方法可以将不完整的树存储在数组中，这些方法对内存的滥用较少，但比简单的 "left child at 2i+1 and right child at 2i+2" 更复杂。
在大学里，我们被问到如何将不完整的二叉树保存到数组中。 对于顶点的左侧 child 索引为 2i+1，对于顶点的右侧 child 索引为 2i+2。 floor((i − 1)/2) 对于 parent 节点。 现在的第一个问题是我们将如何表示 "missing" 个顶点。
我认为这可以通过将 "null" 保存到数组中来实现。有没有更好的解决方案？
第二个问题我显然不知道该回答什么。有人问为什么实际上没有人会这样做，如果我们从第一个问题开始解决问题，就会出现严重的问题。
感谢您的帮助。
如何表示缺失顶点的答案取决于您的语言。在 Java 中，如果您的数组是对象之一，那么您当然可以使用 null。如果它是一个基元数组，那么您需要某种可以表示 null 的标记值。如前所述，使用数组来表示不完整的二叉树可能会造成浪费，具体取决于树的结构。
第二个问题的答案很可能就是上面的内存问题。话虽如此，还有其他方法可以将不完整的树存储在数组中，这些方法对内存的滥用较少，但比简单的 "left child at 2i+1 and right child at 2i+2" 更复杂。