• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

recursive method to balance a binary tree

 
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi, my problem:

write a method that recursive balance a binary tree from data held in an array

1. Store element i an array. fixed!
2. Emptry the tree fixed!
3. rebuild the tree recursive

I dont now how to do number 3!?!?!?

I appreciate all the help i can get!

code:

public class Node

public class Node
{
private int data;
private Node left;
private Node right;

public Node(int initialData, Node initialLeft, Node initialRight)
{
data=initialData;
left=initialLeft;
right=initialRight;
}
public int getData()
{
return data;
}

public Node getLeft()
{
return left;
}

public Node getRight()
{
return right;
}
public void setLeft(Node newLeft)
{
left=newLeft;
}

public void setRight(Node newRight)
{
right=newRight;
}
}

/code

public class IntTreeBag

code :

public class IntTreeBag
{
private Node root;

public IntTreeBag()
{
root=null;
}

public void add(Node cursor, int element)
{
if(root==null)
{
root = new Node(element,null,null);
return;
}
if(element==cursor.getData())
{
JOptionPane.showMessageDialog(null, "Datat finns redan i ditt tr�d!");
return;
}
if(element<cursor.getData())
{
if(cursor.getLeft()==null)
{
Node newnode = new Node(element,null,null);
cursor.setLeft(newnode);
}
else
add(cursor.getLeft(),element);
}
if(element>cursor.getData())
{
if(cursor.getRight()==null)
{
Node newnode = new Node(element,null,null);
cursor.setRight(newnode);
}
else
add(cursor.getRight(),element);
}
}
private int howmanyNodes(Node cursor)
{
if (cursor==null)
{
return(0);
}
else
{
return(howmanyNodes(cursor.getLeft()) + 1 +howmanyNodes(cursor.getRight()));
}
}
public int[] toSortedArray()
{
int non = howmanyNodes();
int[] array = new int[non];
Order(getRoot(), array, 0);
return array;
}

private int Order(Node cursor, int[] array, int i)
{
if(cursor != null)
{
i = Order(cursor.getLeft(), array, i);
array[i++] = cursor.getData();
i = Order(cursor.getRight(), array, i);
}
return i;
}
}
/code
 
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
what is the approach and are there any other constraints?

Are you going to add basically one node to the tree at a time and balance each time?

Are you going to add all of the nodes, then balance?

Are you going to load a series of small trees, then thread back to a balanced tree?

Are you going to order the nodes from the array so that the binary tree will be balanced on creation?

Are there any rules as to the delta of branches before a balance is done?
 
tomas fleen
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
all nodes(elements) from the array should be added whit an recursive method that balance at the same time, if it is possible?!?!

middle value from array as root
left part of the array to the left part of the tree
right part of the array to the right part of the tree
 
Steve Fahlbusch
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well you really have your method

 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic