Results 1 to 2 of 2
- 03-21-2012, 02:55 PM #1
Member
- Join Date
- Mar 2012
- Posts
- 1
- Rep Power
- 0
How to balance a random binary search tree with an array (in Java)?
Hi,
I got the following assignment - I have a certain java code for a binary search tree and I need to add methods to do the following things with it:
1. Transform the BST into an array that's sorted by BST data keys.
2. Create a balanced BST from an ordered integer array.
3. Use 1. and 2. to balance an existing BST (randomly generated and presumably somewhat unbalanced)
4. Display the BST before and after balancing.
Please guys, help me if you're smarter than me and know how can that be achieved!
Here is the code that I need to work with:
import java.util.*;
class BtreeNode {
int data;
BtreeNode L,R;
static int depth=0;
public BtreeNode(){
data = 0; L = null; R=null;
}
public BtreeNode(int key){
this();data = key;
}
public String toString() {
return "["+data+"]";
}
public static BtreeNode insOrd(BtreeNode roo, int key){
if(roo==null)return new BtreeNode(key);
//Не се допуска повторение на ключове
if(key==roo.data)return roo;
if(key<roo.data)roo.L=insOrd(roo.L,key);
else roo.R=insOrd(roo.R,key);
return roo;
}
public static BtreeNode generate(int length) {
BtreeNode start = null;
Random rn = new Random();
for(int i = 0; i < length; i++){
start = insOrd(start,rn.nextInt(10000));
}
return start;
}
public static void spc(int n){
for(int i=0;i<n;i++)System.out.print(" ");
}
public static void print(BtreeNode roo){
if(roo!=null){
depth++;
print(roo.R);
spc(depth);System.out.println(roo);
print(roo.L);
depth--;
}
}
public static BtreeNode find(BtreeNode roo, int key){
BtreeNode r=null;
if(roo==null)return r;
if(roo.data==key)r= roo;
if(key>roo.data)r= find(roo.R,key);
if(key<roo.data)r= find(roo.L,key);
return r;
}
};
public class Main {
public static void main(String[] args){
int N;
Scanner sc = new Scanner(System.in);
System.out.print("Enter the number if tree items:");
N=sc.nextInt();
BtreeNode c = BtreeNode.generate(N);
BtreeNode.print(c);
/*
System.out.println("This tree has "+
BtreeNode.weight(c)+" nodes and "+
BtreeNode.height(c)+" levels.");
*/
}
}
- 03-23-2012, 06:51 PM #2
Similar Threads
-
Binary search tree
By hansmoolman in forum New To JavaReplies: 2Last Post: 10-28-2010, 02:59 PM -
Data Structures(Binary Search Tree to AVL Tree)ASAP pls
By jfAdik in forum Forum LobbyReplies: 0Last Post: 04-04-2010, 08:40 AM -
Binary search tree search method
By chopo1980 in forum New To JavaReplies: 2Last Post: 12-10-2009, 02:42 AM -
Binary Tree Deletion & Balance Methods
By sev51 in forum New To JavaReplies: 1Last Post: 01-27-2009, 05:26 PM -
Binary Search Tree
By michael_mke in forum New To JavaReplies: 3Last Post: 12-04-2008, 03:03 AM
Bookmarks