2

我目前正在实施ArrayList基于binary tree in Java. 我试图弄清楚如何做到这一点，但我遇到了墙。有一堆methods我class应该实现的，但是每次我尝试一些东西时，它似乎都不起作用。

我们有Position objects由 标识的Position<E>。在 this中，class我们有一个array listthat isprivate和 a root variable，两者都accessible只有 this class，所以 thesize() method和isEmpty()方法很简单。但是，在实现以下方法时遇到了一些麻烦：hasLeft(Position<E>),hasRight(Position<E>) left(Position<E>), right(Position<E>), addRoot(E e)等... Left 和 Right 方法只返回left childand right child of a node。我熟悉ArrayList，但在binary tree class与他们一起实施 a 时并不熟悉。

我将如何实施这些方法？我被困住了，如果能得到任何帮助，我将不胜感激。

谢谢！

4

2 回答 2

2

当您将二叉树编写为数组时，您正在构建通常称为堆的东西。堆有很好的文档记录，本文将为您详细介绍它们是如何实现的：

http://en.wikipedia.org/wiki/Binary_heap

于 2012-10-17T02:16:44.340 回答
0

您可以在连续数组的顶部构建二叉树。基本上，对于数组第 i 个位置的元素，具有基于 0 的索引：

left(i) : 2 * i + 1
right(i) : 2 * i + 2
于 2012-10-17T02:27:59.680 回答