There are three classes below: Tree, Node and TreeApp. Can you check to see if t
ID: 3811111 • Letter: T
Question
There are three classes below: Tree, Node and TreeApp. Can you check to see if the methods that I created are correct in the the tree class below. Also, explain how to add to TreeApp class main and give options for user to select size(), depth(), removeLeaves(), rightMinValue(), leftMaxValue(), maximum() and minimum().
These are the methods
1. int size()
2. int depth(int key)
3. void removeLeaves()
4. int rightMinValue()
5. int leftMaxValue()
6. int maximum()
7. int minimum()
import java.io.*;
import java.util.*; // for Stack class
////////////////////////////////////////////////////////////////
class Tree
{
private Node root; // first node of tree
// -------------------------------------------------------------
public Tree() // constructor
{
root = null;
} // no nodes in tree yet
// -------------------------------------------------------------
public Node find(int key) // find node with given key
{ // (assumes non-empty tree)
Node current = root; // start at root
while(current.iData != key) // while no match,
{
if(key < current.iData) // go left?
current = current.leftChild;
else // or go right?
current = current.rightChild;
if(current == null) // if no child,
return null; // didn't find it
}
return current; // found it
} // end find()
// -------------------------------------------------------------
public void insert(int id, double dd)
{
Node newNode = new Node(); // make new node
newNode.iData = id; // insert data
newNode.dData = dd;
if(root==null) // no node in root
root = newNode;
else // root occupied
{
Node current = root; // start at root
Node parent;
while(true) // (exits internally)
{
parent = current;
if(id < current.iData) // go left?
{
current = current.leftChild;
if(current == null) // if end of the line,
{ // insert on left
parent.leftChild = newNode;
return;
}
} // end if go left
else // or go right?
{
current = current.rightChild;
if(current == null) // if end of the line
{ // insert on right
parent.rightChild = newNode;
return;
}
} // end else go right
} // end while
} // end else not root
} // end insert()
// -------------------------------------------------------------
public boolean delete(int key) // delete node with given key
{ // (assumes non-empty list)
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while(current.iData != key) // search for node
{
parent = current;
if(key < current.iData) // go left?
{
isLeftChild = true;
current = current.leftChild;
}
else // or go right?
{
isLeftChild = false;
current = current.rightChild;
}
if(current == null) // end of the line,
return false; // didn't find it
} // end while
// found node to delete
// if no children, simply delete it
if(current.leftChild==null &&
current.rightChild==null)
{
if(current == root) // if root,
root = null; // tree is empty
else if(isLeftChild)
parent.leftChild = null; // disconnect
else // from parent
parent.rightChild = null;
}
// if no right child, replace with left subtree
else if(current.rightChild==null)
if(current == root)
root = current.leftChild;
else if(isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
// if no left child, replace with right subtree
else if(current.leftChild==null)
if(current == root)
root = current.rightChild;
else if(isLeftChild)
parent.leftChild = current.rightChild;
else
parent.rightChild = current.rightChild;
else // two children, so replace with inorder successor
{
// get successor of node to delete (current)
Node successor = getSuccessor(current);
// connect parent of current to successor instead
if(current == root)
root = successor;
else if(isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = successor;
// connect successor to current's left child
successor.leftChild = current.leftChild;
} // end else two children
// (successor cannot have a left child)
return true; // success
} // end delete()
// -------------------------------------------------------------
// returns node with next-highest value after delNode
// goes to right child, then right child's left descendents
private Node getSuccessor(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild; // go to right child
while(current != null) // until no more
{ // left children,
successorParent = successor;
successor = current;
current = current.leftChild; // go to left child
}
// if successor not
if(successor != delNode.rightChild) // right child,
{ // make connections
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
// -------------------------------------------------------------
public void traverse(int traverseType)
{
switch(traverseType)
{
case 1: System.out.print(" Preorder traversal: ");
preOrder(root);
break;
case 2: System.out.print(" Inorder traversal: ");
inOrder(root);
break;
case 3: System.out.print(" Postorder traversal: ");
postOrder(root);
break;
}
System.out.println();
}
// -------------------------------------------------------------
private void preOrder(Node localRoot)
{
if(localRoot != null)
{
System.out.print(localRoot.iData + " ");
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void inOrder(Node localRoot)
{
if(localRoot != null)
{
inOrder(localRoot.leftChild);
System.out.print(localRoot.iData + " ");
inOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void postOrder(Node localRoot)
{
if(localRoot != null)
{
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.print(localRoot.iData + " ");
}
}
// -------------------------------------------------------------
public void displayTree()
{
Stack globalStack = new Stack();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out.println(
"......................................................");
while(isRowEmpty==false)
{
Stack localStack = new Stack();
isRowEmpty = true;
for(int j=0; j<nBlanks; j++)
{
System.out.print(' ');
}
while(globalStack.isEmpty()==false)
{
Node temp = (Node)globalStack.pop();
if(temp != null)
{
System.out.print(temp.iData);
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);
if(temp.leftChild != null || temp.rightChild != null)
{
isRowEmpty = false;
}
}
else
{
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for(int j=0; j<nBlanks*2-2; j++)
{
System.out.print(' ');
}
} // end while globalStack not empty
System.out.println();
nBlanks /= 2;
while(localStack.isEmpty()==false)
{
globalStack.push(localStack.pop());
}
} // end while isRowEmpty is false
System.out.println(
"......................................................");
} // end displayTree()
// -------------------------------------------------------------
public int size()
{
return size(root);
}
private int size(Node a)
{
if(a != null)
{
return 1 + size(a.leftChild) + size(a.rightChild);
}
return 0;
}
public int depth(int key)
{
Node current = root;
int depth = 0;
while(current.iData != key)
{
if(current == null)
{
return -1;
}
if(current.iData < key)
{
current = current.rightChild;
}
else
{
current = current.leftChild;
depth++;
}
}
return depth;
}
public void removeLeaves()
{
removeLeaves2(root);
}
public void removeLeaves2(Node a)
{
if(a.leftChild != null)
{
if(a.leftChild.rightChild == null && a.leftChild.leftChild == null)
{
a.leftChild = null;
}
else
{
removeLeaves2(a.leftChild);
}
}
if(a.rightChild != null)
{
if(a.rightChild.rightChild == null && a.rightChild == null)
{
a.rightChild = null;
}
else
{
removeLeaves2(a.rightChild);
}
}
}
public int rightMaxValue()
{
return rightMaxValue(root);
}
private int rightMaxValue(Node a)
{
int max = a.iData;
if (a.rightChild != null)
{
max = Math.max(max, rightMaxValue(a.rightChild));
}
return max;
}
public int leftMaxValue()
{
return leftMaxValue(root);
}
private int leftMaxValue(Node a)
{
int max = a.iData;
if (a.leftChild != null)
{
max = Math.max(max, leftMaxValue(a.leftChild));
}
return max;
}
public int maximum()
{
return maximum(root);
}
private int maximum(Node a)
{
int max = a.iData;
if (a.leftChild != null)
{
max = Math.max(max, maximum(a.leftChild));
}
if (a.rightChild != null)
{
max = Math.max(max, maximum(a.rightChild));
}
return max;
}
private int minimum(Node a)
{
int min = a.iData;
if (a.leftChild != null)
{
min = Math.min(min, minimum(a.leftChild));
}
if (a.rightChild != null)
{
min = Math.min(min, minimum(a.rightChild));
}
return min;
}
public int minimum()
{
return minimum(root);
}
} // end class Tree
class Node
{
public int iData; // data item (key)
public double dData; // data item
public Node leftChild; // this node's left child
public Node rightChild; // this node's right child
public void displayNode() // display ourself
{
System.out.print('{');
System.out.print(iData);
System.out.print(", ");
System.out.print(dData);
System.out.print("} ");
}
} // end class Node
import java.io.*;
import java.util.Scanner;
class TreeApp
{
public static void main(String[] args) throws IOException
{
int value;
Tree theTree = new Tree();
theTree.insert(50, 1.5);
theTree.insert(25, 1.2);
theTree.insert(75, 1.7);
theTree.insert(12, 1.5);
theTree.insert(37, 1.2);
theTree.insert(43, 1.7);
theTree.insert(30, 1.5);
theTree.insert(33, 1.2);
theTree.insert(87, 1.7);
theTree.insert(93, 1.5);
theTree.insert(97, 1.5);
Scanner kb = new Scanner(System.in);
System.out.println("Hello! Please select size, depth, removeLeaves, rightMinValue, leftMaxValue, maximum, or minimum: ");
int selectedElement = kb.nextInt();
while(true)
{
System.out.println("Enter first letter of show, ");
System.out.println("insert, find, delete, or traverse: ");
int choice = getChar();
switch(choice)
{
case 's':
theTree.displayTree();
break;
case 'i':
System.out.print("Enter value to insert: ");
value = getInt();
theTree.insert(value, value + 0.9);
break;
case 'f':
System.out.print("Enter value to find: ");
value = getInt();
Node found = theTree.find(value);
if(found != null)
{
System.out.print("Found: ");
found.displayNode();
System.out.print(" ");
}
else
System.out.print("Could not find ");
System.out.print(value + ' ');
break;
case 'd':
System.out.print("Enter value to delete: ");
value = getInt();
boolean didDelete = theTree.delete(value);
if(didDelete)
System.out.print("Deleted " + value + ' ');
else
System.out.print("Could not delete ");
System.out.print(value + ' ');
break;
case 't':
System.out.print("Enter type 1, 2 or 3: ");
value = getInt();
theTree.traverse(value);
break;
default:
System.out.print("Invalid entry ");
int key = 100;
if(theTree.depth(key) != -1)
{
System.out.println("Depth of " + key + "is " + theTree.depth(key));
}
else
{
System.out.println("Key not in Tree.");
}
} // end switch
} // end while
} // end main()
// -------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
// -------------------------------------------------------------
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
//-------------------------------------------------------------
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
// -------------------------------------------------------------
} // end class TreeApp
////////////////////////////////////////////////////////////////
Explanation / Answer
Solution:
Modified TreeApp.JAVA
package treeapp;
import java.io.*;
import java.util.Scanner;
class TreeApp
{
public static void main(String[] args) throws IOException
{
int value;
Tree theTree = new Tree();
theTree.insert(50, 1.5);
theTree.insert(25, 1.2);
theTree.insert(75, 1.7);
theTree.insert(12, 1.5);
theTree.insert(37, 1.2);
theTree.insert(43, 1.7);
theTree.insert(30, 1.5);
theTree.insert(33, 1.2);
theTree.insert(87, 1.7);
theTree.insert(93, 1.5);
theTree.insert(97, 1.5);
Scanner kb = new Scanner(System.in);
while(true)
{
System.out.println(" Enter the letter of choices:");
System.out.println("s: show i: insert f: find d: delete t:traverse a:size b:depth");
System.out.println("r:removeLeaves c: right min value e: left max value x: maximum n:minimum");
int choice = getChar();
switch(choice)
{
case 's':
theTree.displayTree();
break;
case 'i':
System.out.print("Enter value to insert: ");
value = getInt();
theTree.insert(value, value + 0.9);
break;
case 'f':
System.out.print("Enter value to find: ");
value = getInt();
Node found = theTree.find(value);
if(found != null)
{
System.out.print("Found: ");
found.displayNode();
System.out.print(" ");
}
else
System.out.print("Could not find ");
System.out.print(value + ' ');
break;
case 'd':
System.out.print("Enter value to delete: ");
value = getInt();
boolean didDelete = theTree.delete(value);
if(didDelete)
System.out.print("Deleted " + value + ' ');
else
System.out.print("Could not delete ");
System.out.print(value + ' ');
break;
case 't':
System.out.print("Enter type 1, 2 or 3: ");
value = getInt();
theTree.traverse(value);
break;
case 'a':
System.out.print("Size of the tree is : "+theTree.size());
break;
case 'b':
System.out.println("Enter key to find the depth");
int ke=kb.nextInt();
System.out.print("Depth of the tree is : "+theTree.depth(ke));
break;
case 'r':
theTree.removeLeaves();
break;
case 'c':
System.out.println("The right min value is"+theTree.rightMaxValue());
break;
case 'e':
System.out.println("The left max value is"+theTree.leftMaxValue());
break;
case 'x':
System.out.println("Maximum"+theTree.maximum());
break;
case 'n':
System.out.println("Minimum"+theTree.minimum());
break;
default:
System.out.print("Invalid entry ");
int key = 100;
if(theTree.depth(key) != -1)
{
System.out.println("Depth of " + key + "is " + theTree.depth(key));
}
else
{
System.out.println("Key not in Tree.");
}
}
} // end while
} // end main()
// -------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
// -------------------------------------------------------------
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
//-------------------------------------------------------------
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
// -------------------------------------------------------------
} // end class TreeApp
/////////////////////////////////////////////////////////////
Sample Run:
run:
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
s
......................................................
50
25 75
12 37 -- 87
-- -- 30 43 -- -- -- 93
-- -- -- -- -- 33 -- -- -- -- -- -- -- -- -- 97
......................................................
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
n
Minimum12
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
x
Maximum97
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
e
The left max value is50
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
c
The right min value is97
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
r
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
s
......................................................
50
25 75
-- 37 -- 87
-- -- 30 43 -- -- -- 93
-- -- -- -- -- 33 -- -- -- -- -- -- -- -- -- 97
......................................................
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
r
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
s
......................................................
50
25 75
-- 37 -- 87
-- -- 30 43 -- -- -- 93
-- -- -- -- -- 33 -- -- -- -- -- -- -- -- -- 97
......................................................
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
i
Enter value to insert: 100
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
s
......................................................
50
25 75
-- 37 -- 87
-- -- 30 43 -- -- -- 93
-- -- -- -- -- 33 -- -- -- -- -- -- -- -- -- 97
--------------------------------------------------------------100
......................................................
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
c
The right min value is100
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
x
Maximum100
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
c
The right min value is100
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
e
The left max value is50
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
a
Size of the tree is : 11
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
i
Enter value to insert: 10
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
s
......................................................
50
25 75
10 37 -- 87
-- -- 30 43 -- -- -- 93
-- -- -- -- -- 33 -- -- -- -- -- -- -- -- -- 97
--------------------------------------------------------------100
......................................................
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum
a
Size of the tree is : 12
Enter the letter of choices:
s: show
i: insert
f: find
d: delete
t:traverse
a:size
b:depth
r:removeLeaves
c: right min value
e: left max value
x: maximum
n:minimum