Home arrow static arrow Java Programming [Archive] - Need help build binary tree from array
Warning: Creating default object from empty value in /www/htdocs/w008deb8/wiki/components/com_staticxt/staticxt.php on line 51
Java Programming [Archive] - Need help build binary tree from array
This topic has 8 replies on 1 page.

Posts:5
Registered: 8/4/04
Need help build binary tree from array  
Aug 4, 2004 2:58 AM



 
Hello!
My first post here so forgive me if i post in the wrong forum...

I have search on google and in here but i can't find any good explanation (at least for me to understand) how to build a balanced binary tree from a sorted array.

Let say i have a array like:
1,3,5,7,10,12,14,16,18

Now i want to build a balance binary tree from this array:
             10            /    \         5         14       /   \     /    \     3       7 12       16    /                     \   1                       18

What i know i have to set the root node to the one in the middle from the array (10) and then build left side from the array to left side in the tree and right to right.

Let say i insert and remove nodes in a tree and after that I want to rebuild the tree to make it balanced. To do that i put all nodes in a sorted array as the code below, this works fine but now i'm stuck. How can I develop this method to rebuild the tree from the array i just have created (recursive)?

public void rebuild(Node a){if (pos==0)//Make arrayarr=new int[countNodes(myTree)];if(a.left != null) {rebuild(a.left);  }arr[pos] = a.content;  pos++;  if(a.right != null) {  rebuild(a.right);  }


Thanks!
 

Posts:5,965
Registered: 5/17/03
Re: Need help build binary tree from array  
Aug 4, 2004 3:42 AM (reply 1 of 8)



 
how to build a balanced binary tree from a sorted array.

Normally the insert and delete methods are enhanced so they keep the tree balanced at all times. There are algoritms availible for that.

Anyway say you have a sorted array and want to build a balanced tree from it.

What i know i have to set the root node to the one in
the middle from the array (10) and then build left
side from the array to left side in the tree and right
to right.

What you indicate here is actually the beginning of a recursive "divide-and conquer" formulation (I use sequence instead of array):

1. Split the sequence in the middle and create a node using the middle element.
2. Do step one with both the sequence to the left and to the right of the middle element. Stop if a sequence is empty.

You don't actually have to split arrays. You can work with left and right array indexes.

It's possible to write a recursive balanced tree builder from that formulation I think (but I've never tried -:)
 

Posts:5,965
Registered: 5/17/03
Re: Need help build binary tree from array  
Aug 4, 2004 4:25 AM (reply 2 of 8)



 
Something like this (not tested),
int[] arr = new int[10];//class Node {   int element;   Node left, right;}//Node builder(int l, int r) { // subsequence (left/right index)   Node p = null;   if (l <= r) { // sequence is not empty      p = new Node(); // new node      int m = (l+r)/2; // index of middle element      p.element = arr[m]; // middle element      p.left = builder(l, m-1); // build left subtree      p.right = builder(m+1, r); // build right subtree   }   return p; // null if leaf, otherwise pointer of subtree}//Node root = builder(0,arr.length-1);
 

Posts:196
Registered: 6/24/97
Re: Need help build binary tree from array  
Aug 4, 2004 4:43 AM (reply 3 of 8)



 
public class TreeNode {  // the right and left nodes of the tree  TreeNode left, right;   // the value of the node itself  Object value;   // the constructor expects a sorted array of Comparable objects  public TreeNode ( Comparable[] elements) {    // find the middle element    int length = elements.length;              // eg odd = 9, even = 10    int middle = length /2;                         // eg for odd  = 4 --> 0-3 on left 5-8 on right                                                                // for even = 5 ---> 0-4 on left 6-9 on right                   // setup the value of the curent node    this.value = elements[middle];      // calculate the left elements    int firstLeft = 0;    int lastLeft = middle - 1;    if ( lastLeft >0) {   // check that there is something on the left      Comparable leftElements = subArray (elements, firstLeft,lastLeft);   // left 2 u 2 implement      this.left = leftElements;    }     // calculate the right elements    int firstRight = middle;    int lastRight = elements.length -1;    if (( firstRight > 0)  && (lastRight >0))  {             // check that there is something on teh right      Comparable rightElements = subArray( elements, firstRight, lastRight);      this.right = rightElements;    }  }   public static void main(String args[]) {    String[] elements = { "a", "b", "c", "d", "e", "f", "g" };    TreeNode root = new TreeNode(elements);  }} 


Not checked if it compiles or works

Not checked if it compiles or works
 

Posts:5
Registered: 8/4/04
Re: Need help build binary tree from array  
Aug 4, 2004 6:18 AM (reply 4 of 8)



 
Thanks to both of you but especially to UlrikaJ because that worked like a dream ;)

Thanks again!
 

Posts:5,965
Registered: 5/17/03
Re: Need help build binary tree from array  
Aug 4, 2004 6:41 AM (reply 5 of 8)



 
Thanks. -:)

You see that my solution creates new nodes, but this isn't necessary. If you store the nodes in the array instead of the elements, you can modify builder to reuse the old nodes. You just use the Node at index m like, p = arr[m]; instead of creating a new one.

Also instead of hardcoding arr in builder you could pass the array as the first parameter to make it more general.
 

Posts:196
Registered: 6/24/97
Re: Need help build binary tree from array  
Aug 4, 2004 6:49 AM (reply 6 of 8)



 
Yuck!! I didn't see Ulrika's code before posting mine.

Good one Ulrika.
 

Posts:10,967
Registered: 4/7/01
Re: Need help build binary tree from array  
Aug 4, 2004 4:26 PM (reply 7 of 8)



 
This may be of interest - It takes an unsorted int array and loads a Red-Black tree (TreeSet). The additional Collections functions that become available can be useful.
int[] ar = {5, 16, 3, 1, 14, 7, 10, 18, 12};  // Not sorted Object newInt[] = new Object[ar.length]; for (int i = 0; i < ar.length; i++){    newInt[i] = new Integer(ar[i]);}  Set st = new TreeSet(Arrays.asList(newInt));
 

Posts:5,965
Registered: 5/17/03
Re: Need help build binary tree from array  
Aug 4, 2004 10:40 PM (reply 8 of 8)



 
This may be of interest - It takes an unsorted int
array and loads a Red-Black tree (TreeSet).

A ready made collection is always to prefer but how do you know a TreeSet is implemented using a Red-Black tree? It may be now but this is not in the class contract so there's no guarantee.
 
This topic has 8 replies on 1 page.