ArrayList Based Binary Tree - Java

Question

I am currently in the process of implementing an ArrayList based binary tree in Java. I am trying to figure out how this would be done, but I am running into a wall. There are a bunch of methods in a class I am supposed to implement, but each time I try something, it doesn't seem to work.

We have Position objects that are identified by Position<E>. In this class we have an array list that is private, and a root variable, both accessible only by this class, so the size() method, and the isEmpty() methods are simple. However, I am running into some trouble when it comes to implementing the methods such as: hasLeft(Position<E>), hasRight(Position<E>) left(Position<E>), right(Position<E>), addRoot(E e), etc... The Left and Right methods simply return the left child and right child of a node. I am familiar with ArrayList, but not when it comes to implementing a binary tree class with them.

How would I go about implementing these methods? I am stuck, and I would appreciate any help I can get.

Thanks!

Could you show the interface you are supposed to implement? — Pao
– Pao, Commented Oct 16, 2012 at 23:56

chubbsondubs · Accepted Answer · 2012-10-17 02:16:44Z

2

When you write binary trees as an Array you are building what's typically called a heap. Heaps are fairly well documented and this article will give you lots of detail about how they are implemented:

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

answered Oct 17, 2012 at 2:16

chubbsondubs

39.4k25 gold badges110 silver badges143 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

leo · Accepted Answer · 2012-10-17 02:27:59Z

0

You can build a binary tree on the top of a contiguous array. Basically, having a 0 based index, for an element on the i th position of the array:

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

answered Oct 17, 2012 at 2:27

leo

1,1171 gold badge8 silver badges18 bronze badges

Collectives™ on Stack Overflow

ArrayList Based Binary Tree - Java

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related