基于ArrayList的二叉树 - Java

Question

我目前正在实施基于binary tree in Java的ArrayList。我试图弄清楚如何做到这一点，但我正陷入困境。有一堆methods在class我应该实施，但每次我尝试的东西，它似乎并没有工作。我们有Position objectsPosition<E>。在这个class我们有一个array list是private和root variable，既accessible只有这样class，所以size()method和isEmpty()方法很简单。然而，我遇到了一些麻烦，当涉及到实施的方法，如：hasLeft(Position<E>),hasRight(Position<E>)left(Position<E>), right(Position<E>),addRoot(E e)等...左和右方法只是简单地返回left child和right child of a node。我熟悉ArrayList，但在实施binary tree class时并非如此。

我将如何去实施这些方法？我卡住了，我会很感激我能得到的任何帮助。

谢谢！

Answer 1

当您将二叉树编写为数组时，您正在构建通常称为堆的东西。堆是相当有据可查，并且这篇文章会给你很多细节对他们是如何实现的：

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

Answer 2

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

left(i) : 2 * i + 1 
right(i) : 2 * i + 2