binary-tree - 二叉树、数组与链接

Question

通常，基于二叉树的抽象可以使用实际链接的节点对象来实现，其中每个节点都有指向它的两个子节点的指针，或者一个数组，其中索引 k 中节点的子节点是 2k 和 2k+1。

除了节点的少量额外内存开销外，总体上的复杂性似乎是相同的。

一个比另一个有什么具体的优势吗？有趣的是，我已经看到二叉堆倾向于使用数组实现，而二叉搜索树倾向于使用链接节点实现。这有什么原因吗？

Answer 1

数组不能有效地表示任意形状的二叉树，只能表示完整的树。一棵完全二叉树是所有层都是满的，或者除了最深层之外的所有层都是满的，并且最深层的所有节点都尽可能向左。 (您可以想象这些级别从左到右填充了节点，并且必须先填充一个级别，然后才能开始下一个级别。)

根据定义，堆是完整的二叉树——因此使用数组实现是由于其卓越的内存效率。另一方面，必须支持在任意位置插入和删除的二叉搜索树(因此可能不是完整的树)不能使用数组实现。