CODEWITHSUNDEEP
javaarraylistbinary-tree
shootingrubber
shootingrubber

Reputation: 145

ArrayList Based Binary Tree - Java

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!

Upvotes: 2

Views: 4997

Answers (2)

leo
leo

Reputation: 1117

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

Upvotes: 0

chubbsondubs
chubbsondubs

Reputation: 38751

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

Upvotes: 2

Related Questions