Results 1 to 2 of 2
  1. #1
    waasp is offline Member
    Join Date
    Mar 2012
    Posts
    1
    Rep Power
    0

    Default 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.");
    */
    }
    }

  2. #2
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default Re: How to balance a random binary search tree with an array (in Java)?

    "Please guys, help me if you're smarter than me and know how can that be achieved!"

    Probably, and the answer is through hard work, reading your textbook, and not doing homework-dumps on web forums. Good luck!

Similar Threads

  1. Binary search tree
    By hansmoolman in forum New To Java
    Replies: 2
    Last Post: 10-28-2010, 01:59 PM
  2. Replies: 0
    Last Post: 04-04-2010, 07:40 AM
  3. Binary search tree search method
    By chopo1980 in forum New To Java
    Replies: 2
    Last Post: 12-10-2009, 01:42 AM
  4. Binary Tree Deletion & Balance Methods
    By sev51 in forum New To Java
    Replies: 1
    Last Post: 01-27-2009, 04:26 PM
  5. Binary Search Tree
    By michael_mke in forum New To Java
    Replies: 3
    Last Post: 12-04-2008, 02:03 AM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •