BST JAVA FILE import java.util.*; public class BST <E extends Comparable <E>> { private TreeNode<E>...
BST JAVA FILE
import java.util.*;
public class BST <E extends Comparable <E>> {
private TreeNode<E> overallRoot;
public BST() {
overallRoot = null;
}
// ************ ADD ************ //
public void add(E addThis) {
if (overallRoot == null) {
overallRoot =
new TreeNode<>(addThis);
} else {
add(overallRoot,
addThis);
}
}
private TreeNode<E> add(TreeNode<E>
node, E addThis) {
if (node == null) {
return new
TreeNode<>(addThis);
} else if
(node.data.compareTo(addThis) > 0) {
node.left =
add(node.left, addThis);
} else {
node.right =
add(node.right, addThis);
}
return node;
}
// ************ SEARCH ************ //
public TreeNode<E> search(E find) {
return search(overallRoot,
find);
}
private TreeNode<E> search(TreeNode<E>
node, E find) {
if (node == null ||
node.data.equals(find)) {
return
node;
} else if
(node.data.compareTo(find) > 0) {
return
search(node.left, find);
} else {
return
search(node.right, find);
}
}
// ************ REMOVE ************ //
public void remove(E deleteThis) {
overallRoot = remove(overallRoot,
deleteThis);
}
private TreeNode<E> remove(TreeNode<E>
node, E deleteThis) {
if (node == null) {
return null;
} else if (node.data.compareTo(deleteThis) > 0) {
node.left = remove(node.left, deleteThis);
} else if (node.data.compareTo(deleteThis) < 0)
{
node.right = remove(node.right,
deleteThis);
}
else { // if
(node.data.equals(deleteThis)) {
if (node.left == null) {
return node.right;
} else if
(node.right == null) {
return node.left;
} else {
node.data
= findMax(node.left);
node.left
= remove(node.left, node.data);
}
}
return node;
}
// Returns the largest value from this node + it's subtree
private E findMax(TreeNode<E> node) {
return null;
}
// ************ PRINT ************ //
public void print() {
System.out.print("In order = ");
printInorder(overallRoot);
System.out.println();
}
private void printInorder(TreeNode<E> root)
{
if (root != null) {
printInorder(root.left);
System.out.print(root.data + " ");
printInorder(root.right);
}
}
// ************ NORMAL BINARY TREE OPERATIONS
************ //
public int countLeaves() {
return
countLeaves(overallRoot);
}
private int countLeaves(TreeNode<E> node)
{
if (node == null) {
return 0;
} else if (node.left == null && node.right == null) {
return 1;
} else {
return
countLeaves(node.left) + countLeaves(node.right);
}
}
// Returns the number of nodes total in the tree
public int countNodes() {
return 0;
}
// Returns the number of children for this value
public int countChildren(E data) {
return 0;
}
// ************ BST OPERATIONS ************ //
public E max() {
return findMax(overallRoot);
}
public boolean isBST() {
return isBST(overallRoot);
}
private boolean isBST(TreeNode<E> node) {
if (node == null) {
return true;
} else {
boolean leftCheck = node.left == null ? true :
node.data.compareTo(node.left.data) > 0;
boolean rightCheck = node.right == null ? true :
node.data.compareTo(node.right.data) < 0;
return leftCheck && rightCheck && isBST(node.left)
&& isBST(node.right);
}
}
// Returns if the tree is balanced or not
public boolean isBalanced() {
return false;
}
// ========== MAIN ==========
public static void main(String[] args) {
int[] numbers = {20, 30, 5, 6};
int[] numbers2 = {13, 10, 5, -8, 2, 17, -4, 6};
int[] numbers3 = {5, 4, 7, 3, 9, 6};
BST<Integer> bst = new BST<>();
for(int n : numbers)
bst.add(n);
System.out.println("==== Tree Info ==== ");
bst.print();
System.out.println("Count of nodes = " + bst.countNodes());
System.out.println("The largest value in the tree is " + bst.max()
+ ".");
System.out.println("Node 5 has " + bst.countChildren(5) + "
children.");
System.out.println("Node 6 has " + bst.countChildren(6) + "
children.");
System.out.println("isBalanced? " + bst.isBalanced());
System.out.println("isBST? " + bst.isBST());
}
} //end of BST
--------------------------------------------------------------------------------------------------------------
BST TESTER
public class BSTTester {
public static void main(String[] args) {
int[] numbers = {20, 30, 5, 6};
int[] numbers2 = {13, 10, 5, -8, 2, 17, -4, 6};
int[] numbers3 = {5, 4, 7, 3, 9, 6};
BST<Integer> bst = new BST<>();
for(int n : numbers)
bst.add(n);
System.out.println("==== Tree Info ==== ");
bst.print();
System.out.println("Count of nodes = " + bst.countNodes());
System.out.println("The largest value in the tree is " + bst.max()
+ ".");
System.out.println("Node 5 has " + bst.countChildren(5) + "
children.");
System.out.println("Node 6 has " + bst.countChildren(6) + "
children.");
System.out.println("isBalanced? " + bst.isBalanced());
System.out.println("isBST? " + bst.isBST());
}
}
---------------------------------------------------------------------------------------------------------
TREE NODE
import java.util.*;
public class TreeNode<E extends Comparable<E>>
{
public E data;
public TreeNode<E> left;
public TreeNode<E> right;
// constructs a leaf node with given data
public TreeNode(E data) {
this(data, null, null);
}
// constructs a branch node with given data, left subtree, right
subtree
public TreeNode(E data, TreeNode<E> left, TreeNode<E>
right) {
this.data = data;
this.left = left;
this.right = right;
}
public int compareTo(TreeNode<E> other) {
return this.data.compareTo(other.data);
}
}
--------------------------------------------------------------------
Part 1: Check out BST
- Step through how add(addThis) works
- Step through remove(deleteThis)
Part 2: Add functionality to BST
- Write findMax(node)
- Check out countLeaves()
- Write countNodes()
- Write countChildren()
Offline
Part 3: More BST
- Add comments to add() and search() to show that you understand how those methods work
- Write isBalanced()
- Add a numbers4 to your main that generates a balanced BST with at least 4 levels.
What to Submit
- Your completed BST.java
- A screenshot of your built numbers4 BST from debug mode
Homework Answers
Summary :
This solution is provided with following :
1)Notes on implementation .
2) Code
3) output
Notes on Implementation :
Provided details notes and comments inline in the code in file BST.java after implementing the required functionality.
added getHeight() and isBalanced() functions for the isBalanced() function implementation .
Restructured the BSTTester.java code to test numberous arrays by introducing static method TestTree() which accepts a integer array .
############### Code ##############
BST.java
import java.util.*;
import java.math.*;
public class BST <E extends Comparable <E>> {
private TreeNode<E> overallRoot;
public BST() {
overallRoot = null;
}
// ************ ADD ************ //
/**
* This method takes help of recursive function add(TreeNode, E) ( which is also a overloaded function )
* to add an element with value addThis .
* @param addThis - The value to be added to the BST
*/
public void add(E addThis) {
// If the Root node is null insert the node and make it root node
if (overallRoot == null) {
overallRoot = new TreeNode<>(addThis);
} else {
// Take help of recursive add function to add the value - addThis at the right place
add(overallRoot, addThis);
}
}
/**
* This recursive function add the value - addThis under the give node by checking whether its value
* is greater or less than current given node - node and tries to add it to under its left subtree
* or right subtree .
* This recursive function ends when it reaches empty left or right subtree and inserts the node and returns its
* value otherwise it just returns the current node value .
* @param node - given node under which value needs to be added
* @param addThis - Given value that should be added to the BST
* @return - Returns the TreeNode where its added
*/
private TreeNode<E> add(TreeNode<E> node, E addThis) {
// If node is null the recursive function will
// create a new node add the value and return the value of Node
if (node == null) {
return new TreeNode<>(addThis);
} else if (node.data.compareTo(addThis) > 0) {
// In case addThis value is less than current node
// try to add it under left subtree
node.left = add(node.left, addThis);
} else {
// In case addThis value is greater than currentNode
//recursively try to add it under right sub tree
node.right = add(node.right, addThis);
}
return node;
}
// ************ SEARCH ************ //
/**
* This search method searches the given value 'find' in the given tree
* if success returns the node value else null
* @param find - Value to be found in the tree
* @return - TreeNode value
*/
public TreeNode<E> search(E find) {
// REcursively find for value - find in Tree with head - overallRoot
return search(overallRoot, find);
}
/**
* This function recursively searces for value - find under the tree pointed by
* given node . It check if the root node value matches the given values , else
* it checks to see whether to recursively search for left or right based on
* compareTo() value of given node and find value and accordingly searches in left subtree
* or right subtree .
* @param node
* @param find
* @return
*/
private TreeNode<E> search(TreeNode<E> node, E find) {
// If node is not null and node value is equal to find return the node itself
if (node == null || node.data.equals(find)) {
return node;
} else if (node.data.compareTo(find) > 0) {
// Search left subtree if the value of find < node data
return search(node.left, find);
} else {
// Search right subtree if the value of find > node data
return search(node.right, find);
}
}
// ************ REMOVE ************ //
public void remove(E deleteThis) {
overallRoot = remove(overallRoot, deleteThis);
}
private TreeNode<E> remove(TreeNode<E> node, E deleteThis) {
if (node == null) {
return null;
} else if (node.data.compareTo(deleteThis) > 0) {
node.left = remove(node.left, deleteThis);
} else if (node.data.compareTo(deleteThis) < 0) {
node.right = remove(node.right, deleteThis);
}
else { // if (node.data.equals(deleteThis)) {
if (node.left == null) {
return node.right;
} else if (node.right == null) {
return node.left;
} else {
node.data = findMax(node.left);
node.left = remove(node.left, node.data);
}
}
return node;
}
// Returns the largest value from this node + it's subtree
private E findMax(TreeNode<E> node)
{
TreeNode<E> tmpNode = node ;
while ( tmpNode.right != null )
{
tmpNode = tmpNode.right;
}
if ( tmpNode != null )
return tmpNode.data ;
else
return null;
}
// ************ PRINT ************ //
public void print() {
System.out.print("In order = ");
printInorder(overallRoot);
System.out.println();
}
private void printInorder(TreeNode<E> root) {
if (root != null) {
printInorder(root.left);
System.out.print(root.data + " ");
printInorder(root.right);
}
}
// ************ NORMAL BINARY TREE OPERATIONS ************ //
public int countLeaves() {
return countLeaves(overallRoot);
}
private int countLeaves(TreeNode<E> node) {
if (node == null) {
return 0;
} else if (node.left == null && node.right == null) {
return 1;
} else {
return countLeaves(node.left) + countLeaves(node.right);
}
}
// Returns the number of nodes total in the tree
public int countNodes() {
return countNodes(overallRoot);
}
public int countNodes( TreeNode<E> thisNode )
{
if ( thisNode == null )
return 0 ;
int numNodes_LeftSide = 0 ;
int numNodes_RightSide = 0 ;
if ( thisNode.left != null )
numNodes_LeftSide = countNodes(thisNode.left);
if ( thisNode.right != null )
numNodes_RightSide = countNodes(thisNode.right);
//System.out.format(" %d %d \n", numNodes_LeftSide,numNodes_RightSide);
return 1 + numNodes_LeftSide + numNodes_RightSide;
}
// Returns the number of children for this value
public int countChildren(E data) {
TreeNode<E> tmpNode = search( data );
return countNodes(tmpNode) - 1;
}
// ************ BST OPERATIONS ************ //
public E max() {
return findMax(overallRoot);
}
public boolean isBST() {
return isBST(overallRoot);
}
private boolean isBST(TreeNode<E> node) {
if (node == null) {
return true;
} else {
boolean leftCheck = node.left == null ? true : node.data.compareTo(node.left.data) > 0;
boolean rightCheck = node.right == null ? true : node.data.compareTo(node.right.data) < 0;
return leftCheck && rightCheck && isBST(node.left) && isBST(node.right);
}
}
// Returns if the tree is balanced or not
public boolean isBalanced() {
return isBalanced(overallRoot);
}
/**
* This method recursively finds whether left subtree is balanced
* and right subtree is balanced in addition checks if left subtree Height
* and right Subtree height diff is not > 1 to return True
*
* @param node
* @return
*/
private boolean isBalanced(TreeNode<E> node )
{
if ( node == null )
return true ;
int leftHeight = getHeight(node.left);
int rightHeight = getHeight(node.right);
if (( Math.abs( leftHeight - rightHeight ) <= 1 )
& isBalanced(node.left) & isBalanced(node.right))
return true ;
return false;
}
/**
* This method recursively finds the height of left subtree
* and right subtree and returns by checking max of both the tree
* as height of the tree of given node
* @param node
* @return
*/
private int getHeight(TreeNode<E> node )
{
if ( node == null )
return 0 ;
else
{
int leftHeight = getHeight(node.left) ;
int rightHeight = getHeight(node.right);
if ( leftHeight > rightHeight)
return 1 + leftHeight ;
else
return 1 + rightHeight;
}
}
// ========== MAIN ==========
public static void main(String[] args) {
int[] numbers = {20, 30, 5, 6 };
int[] numbers2 = {13, 10, 5, -8, 2, 17, -4, 6};
int[] numbers3 = {5, 4, 7, 3, 9, 6};
BST<Integer> bst = new BST<>();
for(int n : numbers)
bst.add(n);
System.out.println("==== Tree Info ==== ");
bst.print();
System.out.println("Count of nodes = " + bst.countNodes());
System.out.println("The largest value in the tree is " + bst.max() + ".");
System.out.println("Node 5 has " + bst.countChildren(5) + " children.");
System.out.println("Node 6 has " + bst.countChildren(6) + " children.");
System.out.println("isBalanced? " + bst.isBalanced());
System.out.println("isBST? " + bst.isBST());
}
} //end of BST
###
BSTTester.java
###
//BST TESTER
import java.util.Random;
public class BSTTester {
public static void TestTree( int[] numbers )
{
Random rand = new Random();
BST<Integer> bst = new BST<>();
for(int n : numbers)
bst.add(n);
Add Answer to:
BST JAVA FILE
import java.util.*;
public class BST <E extends Comparable <E>> {
private TreeNode<E>...
The code is in JAVA public class CheckBST { //method to implement public static boolean isValidBST(TreeNode...
The code is in JAVA
public class CheckBST {
//method to implement
public static boolean isValidBST(TreeNode root) {
}
public static void main(String[] args) {
TreeNode a = new TreeNode(1);
TreeNode b = new TreeNode(2);
TreeNode c = new TreeNode(3);
a.left = b;
a.right = c;
System.out.println(isValidBST(a));
TreeNode d = new TreeNode(2);
TreeNode e = new TreeNode(1);
TreeNode f = new TreeNode(3);
d.left = e;
d.right = f;
System.out.println(isValidBST(d));
}
}
TreeNode.java
class TreeNode {
int val;
TreeNode left;
TreeNode...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to com...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to completely test every method in the BST class to ensure the class meets all its requirements. You should read the Listing 25.5: TestBST.java for an idea of what your program should look like. Listing 25.4 BST.java public class BST> extends AbstractTree { protected TreeNode...
using java to write,show me the output. please write some common. You CAN NOT use inbuild...
using java to write,show me the output. please write some
common.
You CAN NOT use inbuild functions for Tree ADT operations.
using code below to finsih
public class Main
{
public static void main(String[] args) {
BinaryTree tree = new
BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
tree.root.left.left.left = new Node(8);
tree.root.left.left .right= new Node(9);...
write a new test program called RemoveDuplicates.java. The program reads text input from keyboard or a text file and adds the words to a BST. The program then traverses the BST and prints out the word...
write a new test program called RemoveDuplicates.java. The program reads text input from keyboard or a text file and adds the words to a BST. The program then traverses the BST and prints out the words in order (based on ASCII/UNICODE order) on the screen (or to output text file). Note that you may need to make some changes to BST.java. Sample test: ----jGRASP exec: java -ea removeDuplicates Original Text: a B 2 n w C q K l 0...
CAN SOMEONE PLEASE SOLVE THIS? THANK YOU. FINALTREE.JAVA: import java.util.LinkedList; public class FinalTree<E extends Comparable<? super...
CAN SOMEONE PLEASE SOLVE THIS? THANK YOU.
FINALTREE.JAVA:
import java.util.LinkedList;
public class FinalTree<E extends Comparable<? super E>> {
private Node<E> root;
private int size;
public FinalTree() {
root = null;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public void add(E newItem) {
if (isEmpty()) {
root = new Node<E>(newItem);
} else {
Node<E> parent = null;
Node<E> temp = root;
int result = 0;
while (temp != null) {
parent = temp;
result =...
package hw3; import java.util.LinkedList; /* *********************************************************************** * A simple BST with int keys and no values...
package hw3; import java.util.LinkedList; /* *********************************************************************** * A simple BST with int keys and no values * * Complete each function below. * Write each function as a separate recursive definition (do not use more than one helper per function). * Depth of root==0. * Height of leaf==0. * Size of empty tree==0. * Height of empty tree=-1. * * TODO: complete the functions in this file. * DO NOT change the Node class. * DO NOT change the name...
TreeNode.java public class TreeNode { public int key; public TreeNode p; public TreeNode...
TreeNode.java
public class TreeNode {
public int key;
public TreeNode p;
public TreeNode left;
public TreeNode right;
public TreeNode () {
p = left = right = null;
}
public TreeNode (int k) {
key = k;
p = left = right = null;
}
}
BinarySearchTree.java
public class BinarySearchTree {
public TreeNode root;
public BinarySearchTree () {
root...
Java help! Please help complete the min method below in bold. import java.util.Arrays; import java.util.ArrayList; import...
Java help! Please help complete the min method below in bold. import java.util.Arrays; import java.util.ArrayList; import java.util.Collections; import java.util.Iterator; import java.util.List; /** * Provides an implementation of a binary search tree * with no balance constraints, implemented with linked nodes. * * * */ public class Bst<T extends Comparable<T>> implements Iterable<T> { ////////////////////////////////////////////////////////////////// // I M P L E M E N T T H E M I N M E T H O D B E L O W...
I need to do a tree sort method but the treesortMethod is not working /****Binarytree class****\...
I need to do a tree sort method but the treesortMethod is not working /****Binarytree class****\ package Tree; public class BinaryTree { private TreeNode root; // head of the list //constructor - create an empty binary tree public BinaryTree() { root = null; } //isEmpty() - return true if tree is empty, false otherwise public boolean isEmpty() { return (root == null); } //deleteTree() - remove all items from tree public void deleteList() { root =...
Adapt the provided program to recreate the following tree: import java.util.ArrayList; import java.util.List; public class TreeNode<T>{ public T data = null; private List<TreeNode> childr...
Adapt the provided program to recreate the following tree: import java.util.ArrayList; import java.util.List; public class TreeNode<T>{ public T data = null; private List<TreeNode> children = new ArrayList<>(); private TreeNode parent = null; public TreeNode() { } public TreeNode(T data) { this.data = data; } public TreeNode<T> addChild(TreeNode child) { child.setParent(this); this.children.add(child); return child; } public TreeNode<T> addChild(T data) { TreeNode<T> newChild = new TreeNode<>(data); newChild.setParent(this); children.add(newChild); return newChild; } public void addChildren(List<TreeNode> children) { for(TreeNode t : children) { t.setParent(this);...
The code is in JAVA
public class CheckBST {
//method to implement
public static boolean isValidBST(TreeNode root) {
}
public static void main(String[] args) {
TreeNode a = new TreeNode(1);
TreeNode b = new TreeNode(2);
TreeNode c = new TreeNode(3);
a.left = b;
a.right = c;
System.out.println(isValidBST(a));
TreeNode d = new TreeNode(2);
TreeNode e = new TreeNode(1);
TreeNode f = new TreeNode(3);
d.left = e;
d.right = f;
System.out.println(isValidBST(d));
}
}
TreeNode.java
class TreeNode {
int val;
TreeNode left;
TreeNode...
using java to write,show me the output. please write some
common.
You CAN NOT use inbuild functions for Tree ADT operations.
using code below to finsih
public class Main
{
public static void main(String[] args) {
BinaryTree tree = new
BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
tree.root.left.left.left = new Node(8);
tree.root.left.left .right= new Node(9);...
CAN SOMEONE PLEASE SOLVE THIS? THANK YOU.
FINALTREE.JAVA:
import java.util.LinkedList;
public class FinalTree<E extends Comparable<? super E>> {
private Node<E> root;
private int size;
public FinalTree() {
root = null;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public void add(E newItem) {
if (isEmpty()) {
root = new Node<E>(newItem);
} else {
Node<E> parent = null;
Node<E> temp = root;
int result = 0;
while (temp != null) {
parent = temp;
result =...
TreeNode.java
public class TreeNode {
public int key;
public TreeNode p;
public TreeNode left;
public TreeNode right;
public TreeNode () {
p = left = right = null;
}
public TreeNode (int k) {
key = k;
p = left = right = null;
}
}
BinarySearchTree.java
public class BinarySearchTree {
public TreeNode root;
public BinarySearchTree () {
root...
Most questions answered within 3 hours.
-
The factory method and the abstract factory pattern use
different object oriented
mechanisms are used to...
asked 1 hour ago -
Given the data below for the monthly sales data at each branch in
your region for...
asked 2 hours ago -
Blossom Company owns 10000 of the 50000 outstanding shares of
Taylor, Inc. common stock. During 2018,...
asked 3 hours ago -
Calculate the following: ***SHOW ALL WORK!!!! Or
NO CREDIT*** Circle your answers. 8pts
each
In the...
asked 5 hours ago -
Bank Z is currently advertising interest rates on its checking
account. They claim to pay an...
asked 4 hours ago -
List two ways of transformation on the response variable that
can be used to deal with...
asked 5 hours ago -
If a 2000 ohm resistor has a -3.90 mA current going through it.
What is the...
asked 5 hours ago -
Please comment on the sentences.
Some types of jobs require more training than others. Some
companies...
asked 6 hours ago -
The )G01 for the hydrolysis of phosphorarginine
reaction depicted below is –32 kJ mol-1.
Phosphoarginine ...
asked 7 hours ago -
Cross a heterozygous blue-eyed goat with a homozygous brown-eyed
goat. Be sure to indicate which kids...
asked 7 hours ago -
Use the following information to answer the next two
questions.
Please refer to question 9-90. A...
asked 7 hours ago -
A solution containing 0.050 g of an unknown electrolyte in 2.50
g of cyclohexane was found...
asked 8 hours ago