堆与二叉树 - 如何实现？

Question

在实现堆结构时,我们可以将数据存储在一个数组中,使得位置i的节点的子节点位于位置2i和2i + 1.

我的问题是,为什么我们不使用数组来表示二进制搜索树,而是处理指针等？

谢谢

Answer 1

如果所有子节点的位置都是静态预先计算的,那么数组本质上代表一个完全完整,完全平衡的二叉树.

并非所有"真实生活"中的二叉树都完全饱满且完美平衡.如果你碰巧有一些特别长的分支,你必须使你的整个阵列更大,以适应最底层的所有节点.

• 如果数组绑定的二叉树基本上是空的,则大部分数组空间都被浪费了.

• 如果树的一些分支足够深,可以到达阵列的"底部",那么浪费的空间也很大.

• 如果树(或仅一个分支)需要比数组允许的"更深"增长,则需要"增长"数组,这通常实现为复制到更大的数组.这是一项耗时的操作.

所以:使用指针可以让我们动态灵活地扩展结构.在数组中表示树是一个很好的学术练习,适用于小而简单的情况但通常不能满足"真实"计算的要求.

Answer 2

亲身

1. 因为使用指针更容易动态增长数据结构大小

2. 我发现维护bin树比堆更容易

3. 平衡,移除,插入树中的元素的算法将仅改变指针,而不是像在矢量中那样物理移动.

等等...

Answer 3

主要是因为递归树允许非常简单的代码.如果将树展平为数组,则代码变得非常复杂,因为您必须执行大量的簿记,递归算法会为您执行此操作.

此外,高度为N的树可以在N和2^(N+1)-1节点之间具有任何内容(.只有实际节点需要内存.如果使用数组,则必须始终为所有节点(即使是空节点)分配空间,除非使用稀疏数组(这会使代码更复杂.)因此,虽然很容易在内存中保留高度为100的稀疏树,但找到一台可以分配20282409603651670423947251286008字节RAM的计算机会有问题.

Answer 4

据我所知，我们可以使用Array来表示二叉搜索树。但使用指针更加灵活。