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

[xajaxworldx]

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:

[sunde887]

Why did you quote your question?

[xajaxworldx]

This is my first time to use java forums website.

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

[Fubarable]

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

[xajaxworldx]

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