Results 1 to 5 of 5
 05062011, 05:28 AM #1Member
 Join Date
 May 2011
 Posts
 5
 Rep Power
 0
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 onedimensional 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; 05062011 at 06:00 AM.
 05062011, 05:29 AM #2
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,069
 Blog Entries
 3
 Rep Power
 10
Why did you quote your question?
 05062011, 05:55 AM #3Member
 Join Date
 May 2011
 Posts
 5
 Rep Power
 0
This is my first time to use java forums website.
I copied and pasted what the teacher says and do code.

Please edit and fix your original post by changing the [quote] and [/quote] tags to [code] and [/code] tags.
 05062011, 05:59 AM #5Member
 Join Date
 May 2011
 Posts
 5
 Rep Power
 0
Similar Threads

Binary search tree
By hansmoolman in forum New To JavaReplies: 2Last Post: 10282010, 01:59 PM 
Data Structures(Binary Search Tree to AVL Tree)ASAP pls
By jfAdik in forum Forum LobbyReplies: 0Last Post: 04042010, 07:40 AM 
Binary search tree search method
By chopo1980 in forum New To JavaReplies: 2Last Post: 12102009, 02:42 AM 
Binary Search Tree
By anmadie in forum New To JavaReplies: 5Last Post: 11172009, 03:39 AM 
Binary Search Tree
By Goo in forum New To JavaReplies: 0Last Post: 03062009, 05:46 PM
Bookmarks