Reputation: 47
How would one go about adding nodes to a binary tree row by row from an array? It's easy enough when elements are added in their proper position based on a key value of some sort, and I have attempted to assign keys to the values in the array in order to do the row by row adding, but I feel like there must be a more elegant way to do this.
To clarify, what I want is to take an array and convert it into a tree like this
_ _ _ 0 _ _ _
_ 1 _ _ _ 2 _
3 _ 4 _ 5 _ 6
where the numbers represent the indices the values had in the initial array
Upvotes: 1
Views: 831
Reputation: 1440
Notice that the left child of a node with index i has the index 2*i+1 and the right child 2*i+2. Using that, it's very simple:
class Node<T>
{
T val;
Node left = null, right = null;
public void fill(int index, T [] vals)
{
val = vals[index];
if (vals.length > 2*index+1)
{
left = new Node<T>();
left.fill(2*index+1, vals);
}
if (vals.length > 2*index+2)
{
right = new Node<T>();
right.fill(2*index+2, vals);
}
}
}
Start with:
Node<MyValueType> root = new Node<MyValueType>();
root.fill(0, vals);
Replacing MyValueType with whatever is in your array of course.
Upvotes: 2