Need to successfully add the following methods to a JAVA binary tree. The code f
ID: 3834799 • Letter: N
Question
Need to successfully add the following methods to a JAVA binary tree. The code for the tree is given in the book. THe BinaryTreeTester main class cannot be modified. The methods below will go under the Binary Tree class. I am having trouble integrating the methods successfully to the existing binary tree. So A working solution with the 6 methods will get extra points.
boolean update (int oldValue, int newValue)
-Searches for oldValue in the tree. If found, the data for that node is changed to newValue and the tree is modified such that the node with the new value is placed in the appropriate place in the tree and returns true
-If the oldValue is not found in the tree, the function returns false and the tree stays as is
int findMin()
-If the tree is empty, return -1
-Otherwise, return the smallest value node in the tree
int findMax()
-If the tree is empty, return -1
-Otherwise, return the largest value node in the tree
double calculateAverage()
-If the tree is empty, return 0.0
-Otherwise, return the average value of the tree by adding all node values and dividing by the number of nodes in the tree
int getNumberOfNodes()
-Returns the number of nodes in the tree
boolean isBalanced()
-If the tree is empty, return false
-Otherwise, return true if the tree is balanced
-A balanced is tree is defined as follows:
here is the code: BinaryTree class:
package binarytreetester;
import java.util.Stack;
public class BinaryTree {
// insert function
private Node root;
public BinaryTree()
{
root = null;
}
public void insert(int n)
{
Node current = root;
Node newNode = new Node();
newNode.data = n;
newNode.left = null;
newNode.right = null;
if (root == null)
root = newNode;
else
while(true)
if (newNode.data > current.data)
if (current.right == null)
{
current.right = newNode;
break;
}
else
current = current.right;
else
if (current.left == null)
{
current.left = newNode;
break;
}
else
current = current.left;
}
// Search function
public Node search(int n)
{
Node current = root; // assign node to root
while (current != null)
if (current.data == n)
return current;
else if (current.data > n) //greater than n we go to the left
current = current.left;
else
current = current.right;
return null;
}
// Delete Function below
public boolean remove(int n)
{
// Check empty tree
if (root == null)
return false;
// Prepare search for node
Node current = root;
Node parent = root;
boolean currentIsLeft = true;
// At this point, current is the node to delete
// Now, we check for the situations
// Situation 1 - leaf node
if (current.left == null && current.right == null)
// Check if current node is root
if (parent == current)
root = null;
// Check which child pointer of parent to set
else if (currentIsLeft)
parent.left = null;
else
parent.right = null;
// Situation 2 - one child. Parent inherits child
// or if current is root, root takes child
else if (current.left == null)
if (parent == current)
root = current.right;
else if (currentIsLeft)
parent.left = current.right;
else
parent.right = current.right;
else if (current.right == null)
if (parent == current)
root = current.left;
else if (currentIsLeft)
parent.left = current.left;
else
parent.right = current.left;
// Situation 3: two children
else
{
Node successor = getSuccessor(current);
// Replace current node with successor
if (parent == current)
root = successor;
else if (currentIsLeft)
parent.left = successor;
else
parent.right = successor;
// Successor will always come from the right, so
// it must also take deleted node’s left child
successor.left = current.left;
}
return true;
}
private Node getSuccessor(Node removedNode)
{
// Prepare successor search by keeping track
// of parent and current
Node successorParent = removedNode;
Node successor = removedNode;
Node current = successor.right;
// Starting at the right child of the node to be
// removed, go down the subtree’s left children
// until there are no more children on the left
while (current != null)
{
successorParent = successor;
successor = current;
current = current.left;
}
// if the successor is somewhere down the subtree,
// the parent’s left child must take the
// the successor’s right child. Then, the
// successor’s right child takes the node
// to delete’s right child (because successor will
// be replacing it.
if (successor != removedNode.right)
{
successorParent.left = successor.right;
successor.right = removedNode.right;
}
// Note that if the successor is the immediate
// right child of the node to delete, we just
// return that node (it has no left children and what
// ever is on successor’s right stays that way even
// after successor replaces the removed node.
return successor;
}
// Traversing a Tree
public void display()
{
inOrder(root);
/* 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 i = 0; i<nBlanks; i++)
System.out.print (" ");
while (globalStack.isEmpty()== false)
{
Node temp = (Node)globalStack.pop();
if (temp != null)
{
System.out.print (temp.data);
localStack.push(temp.left);
localStack.push(temp.right);
if (temp.left != null || temp.right != null)
isRowEmpty = false;
}
else
{
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for (int i=0 ; i<nBlanks*2-2; i++)
System.out.print(' ');
} // end while globlstack not empty
System.out.println();
nBlanks /= 2;
while (localStack.isEmpty() == false)
globalStack.push (localStack.pop() );
} // end while isRowempty is false
System.out.println(
".......................");*/
}
void preOrder(Node current)
{
if (current != null)
{
System.out.println(current.data);
/*display*/preOrder(current.left);
/*display*/preOrder(current.right);
}
}
void inOrder(Node current)
{
if (current != null)
{
/*display*/inOrder(current.left);
System.out.println(current.data);
/*display*/inOrder(current.right);
}
}
//PreOrder traversal
// Displaying the tree after it has been organized
void postOrder(Node current)
{
if (current != null)
{
/*display*/postOrder(current.left);
/*display*/postOrder(current.right);
System.out.println(current.data);
}
}
// Update the node
/*private boolean update (NOT DONE YET)
// Finding the minimum
int findMin(Node node)
{
Node current = node;
if( node == null ){
return -1;
}
while (current.left != null)
{
current = current.left;
}
return (current.data);
}
// returning the Maximum
int findMax (Node node)
{
Node current = node;
if( node == null ){
return -1;
}
while (current.right != null)
{
current = current.right;
}
return (current.data);
}
// getting the Averagen(NOT DONE YET)
// getting the number on nodes
static int getNumberOfNodes(Node node) {
// empty trees have zero nodes
if( node == null ){
return 0;
}
// all other nodes count the nodes from their left and right subtree
// as well as themselves
return getNumberOfNodes( node.left ) + getNumberOfNodes( node.right ) + 1;
}
// Checking to see if the tree is balanced
public boolean isBalanced(Node node) {
if (node == null)
return true;
if (getHeight(node) == -1)
return false;
return true;
}
public int getHeight(Node node) {
if (node == null)
return 0;
int left = getHeight(node.left);
int right = getHeight(node.right);
if (left == -1 || right == -1)
return -1;
if (Math.abs(left - right) > 1) {
return -1;
}
return Math.max(left, right) + 1;
}
CANT modify the BinaryTreeTester Class (LEave as is):
package binarytreetester;
/**
* Do not modify anything inside this class.
*/
public class BinaryTreeTester
{
public static void main(String[] args)
{
BinaryTree t1 = new BinaryTree();
// Test insert functions
t1.insert(100);
t1.insert(50);
t1.insert(175);
t1.insert(200);
t1.insert(150);
// Test displayInOrder and displayPreOrder
System.out.println("InOrder: ");
t1.inOrder();
System.out.println("PreOrder: ");
t1.preOrder();
// Test search function
Node searchNode = t1.search(150);
if (searchNode != null)
System.out.println("150 Found");
else
System.out.println("150 Not Found");
searchNode = t1.search(10);
if (searchNode != null)
System.out.println("10 Found");
else
System.out.println("10 Not Found");
// Test delete function
System.out.println();
t1.insert(160);
t1.insert(170);
t1.insert(155);
t1.insert(158);
t1.preOrder();
// Leaf remove test
if (t1.remove(200) == true)
System.out.println("200 was found and removed");
else
System.out.println("200 was not found");
t1.preOrder();
// Not found remove test
if (t1.remove(1) == true)
System.out.println("1 was found and removed");
else
System.out.println("1 was not found");
// One child remove test
if (t1.remove(155) == true)
System.out.println("155 was found and removed");
else
System.out.println("155 was not found");
t1.preOrder();
// Two children at root remove test
if (t1.remove(100) == true)
System.out.println("100 was found and removed");
else
System.out.println("100 was not found");
t1.preOrder();
// End given functions testing
// Update test 1 - node not found
if (t1.update(1000, 20) == true)
System.out.println("1000 was changed to 20");
else
System.out.println("1000 was not changed to 20");
// Update test 2 - node found
if (t1.update(160, 25) == true)
System.out.println("160 was changed to 25");
else
System.out.println("160 was not changed to 25");
t1.preOrder();
// Update test 3 - node found and changed root
if (t1.update(150, 75) == true)
System.out.println("150 was changed to 75");
else
System.out.println("150 was not changed to 75");
t1.preOrder();
// Math functions test
System.out.println("Math functions test");
System.out.println(t1.findMin());
System.out.println(t1.findMax());
System.out.println(t1.calculateAverage());
System.out.println(t1.getNumberOfNodes());
// Balance test 1
if (t1.isBalanced())
System.out.println("Tree is balanced");
else
System.out.println("Tree is not balanced");
// Balance test 2
t1.insert(171);
t1.insert(172);
t1.insert(173);
t1.preOrder();
if (t1.isBalanced())
System.out.println("Tree is balanced");
else
System.out.println("Tree is not balanced");
}
}
}
Node Class:
public class Node {
/* public int iData; // data item key
public double dData; // data item
public Node leftChild; // the node'e left child
public Node rightChild; // Nodes right child*/
int data;
public Node left;
public Node right;
public Node last;
/* public void displayNode()
{
System.out.print('{');
System.out.print(iData);
System.out.print(" , ");
System.out.print(dData);
System.out.print("} ");
}*/
}
Explanation / Answer
Please find my implementation.
#############
public class BinaryTree {
// insert function
private Node root;
public BinaryTree()
{
root = null;
}
public void insert(int n)
{
Node current = root;
Node newNode = new Node();
newNode.data = n;
newNode.left = null;
newNode.right = null;
if (root == null)
root = newNode;
else
while(true)
if (newNode.data > current.data)
if (current.right == null)
{
current.right = newNode;
break;
}
else
current = current.right;
else
if (current.left == null)
{
current.left = newNode;
break;
}
else
current = current.left;
}
// Search function
public Node search(int n)
{
Node current = root; // assign node to root
while (current != null)
if (current.data == n)
return current;
else if (current.data > n) //greater than n we go to the left
current = current.left;
else
current = current.right;
return null;
}
// Delete Function below
public boolean remove(int n)
{
// Check empty tree
if (root == null)
return false;
// Prepare search for node
Node current = root;
Node parent = root;
boolean currentIsLeft = true;
// At this point, current is the node to delete
// Now, we check for the situations
// Situation 1 - leaf node
if (current.left == null && current.right == null)
// Check if current node is root
if (parent == current)
root = null;
// Check which child pointer of parent to set
else if (currentIsLeft)
parent.left = null;
else
parent.right = null;
// Situation 2 - one child. Parent inherits child
// or if current is root, root takes child
else if (current.left == null)
if (parent == current)
root = current.right;
else if (currentIsLeft)
parent.left = current.right;
else
parent.right = current.right;
else if (current.right == null)
if (parent == current)
root = current.left;
else if (currentIsLeft)
parent.left = current.left;
else
parent.right = current.left;
// Situation 3: two children
else
{
Node successor = getSuccessor(current);
// Replace current node with successor
if (parent == current)
root = successor;
else if (currentIsLeft)
parent.left = successor;
else
parent.right = successor;
// Successor will always come from the right, so
// it must also take deleted node’s left child
successor.left = current.left;
}
return true;
}
private Node getSuccessor(Node removedNode)
{
// Prepare successor search by keeping track
// of parent and current
Node successorParent = removedNode;
Node successor = removedNode;
Node current = successor.right;
// Starting at the right child of the node to be
// removed, go down the subtree’s left children
// until there are no more children on the left
while (current != null)
{
successorParent = successor;
successor = current;
current = current.left;
}
// if the successor is somewhere down the subtree,
// the parent’s left child must take the
// the successor’s right child. Then, the
// successor’s right child takes the node
// to delete’s right child (because successor will
// be replacing it.
if (successor != removedNode.right)
{
successorParent.left = successor.right;
successor.right = removedNode.right;
}
// Note that if the successor is the immediate
// right child of the node to delete, we just
// return that node (it has no left children and what
// ever is on successor’s right stays that way even
// after successor replaces the removed node.
return successor;
}
// Traversing a Tree
public void display()
{
inOrder(root);
/* 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 i = 0; i<nBlanks; i++)
System.out.print (" ");
while (globalStack.isEmpty()== false)
{
Node temp = (Node)globalStack.pop();
if (temp != null)
{
System.out.print (temp.data);
localStack.push(temp.left);
localStack.push(temp.right);
if (temp.left != null || temp.right != null)
isRowEmpty = false;
}
else
{
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for (int i=0 ; i<nBlanks*2-2; i++)
System.out.print(' ');
} // end while globlstack not empty
System.out.println();
nBlanks /= 2;
while (localStack.isEmpty() == false)
globalStack.push (localStack.pop() );
} // end while isRowempty is false
System.out.println(
".......................");*/
}
void preOrder()
{
preOrder(root);
}
void preOrder(Node current)
{
if (current != null)
{
System.out.println(current.data);
/*display*/preOrder(current.left);
/*display*/preOrder(current.right);
}
}
void inOrder()
{
inOrder(root);
}
void inOrder(Node current)
{
if (current != null)
{
/*display*/inOrder(current.left);
System.out.println(current.data);
/*display*/inOrder(current.right);
}
}
//PreOrder traversal
// Displaying the tree after it has been organized
void postOrder(Node current)
{
if (current != null)
{
/*display*/postOrder(current.left);
/*display*/postOrder(current.right);
System.out.println(current.data);
}
}
// Update the node
/*private boolean update (NOT DONE YET)*/
// Finding the minimum
int findMin(Node node)
{
Node current = node;
if( node == null ){
return -1;
}
while (current.left != null)
{
current = current.left;
}
return (current.data);
}
// returning the Maximum
int findMax (Node node)
{
Node current = node;
if( node == null ){
return -1;
}
while (current.right != null)
{
current = current.right;
}
return (current.data);
}
// getting the Averagen(NOT DONE YET)
// getting the number on nodes
int getNumberOfNodes(Node node) {
// empty trees have zero nodes
if( node == null ){
return 0;
}
// all other nodes count the nodes from their left and right subtree
// as well as themselves
return getNumberOfNodes( node.left ) + getNumberOfNodes( node.right ) + 1;
}
public int getHeight(Node node) {
if (node == null)
return 0;
int left = getHeight(node.left);
int right = getHeight(node.right);
if(left > right)
return 1+left;
else
return 1+right;
}
boolean update (int oldValue, int newValue){
return update(root, oldValue, newValue);
}
boolean update (Node node, int oldValue, int newValue){
if(node == null)
return false;
if(node.data == oldValue){
node.data = newValue;
return true;
}
if(node.data > oldValue)
return update(node.left, oldValue, newValue);
else
return update(node.right, oldValue, newValue);
}
int findMin(){
if(root == null)
return -1;
Node temp = root;
while(temp.left != null)
temp = temp.left;
return temp.data;
}
int findMax(){
if(root == null)
return -1;
Node temp = root;
while(temp.right != null)
temp = temp.right;
return temp.data;
}
double calculateAverage(){
double sum = calculateAverage(root);
int n = getNumberOfNodes(root);
if(n == 0)
return 0;
else
return sum/n;
}
double calculateAverage(Node node){
if(node == null)
return 0;
return calculateAverage( node.left ) + calculateAverage( node.right ) + node.data;
}
int getNumberOfNodes(){
return getNumberOfNodes(root);
}
boolean isBalanced(){
return isBalanced(root);
}
/* Returns true if binary tree with root as root is height-balanced */
boolean isBalanced(Node node)
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */
/* If tree is empty then return true */
if (node == null)
return true;
/* Get the height of left and right sub trees */
lh = getHeight(node.left);
rh = getHeight(node.right);
if (Math.abs(lh - rh) <= 1
&& isBalanced(node.left)
&& isBalanced(node.right))
return true;
/* If we reach here then tree is not height-balanced */
return false;
}
}
##################
public class BinaryTreeTester
{
public static void main(String[] args)
{
BinaryTree t1 = new BinaryTree();
// Test insert functions
t1.insert(100);
t1.insert(50);
t1.insert(175);
t1.insert(200);
t1.insert(150);
// Test displayInOrder and displayPreOrder
System.out.println("InOrder: ");
t1.inOrder();
System.out.println("PreOrder: ");
t1.preOrder();
// Test search function
Node searchNode = t1.search(150);
if (searchNode != null)
System.out.println("150 Found");
else
System.out.println("150 Not Found");
searchNode = t1.search(10);
if (searchNode != null)
System.out.println("10 Found");
else
System.out.println("10 Not Found");
// Test delete function
System.out.println();
t1.insert(160);
t1.insert(170);
t1.insert(155);
t1.insert(158);
t1.preOrder();
// Leaf remove test
if (t1.remove(200) == true)
System.out.println("200 was found and removed");
else
System.out.println("200 was not found");
t1.preOrder();
// Not found remove test
if (t1.remove(1) == true)
System.out.println("1 was found and removed");
else
System.out.println("1 was not found");
// One child remove test
if (t1.remove(155) == true)
System.out.println("155 was found and removed");
else
System.out.println("155 was not found");
t1.preOrder();
// Two children at root remove test
if (t1.remove(100) == true)
System.out.println("100 was found and removed");
else
System.out.println("100 was not found");
t1.preOrder();
// End given functions testing
// Update test 1 - node not found
if (t1.update(1000, 20) == true)
System.out.println("1000 was changed to 20");
else
System.out.println("1000 was not changed to 20");
// Update test 2 - node found
if (t1.update(160, 25) == true)
System.out.println("160 was changed to 25");
else
System.out.println("160 was not changed to 25");
t1.preOrder();
// Update test 3 - node found and changed root
if (t1.update(150, 75) == true)
System.out.println("150 was changed to 75");
else
System.out.println("150 was not changed to 75");
t1.preOrder();
// Math functions test
System.out.println("Math functions test");
System.out.println(t1.findMin());
System.out.println(t1.findMax());
System.out.println(t1.calculateAverage());
System.out.println(t1.getNumberOfNodes());
// Balance test 1
if (t1.isBalanced())
System.out.println("Tree is balanced");
else
System.out.println("Tree is not balanced");
// Balance test 2
t1.insert(171);
t1.insert(172);
t1.insert(173);
t1.preOrder();
if (t1.isBalanced())
System.out.println("Tree is balanced");
else
System.out.println("Tree is not balanced");
}
}
/*
Sample run:
InOrder:
50
100
150
175
200
PreOrder:
100
50
175
150
200
150 Found
10 Not Found
100
50
175
150
160
155
158
170
200
200 was found and removed
150
50
175
160
155
158
170
200
1 was found and removed
155 was found and removed
158
50
175
160
170
200
100 was found and removed
160
50
175
170
200
1000 was not changed to 20
160 was changed to 25
25
50
175
170
200
150 was not changed to 75
25
50
175
170
200
Math functions test
50
200
124.0
5
Tree is balanced
25
50
175
170
171
172
173
200
Tree is not balanced
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.