Building a Tree from array elements
Hello everyone,
I would like to build a tree structure from the elements of a sorted array. If the array is full, then it should split. A parent node is created and the elements of the array are placed in both left and right nodes of the parent.
The middle element of the array becomes the parent node. The elements less than the parent node goes to left array or list and greater than or equal goes to right array or list. Could anyone have an example related to this?
Any ideas will be appreciated.
Thanks
[538 byte] By [
qwedwea] at [2007-10-2 18:20:07]
Here's one way (ignoring the "if the array is full" part):public class TreeBuilder
{
public static void main(String[] args) {
Integer[] sortedElems = new Integer[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
TreeNode<Integer> root = buildTree(0, sortedElems.length, sortedElems);
// Could also use the variable args thing
//TreeNode<Integer> root = buildTree(0, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
}
public static <E> TreeNode<E> buildTree(int startIndex, int endIndex, E... elements) {
if (endIndex - startIndex == 1)
return new TreeNode<E>(elements[startIndex]);
if (endIndex - startIndex == 2)
return new TreeNode<E>(elements[startIndex + 1], new TreeNode<E>(elements[startIndex]), null);
int middle = startIndex/2 + endIndex/2;
TreeNode<E> left = buildTree(startIndex, middle, elements);
TreeNode<E> right = buildTree(middle + 1, endIndex, elements);
return new TreeNode<E>(elements[middle], left, right);
}
}
class TreeNode<E> {
private E element;
private TreeNode<E> left;
private TreeNode<E> right;
public TreeNode(E element) {
this.element = element;
this.left = null;
this.right = null;
}
public TreeNode(E element, TreeNode<E> left, TreeNode<E> right) {
this.element = element;
this.left = left;
this.right = right;
}
public void setLeft(TreeNode<E> left) {this.left = left;}
public void setRight(TreeNode<E> right) {this.right = right;}
public E getElement() {return element;}
public TreeNode<E> getLeft() {return left;}
public TreeNode<E> getRight() {return right;}
}
Will produce a tree that looks like this:
__5__
/\
28
/ \/ \
1479
///
036
dwga at 2007-7-13 19:40:37 >
This is a bit cleaner and reduces the possibility of programmer error:public class TreeBuilder
{
public static void main(String[] args) {
TreeNode<Integer> root = buildTree(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
}
public static <E> TreeNode<E> buildTree(E... elements) {
return buildTree(0, elements.length, elements);
}
private static <E> TreeNode<E> buildTree(int startIndex, int endIndex, E... elements) {
if (endIndex - startIndex == 1)
return new TreeNode<E>(elements[startIndex]);
if (endIndex - startIndex == 2)
return new TreeNode<E>(elements[startIndex + 1], new TreeNode<E>(elements[startIndex]), null);
int middle = startIndex/2 + endIndex/2;
TreeNode<E> left = buildTree(startIndex, middle, elements);
TreeNode<E> right = buildTree(middle + 1, endIndex, elements);
return new TreeNode<E>(elements[middle], left, right);
}
}
dwga at 2007-7-13 19:40:37 >
Do you mean:buildTree(new Integer[] {1, 2, 3, 4});
orbuildTree(new Integer[][] {{1,2},{3,4}});
?
The first one will produce a tree like before.
The second one will produce a tree like this:
{3,4}
/
{1,2}
dwga at 2007-7-13 19:40:37 >
