基于ArrayList的二叉树Java

Question

我目前正在实施基于ArrayList的binary tree in Java。我试图弄明白这是怎么做到的，但我遇到了麻烦。在我应该实现的class中有很多methods，但是每次我尝试一些东西，它似乎都不起作用

我们有Position objects被Position<E>识别。在这个class中，我们有一个array list即private，和一个root variable，这两个accessible都只通过这个class，所以size(){}和isEmpty()方法很简单。然而，在实现这些方法时，我遇到了一些麻烦，比如：hasLeft(Position<E>)，hasRight(Position<E>)left(Position<E>), right(Position<E>),addRoot(E e)，等等。。。Left和Right方法只返回left child和right child of a node。我对ArrayList很熟悉，但在用它们实现binary tree class时就不熟悉了

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

谢谢

Answer 1

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

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