public class BinarySearchTreeND < K extends Comparable < ? super K > > { static

Question

public class BinarySearchTreeND
< K extends Comparable < ? super K > >

{
static final int DEPTHDELTA = 5; // used to create a text tree display

BSTNodeND < K > root = null;

public void insert (K d) {
insertNode (new BSTNodeND < K > (d)); } // end insert, public version

public void insertNode (BSTNodeND < K > n) {
if (root == null) root = n;
else insertNode (n, root); } // end insert Node

public K find (K d) {
if (root == null)
return null;
BSTNodeND < K > t = findValue (d, root);
return (t==null)?null:t.data; } // end find method

public K max () {
if (root == null)
return null;
return findMax(root).data; } // end max method

public int getSize () {
return getSize (root);}

public void remove (K d) {
root = remove (d, root); } // end remove data

public String toString () {
if (root == null)
return null;
return toString(root);}

private void insertNode (BSTNodeND < K > d, BSTNodeND < K > n) {
d.parent = n;
if (d.data.compareTo (n.data) > 0)
if (n.right == null) n.right = d;
else insertNode (d, n.right);
else
if (n.left == null) n.left = d;
else insertNode (d, n.left); } // end method insertNode

private BSTNodeND < K > findValue (K d, BSTNodeND < K > n) {
if (n.data.compareTo(d) == 0)
return n;
if (n.data.compareTo (d) > 0)
return (n.left==null)?null:findValue (d, n.left);
return (n.right == null)?null:findValue(d, n.right); } // end findValue

private BSTNodeND < K > findMax (BSTNodeND < K > n) {
if (n.right == null)
return n;
return findMax(n.right); } // end findValue

private int getSize (BSTNodeND < K > t) {
if (t == null)
return 0;
return getSize (t.left) + getSize (t.right) + 1; } // end getSize node

private BSTNodeND < K > removeRoot (BSTNodeND < K > t) {
if (t.left == null) {
if (t.right != null)
t.right.parent = t.parent;
return t.right;
}
if (t.right == null) {
t.left.parent = t.parent; // t.left != null because of earlier if test case
return t.left;
}
BSTNodeND < K > newTop = findMax(t.left);
remove (newTop.data, t); // lose the node instance, leave tree intact
t.data = newTop.data; // just replace the data at the internal node
return t; } // end remove data, tree

private BSTNodeND < K > remove (K d, BSTNodeND < K > t) {
if (t == null)
return null;
if (d.compareTo (t.data) < 0)
t.left = remove (d, t.left );
else
if (d.compareTo (t.data)> 0)
t.right = remove (d, t.right);
else // d equals t.data
t = removeRoot (t);
return t; } // end remove data, tree

private String toString (BSTNodeND < K > n) {
return toTreeString (5, n, '>'); } // end toString

// removed use of parent reference, added label parameter, 5/13/2012
private String toTreeString (int depth, BSTNodeND < K > n, char label) { // depth = 0 is bad
return
((n.left == null)?"":toTreeString (depth + DEPTHDELTA, n.left, '/'))
+ String.format ("%" + depth + "s%s ", label, n) // ND: fixed 4/17/2009
+ ((n.right == null)?"":toTreeString (depth + DEPTHDELTA, n.right, '\')); } // end method toTreeString

private String toInOrderString (BSTNodeND < K > n) {
return
((n.left == null)?"":toInOrderString(n.left ))
+ n + " "
+ ((n.right == null)?"":toInOrderString(n.right)); } // end toInOrderString

private String toPreOrderString (BSTNodeND < K > n) {
return
n + " "
+ ((n.left == null)?"":toPreOrderString(n.left ))
+ ((n.right == null)?"":toPreOrderString(n.right)); } // end toPreOrderString

private String toPostOrderString (BSTNodeND < K > n) {
return
((n.left == null)?"":toPostOrderString(n.left ))
+ ((n.right == null)?"":toPostOrderString(n.right))
+ n + " "; } // end to PostOrderString

// See: http://en.wikipedia.org/wiki/Tree_traversal
private String toLevelOrderString (BSTNodeND < K > n) {
String st = "";
BSTNodeND < K > node;
java.util.ArrayDeque < BSTNodeND < K > > q
= new java.util.ArrayDeque < BSTNodeND < K > > ();
q.add (n); // start queue by adding this (root?) to queue
while (q.size() > 0) {
node = q.remove(); // remove the head of queue
st += (node.data + " "); // process head data to String
if (node.left != null) q.add (node.left); // insert left child at end of queue
if (node.right != null) q.add (node.right); // insert right child at end or queue
} // end queue processing
return st.toString(); } // end to LevelOrderString

// main and example methods follow
public static void main (String args []) {
integerExample ();
stringExample ();
Scanner st = new Scanner (System.in);
while (menu(st));
System.out.println ("...Bye"); } // end main

static boolean menu (Scanner st) {
System.out.println ("enter integer values, q to quit:");
String line = st.nextLine();
if (line.length() == 0)
return true; // just <cr> causes crash on next line

Scanner tokens = new Scanner (line).useDelimiter ("[,\s]+"); // allow comma+space separators
if (! tokens.hasNextInt())
if (tokens.hasNext() && tokens.next().equalsIgnoreCase ("q"))
return false;
else
return true;

BinarySearchTreeND <Integer> tree = new BinarySearchTreeND <Integer> ();
while (tokens.hasNextInt()) tree.insert (tokens.nextInt());
System.out.println ("Tree: " + tree);
System.out.println ("Tree in-order: " + tree.toInOrderString (tree.root));
System.out.println ("Tree pre-order: " + tree.toPreOrderString (tree.root));
System.out.println ("Tree post-order: " + tree.toPostOrderString (tree.root));
System.out.println ("Tree level-order: " + tree.toLevelOrderString(tree.root));

if (tokens.hasNext() && tokens.next().equalsIgnoreCase ("q"))
return false;

return true; } // end menu

public static void integerExample () {
BinarySearchTreeND < Integer > x = new BinarySearchTreeND < Integer > ();
int arr [] = {
40, 20, 60, 10, 30, 50, 70, 5, 15, 25, 35, 45, 55, 65, 75,
60, 45, 50, 40, 55,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
};
int rem [] = {};
for (int y: arr) x.insert (y);

System.out.println ("X: " + x);
System.out.println ("X in-order: " + x.toInOrderString(x.root));
System.out.println ("X pre-order: " + x.toPreOrderString(x.root));
System.out.println ("X post-order: " + x.toPostOrderString(x.root));
System.out.println ("X level-order: " + x.toLevelOrderString(x.root));

Integer t = x.find(10);
System.out.println ("find: " + t);
System.out.println ("find: " + x.find(20));
System.out.println ("Size: " + x.getSize());
System.out.println ("MAX: " + x.max());
for (int y: rem) {
System.out.println ("Removing: " + y);
x.remove (y);
System.out.println ("result: " + x);
}
System.out.println ("X: " + x); } // end integerExample

public static void stringExample () {
// The following is an example using a user-defined class, see below
// notice the use of the generic parameter Example
String [] sa = {"one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"};
BinarySearchTreeND < Example > ex = new BinarySearchTreeND < Example > ();
for (String s: sa) ex.insert (new Example (s));
System.out.println ("Example using strings: " + ex); } // end stringExample

// needs to be internal class so, eg, AVLNode in AVLND can extend this internal node class
class BSTNodeND < L extends Comparable< ? super L > > {
L data;
BSTNodeND < L > left, right, parent;

BSTNodeND (L d) {data = d;}
BSTNodeND (L d, BSTNodeND <L> p) {data = d; parent = p;}

public String toString () {
return data.toString();} // end toString method
} // end class BSTNodeND
} // end class BinarySearchTreeND

// A class that can be used with the BinarySearchTreeND data structure
// Notice the use of the generic parameter Example
class Example implements Comparable < Example > {
String data;

public Example (String d) {
data = d;}

// you, of course, will want a more interesting compareTo method
public int compareTo (Example e) {
return data.compareTo (e.data); } // end compareTo method

public String toString () {
return data; } // end toString
} // end class ExampleEnter question here...

Explanation / Answer

public class BinarySearchTree{ public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); tree.add(5); tree.add(1); tree.add(2); tree.add(6); } private Node root; private int size; String inorder = ""; String preorder = ""; public BinarySearchTree(){ root = null; size = 0; } //adds a new item to the queue public void add(T obj) { Node n = new Node(obj); if( root == null ) { root = n; } else { add( root, n ); } size++; } private void add(Node subtree, Node n) { if( subtree.getValue().compareTo(n.getValue()) > 0 ) { if( subtree.getLeftChild() == null ) { subtree.setLeftChild(n); n.setParent(subtree); } else { add( subtree.getLeftChild(), n ); } } else { if( subtree.getRightChild() == null ) { subtree.setRightChild(n); n.setParent(subtree); } else { add( subtree.getRightChild(), n ); } } } //returns the head of the queue public T peek(){ Node current = root; while(current.getLeftChild() != null){ current = current.getLeftChild(); } return current.getValue(); } //removes the head of the queue and returns it public T remove(){ if(root == null){ return null; } Node current = root; while(current.getLeftChild() != null){ current = current.getLeftChild(); } if( current.getParent() == null ) { root = current.getRightChild(); if(root != null){ root.setParent(null); } } else { current.getParent().setLeftChild(current.getRightChild()); if(current.getRightChild() != null){ current.getRightChild().setParent(current.getParent()); } } size--; return current.getValue(); } //returns the position of an element in the queue, or -1 if it is not found public int search(T searchItem){ String tempOrdered = inorder(root); for(int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.