Create the following in JAVA and submit it in a word file. Please make it output
ID: 3860293 • Letter: C
Question
Create the following in JAVA and submit it in a word file. Please make it output in the same format as the example output at the bottom!
Create a class NewTree with the following:
• Internal class Node
Instance variables
data: an integer value
leftChild: a Node representing the child to the left
rightChild: a Node representing the child to the right
• Instance variables
root: a Node representing the first element in the tree.
• Methods
insert: This method returns nothing and takes in an integer value that is then placed as a new node in the tree based on the binary tree properties. A reminder values greater than the parent go to the right subtree and values smaller go to the left subtree. Also it may be a good idea to use a recursive method in order to place these values.
remove: This method returns nothing and takes in an integer value that is to be removed. First the method must search for the value. If the value is found the it is removed while preserving the integrity of the binary search tree. Remember there are cases for the node having no children, having one child, and having two children.
printPreorder: This method which returns nothing and has no parameters prints the pre-order traversal of the tree. For pre-order traversal each the value is printed out, then left subtree must be visited, and finally each of the right subtrees is visited. It is a good idea to make a recursive method to assist with this.
getDepth: The depth of a node is the number of edges from the root to that number. This method returns nothing and takes in a parameter corresponding to the integer value of a node whose depth is returned. If the value is not in the tree a -1 should be returned. Again a recursive helper method may be useful to solve this.
Create another file that creates an instance of the NewTree and tests each of the methods.
Example Output:
Testing the tree
Insterting 10 numbers
Inserting 8
Inserting 13
Inserting 3
Inserting 4
Inserting 18
Inserting 19
Inserting 10
Inserting 1
Inserting 9
Inserting 2
Printing pre-order traversal
8
3
1
2
4
13
10
9
18
19
Removing the number 4
8
3
1
2
13
10
9
18
19
The Depth of 9 is 3
Done!
Explanation / Answer
/**
* The java program IntBSTreeTester that
* tests the IntBSTree and prints the results
* to console of each method of IntBSTree class
* */
///IntBSTreeTester.java
public class IntBSTreeTester
{
public static void main(String[] args)
{
System.out.println("Testing the tree");
IntBSTree testTree = new IntBSTree();
System.out.println("Inserting 10 numbers");
int[] valArr = {8,13,3,4,18,19,10,1,9,2};
for(int i : valArr)
{
System.out.println("Inserting "+i);
testTree.insert(i);
}
System.out.println("Printing pre-order traversal");
testTree.printInorder();
System.out.println("Removing the number 4");
testTree.remove(4);
testTree.printInorder();
System.out.println("The Depth of 9 is "+testTree.getDepth(3));
}
}
---------------------------------------------------------------------------
//IntBSTree.java
public class IntBSTree
{
//Node class
private class Node
{
private int data;
private Node leftChild;
private Node rightChild;
public Node(int aData)
{
this.data = aData;
this.leftChild = null;
this.rightChild = null;
}
}
private Node root;
public IntBSTree()
{
root = null;
}
//Method insert that takes data
//and calls the insert method to
//insert data into the tree
public void insert(int data)
{
Node newNode=new Node(data);
newNode.data=data;
if(root==null)
root=newNode;
else
insert(root,data);
}
//Helper method that takes node and data
//and inserts the data into the tree
private Node insert(Node aNode, int data) {
if(aNode==null)
{
Node newNode=new Node(data);
newNode.data=data;
aNode=newNode;
}
else if(data<aNode.data)
{
aNode.leftChild=insert(aNode.leftChild, data);
}
else if(data>aNode.data)
{
aNode.rightChild=insert(aNode.rightChild, data);
}
return aNode;
}
//calls printPreorder helper method
public void printInorder()
{
System.out.println("preorder");
printPreorder(root);
}
//remove method that takes data as input argumet
void remove(int data)
{
//calls helper method remove
root = remove(root, data);
}
/*Recursive method to remove the data from the tree*/
Node remove(Node root, int data)
{
if (root == null) return root;
if (data < root.data)
root.leftChild = remove(root.leftChild, data);
else if (data > root.data)
root.rightChild = remove(root.rightChild, data);
else
{
if (root.leftChild == null)
return root.rightChild;
else if (root.rightChild == null)
return root.leftChild;
root.data = minValue(root.rightChild);
root.rightChild = remove(root.rightChild, root.data);
}
return root;
}
//Returns the min value of the tree
int minValue(Node root)
{
int minv = root.data;
while (root.leftChild != null)
{
minv = root.leftChild.data;
root = root.leftChild;
}
return minv;
}
// post: prints in preorder the tree with given root
private void printPreorder(Node root) {
if (root != null) {
System.out.println(root.data);
printPreorder(root.leftChild);
printPreorder(root.rightChild);
}
}
//Returns the depth of the node
public int getDepth(int data) {
return getDepth(root, data, 1);
}
//Returns the depth of the tree
//Depth is the number of edgers from the root to
//given node or value
public int getDepth(Node root, int data, int level) {
if (root == null)
return 0;
if (root.data==data)
return level+1;
int ret = getDepth(root.leftChild, data, level + 1);
if (ret != 0)
return ret;
ret = getDepth(root.rightChild, data, level + 1);
return ret;
}
}
---------------------------------------------------------------------------
Sample Output:
Testing the tree
Inserting 10 numbers
Inserting 8
Inserting 13
Inserting 3
Inserting 4
Inserting 18
Inserting 19
Inserting 10
Inserting 1
Inserting 9
Inserting 2
Printing pre-order traversal
preorder
8
3
1
2
4
13
10
9
18
19
Removing the number 4
preorder
8
3
1
2
13
10
9
18
19
The Depth of 9 is 3
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.