基於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