Question
I am hoping I can get some help from. I am new to Java. And I am tasked with completing some methods for a Binary
I am hoping I can get some help from. I am new to Java. And I am tasked with completing some methods for a Binary Tree. I Can't modify the "Main" class (code was given). Can only declare the methods in the "BinaryTree" Class. I have a bunch of errrors in the "Main" class, which means my methods are wrong. I can't seem to get them to work just right. So, I hope someone here can help me with this.
Here is the code(main):
/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */
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"); } }
BinaryTree Class:
package binarytreetester;
import java.util.Stack;
/**
*
* @author Manuel
*/
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 nodes 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 subtrees 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 parents left child must take the
// the successors right child. Then, the
// successors right child takes the node
// to deletes 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 successors right stays that way even
// after successor replaces the removed node.
return successor;
}
// Traversing a Tree
public void display()
{
inOrder(root);
}
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);
}
}
// 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 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;
}
I am tasked with completing these 6 methods:
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:
I am missing the Update Method and average method. Don't even know how to even start it. But I can't even get what I have to run without errors. I need helping building those 6 methods and running the program successfully and not modifying the "Main" class.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started