Results 1 to 5 of 5
  1. #1
    xajaxworldx is offline Member
    Join Date
    May 2011
    Posts
    5
    Rep Power
    0

    Unhappy HELP me with Binary Search Tree. hard time on it.

    Java Code:
    In this project you will implement a binary search tree (BST) with the following generic skeleton:
    class BST<T extends Comparable<T>> {
    class Node<T>
    private Node<T> root;
    }
    The Comparable interface is a simple interface from java.lang that introduces only one method:
    interface Comparable<T> {
    int compareTo(T v);
    }
    In the same way that class Object introduces important basic method signatures such as equals() and toString() that
    all classes are expected to follow, the Comparable interface should be implemented by any class whose object
    values can be placed into an order. Clearly, this is an important interface for classes such as String and Integer, but
    not for classes such as Scanner or Random. As with any interface, the class that implements it is given only a
    method signature, and the implementer is free to implement in any appropriate way. In more detail, the
    compareTo() method should work as follows:
    T a, b;
    int value = a.compareTo(b)
    // value < 0 implies “a before b”
    // value == 0 implies “a equivalent to b”
    // value > 0 implies “a after b”
    In the rules for generic type parameters, a definition such as
    class BST<T> { }
    would allow a BST to be created around any class T, even a class for which there is no meaningful comparison of
    values defined. The type parameter can therefore be restricted to only those types that implement the Comparable
    interface. The definition then becomes
    class BST<T extends Comparable> { }
    Note that the keyword “extends” is used in the context of defining generic type parameters, even though
    Comparable is an interface that would use the “implements” keyword in other contexts.
    But since Comparable is also generic, it needs the same type parameter T.
    class BST<T extends Comparable<T>>
    This last definition is sufficient for the current lab. You may see an even more general version in some code as
    follows:
    class BST<T extends Comparable<? super T>>
    The syntax <? super T> is generic programming notation for “any class that is a superclass of T”. The “?” is a
    called a wild card.
    In summary, the extra constraint on T ensures that when a BST is created later from the driver, only base types that
    implement the compareTo() function can be used.
    BST<String> tree1 = new BST<String>(); // okay
    BST<Integer> tree2 = new BST<Integer>(); // okay
    BST<Scanner> tree3 = new BST<Scanner>(); // ?
    The following methods will be implemented:
    public void insert(T value) { }
    public void delete(T value) { }
    public static void generate(BST<Integer> tree, int n, int range) { }
    public String toString() { }
    In pseudo code, here are algorithms for insert(), delete(), and toString():
    insert(T v):
    Node n = new node to hold v
    if root==null then root = n
    else
    // create a temporary to keep track of the current node in the tree being examined
    Node m = root
    // let m descend into the tree until an empty pointer is located on the correct side of the node
    while (v < m.value AND m.left not null) OR (v >= m.value AND m.right not null)
    if v < m.value m = m.left
    else m = m.right
    end while
    // loop has ended but need to see if new node belongs on left or right of m
    if v < m.value then m.left = n
    else m.right = n
    end else
    delete(T v):
    if root==null then do nothing, nothing to delete
    else
    // find the node to delete
    Node p = null
    Node m = root
    // loop until either we find a node with value v or we run off the bottom of the tree
    while m!=null AND m.value !=v
    p = m
    if v<m.value then m = m.left
    else m = m.right
    end while
    // loop has ended, need to find out why
    if m==null then v not found, done, nothing to do
    else
    // delete m, what to do depends on how many child nodes m has
    if m has zero child nodes then
    // 2 subcases
    // m==p.left
    // m==p.right
    …
    if m has one child then
    // 4 subcases
    // m==p.left and m.left not null
    // m==p.left and m.right not null
    // m==p.right and m.left not null
    // m==p.right and m.right not null
    …
    else // m has 2 child nodes
    // don’t delete m directly, find inorder successor, delete it, preserve value in m
    q = inorder successor of m
    int temp = q.value
    delete q
    m.value = temp
    end else
    end else
    toString():
    based on inorder traversal
    public String toString() {
    return toString(root);
    }
    private String toString(Node<T> n) {
    if n is null return “”;
    else return toString(n.left) + “ ” + n.value + “ ” + toString(n.right);
    }
    Displaying BSTs Graphically
    Since trees are not linear structures like one-dimensional arrays and linked list, they are harder to visualize without a
    graphical user interface (GUI). You can optionally add a couple of methods that use the Java Swing classes to build
    a JTree which can be displayed in a true GUI.
    import java.awt.*;
    import java.awt.event.*;
    import javax.swing.*;
    import javax.swing.tree.*;
    private DefaultMutableTreeNode buildJTree(Node<T> n) { }
    public JTree buildJTree() { }
    public void buildAndDisplayJTree() { }
    private static void expandAll(JTree tr, TreePath p, boolean expand) { }
    public static void expandAll(JTree tr, boolean expand) { }
    The methods dealing with the GUI are optional. You will be given additional code hints if you are interested in
    implementing them.
    Use the following as a simple driver for starters:
    public static void main(String[] args) {
    BST<Integer> bsttree = new BST<Integer>();
    generate(bsttree,20,1000);
    System.out.println(bsttree);
    bsttree.buildAndDisplayJTree(); // optional
    }
    
    -----------------
    
    Here code what I tried so far, i know it is flaw. =/ 
    
    import java.util.*;
    
    /*
    
    class extend implements Comparable {
    
    public class BinarySearchTree
    {
        public BinarySearchTree()
        {
          //  root = null;
            //  Node n = new Node(v);// I ADDED, unsure
             
       }
    */
    
    
    class BinarySearchTree<T implements Comparable<T>>
    {
        class Node<T>
        {
        private Node<T> root;
        }
    
    public static void insert(int v) //professor wrote "insert (int v)//
    {
    
        // Node n = new Node(v);
    
            if(root == null)
                root = n;
           
            else
            {
                Node m = root;
               
                while((n.value < m.value && m.left != null) ||
                      (n.value >= m.value && m.right !=null))
                     
                      if(n.value < m.value) m =m.left;
                          else m = m.right;
            }
           
            if(n.value < m.value) m.left = n;
                else m.right = n;
               
    }           
            //    
            public String toString()
            {
                return toString(root); // recursion starts at root
            }
           
            private String toString(Node n)
            {
                if(n == null)
                    return "";
           
                    String result = "";
                    result += toString(n.left); // everything < n
                    result += n.value + " "; // n
                    result += toString(n.right); // everything > n
               
                return result;
               
            }
           
            public void delete(T value)
            {
                Node m = new Node();
               
    //            (m.left == null && m.right == null);
               
                if(p.right = null)
                    p.right = null;
                else
                    p.left = null;
                   
             // switch
            // case 1: 0 children;
            // case 2: 1 children;
                        if    ((m. left != null && m.right != null) || (m.left == null && m.right == null));
                            p.left = m.left;
                            p.left = m. right;
           
                            p.right = m.left;
                           
           
                            p.right = m.right;
                           
            // case 3: 2 children;
                // step 1: find inorder successor of m.
                // step 2: save the inorder succesor value to a temp 102
                // step 3: m.value = temp;
                     p = null;
                    m = root;
                    while(m.right != null)
                    {
                        p = m;
                        m = m.right;
                    }
                   
            // case 4: ??
                       
                           
            //     default;
             
             
            }
           
            public static int min()
            {
                if ( root == null)
            //        { error  or -1; }
                {
                else
                    Node m = root;
                    while(m.left != null)
                        m = m.left;
                }   
                    return m.value;
            }
           
    }

    :confused:
    Last edited by xajaxworldx; 05-06-2011 at 07:00 AM.

  2. #2
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    Why did you quote your question?

  3. #3
    xajaxworldx is offline Member
    Join Date
    May 2011
    Posts
    5
    Rep Power
    0

    Default

    This is my first time to use java forums website.

    I copied and pasted what the teacher says and do code.

  4. #4
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    Please edit and fix your original post by changing the [quote] and [/quote] tags to [code] and [/code] tags.

  5. #5
    xajaxworldx is offline Member
    Join Date
    May 2011
    Posts
    5
    Rep Power
    0

    Default

    But the way above is not really code.. and below is code what i tried so far.

Similar Threads

  1. Binary search tree
    By hansmoolman in forum New To Java
    Replies: 2
    Last Post: 10-28-2010, 02:59 PM
  2. Replies: 0
    Last Post: 04-04-2010, 08:40 AM
  3. Binary search tree search method
    By chopo1980 in forum New To Java
    Replies: 2
    Last Post: 12-10-2009, 02:42 AM
  4. Binary Search Tree
    By anmadie in forum New To Java
    Replies: 5
    Last Post: 11-17-2009, 03:39 AM
  5. Binary Search Tree
    By Goo in forum New To Java
    Replies: 0
    Last Post: 03-06-2009, 05:46 PM

Posting Permissions

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