为什么我们将树表示为由指针链接的单元，而不是将所有内容存储在平面数组中？

Question

为什么我们使用指针、结构体和所有这些东西来构建树，为什么不只使用数组呢？这是由于数组的限制，还是使用指针等提供了比数组更好的性能？

Answer 1

有时我们确实会使用数组。例如，它很容易成为表示二叉堆下的树的最常见方式。然而，它并不适合大多数树木。

如果您使用类似于 的关系从父索引计算子索引childindexes(i) = {2*i+1, 2*i+2}（如通常的堆表示形式），则数组的大小必须与树的深度而不是元素的数量成比例。当树非常平衡时（就像通常的二进制堆表示一样），这很好，但是对于像红黑树这样的树来说，它会浪费大量空间，红黑树是自平衡的，但不是那么平衡。此外，诸如树旋转和其他树结构重新链接之类的内容需要移动整个子树，而不是更改一些指针。

另一方面，如果每个节点都必须存储其子节点所在的数组索引，那么您基本上只是重新实现指针和内存管理，并且您需要一个非常好的、具体的理由来做到这一点，而不是仅仅使用什么你的语言提供。