I am hoping I can get some help from. I am new to Java. And I am tasked with com
ID: 3834703 • Letter: I
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 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 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);
}
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.
Explanation / Answer
check the following code
import java.io.*;
import java.util.*;
public class BinaryTree {
/** Root of the Binary Tree */
Node root;
public static void main(String[] args){
BinaryTreeTest sample = new BinaryTreeTest();
}
/** Build a binary tree
*
*/
public void createBinaryTree(){
root = new Node(50);
root.leftChild = new Node(25);
root.rightChild = new Node(75);
root.leftChild.leftChild = new Node(20);
root.leftChild.rightChild = new Node(30);
root.leftChild.leftChild.leftChild = new Node(19);
root.leftChild.leftChild.rightChild = new Node(21);
root.leftChild.rightChild.leftChild = new Node(29);
root.leftChild.rightChild.rightChild = new Node(31);
root.rightChild.leftChild = new Node(70);
root.rightChild.rightChild = new Node(80);
}
/** Inorder traversal
* left->root->right
*
* @param Node
* @return void
*/
public void inOrder(Node node){
if (node==null){
return;
}
inOrder(node.leftChild);
System.out.println(node.key);
inOrder(node.rightChild);
}
/** Preorder traversal
* root->left->right
*
* @param Node
* @return void
*/
public void preOrder(Node node){
if (node==null){
return;
}
System.out.println(node.key);
preOrder(node.leftChild);
preOrder(node.rightChild);
}
/** Postorder traversal
* left->right->node
*
* @param Node
* @return void
*/
public void postOrder(Node node){
if (node==null){
return;
}
postOrder(node.leftChild);
postOrder(node.rightChild);
System.out.println(node.key);
}
/** In order without using recursion
*/
public void inOrderItr(){
if(root==null){
return;
}
/*Steps for iterative solution:
1. Create an empty stack s and Initialize current node as root
2. Push the current node to s and set currentNode = currentNode.left until currentNode is NULL
If currentNode is NULL and s is not empty then
Pop the top node from stack and print it
set currentNode = currentNode.right
go to step 2
3. If stack is empty and currentNode is also null then we are done with it
*/
Stack<Node> stack = new Stack<Node>();
Node currentNode = root;
while(!stack.isEmpty() || currentNode != null){
if(currentNode != null){
stack.push(currentNode);
currentNode = currentNode.leftChild;
}else{
currentNode = stack.pop();
System.out.println(currentNode.key);
currentNode = currentNode.rightChild;
}
}
}
/** Pre order without using recursion
*/
public void preOrderItr(){
if (root == null){
return;
}
/*Steps for iterative solution:
1. Create empty stack and pust root node to it.
2. Do the following when stack is not empty
Pop a node from stack and print it
Push right child of popped node to stack
Push left child of popped node to stack
*/
Stack<Node> stack = new Stack<Node>;
stack.push(root);
while(!stack.isEmpty()){
Node currentNode = stack.pop();
System.out.println(currentNode.key);
if(currentNode.rightChild != null){
stack.push(currentNode.rightChild);
}
if(currentNode.leftChild != null){
stack.push(currentNode.leftChild);
}
}
}
public void postOrderItr(){
if (root == null){
return;
}
Stack<Node> stack = new Stack<Node>();
Node currentNode = root;
while(true){
if(currentNode != null){
if(currentNode.rightChild != null){
stack.push(currentNode.rightChild);
}
stack.push(currentNode);
currentNode = currentNode.leftChild;
continue;
}
if(stack.isEmpty()){
return;
}
currentNode = stack.pop();
if(currentNode.rightChild != null && !stack.isEmpty() && currentNode.rightChild == stack.peek()){
stack.pop();
stack.push(currentNode);
currentNode = currentNode.rightChild;
}else{
System.out.println(currentNode.key);
currentNode = null;
}
}
}
}
class Node {
Node leftChild;
Node rightChild;
int key;
Node(){
this.key = -1;
this.leftChild = null;
this.rightChild = null;
}
Node(int key){
this.key = key;
this.leftChild = null;
this.rightChild = null;
}
}
/** Test all functions of BinaryTree class
*
* @author Santhosh Kumar
*/
class BinaryTreeTest() {
//Create a test binary tree;
BinaryTree testBinaryTree = BinaryTree();
//Build a befault tree with data nodes.
testBinaryTree.createBinaryTree();
System.out.println("Inorder Traversal");
testBinaryTree.inOrder(tetBinaryTree.root);
System.out.println("PreOrder Traversal");
testBinaryTree.preOrder(testBinaryTree.root);
System.out.println("PostOrder Traversal");
testBinaryTree.postOrder(testBinaryTree.root);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.