Complete in Java : Question 2: Write a program that can convert a sorted array into...
Complete in Java :
Question 2: Write a program that can convert a sorted array into a balanced binary search tree. A binary search tree is a balanced binary search tree if the size of the left and right subtree at each node differs by at most one. The size of the left subtree is defined as the number of nodes in the left subtree. The size of the right subtree is defined as the number of nodes in the right subtree.
Homework Answers
import java.util.*;
import java.io.*;
class BSTNode<T> {
BSTNode left, right;
T data;
/* Constructor */
public BSTNode()
{
left = null;
right = null;
}
/* Constructor */
public BSTNode(T n)
{
left = null;
right = null;
data = n;
}
/* Function to set left node */
public void setLeft(BSTNode n)
{
left = n;
}
/* Function to set right node */
public void setRight(BSTNode n)
{
right = n;
}
/* Function to get left node */
public BSTNode getLeft()
{
return left;
}
/* Function to get right node */
public BSTNode getRight()
{
return right;
}
/* Function to set data to node */
public void setData(T d)
{
data = d;
}
/* Function to get data from node */
public T getData()
{
return data;
}
}
class BinarySearchTree <T extends Comparable<T>>
{
private BSTNode<T> root;
private int size;
private Comparator<T> comparator;
public BinarySearchTree()
{
root = null;
size = 0;
comparator = null;
}
public int Size()
{
return size;
}
private int compare(T x, T y)
{
if(comparator == null)
return x.compareTo(y);
return comparator.compare(x,y);
}
/* ***************************************************************
* Insert a new node
* Returns true on successful insert otherwise false (when already present)
*****************************************************************/
public boolean insert(T data)
{
if( this.search(data) )
return false;
//TODO -> implement here
root = insert_util(root, data);
size++;
return true;
}
/* Function to insert data recursively */
private BSTNode insert_util(BSTNode<T> node, T data)
{
// if(node != null)
// System.out.println(compare(node.getData(), data));
// if tree is empty
if (node == null)
// create a new node
node = new BSTNode<T>(data);
// if the dat lies in the right subtree
else if (compare(node.getData(), data) < 0)
node.setRight(insert_util(node.getRight(), data));
// if the dat lies in the left subtree
else
node.setLeft(insert_util(node.getLeft(), data));
return node;
}
public boolean search(T val)
{
return search_util( this.root , val );
}
// search an element in the tree
private boolean search_util(BSTNode<T> r, T val)
{
if (r == null)
return false;
else if (compare(val, r.data) == 0)
return true;
else if (compare(val, r.data) < 0)
return search_util(r.left, val);
else
return search_util(r.right, val);
}
// get the node with minimum value
public BSTNode<T> getMin(BSTNode<T> x)
{
// moke trav point to the root of the tree
BSTNode trav = x;
// go tp the node at the extreme left
while (trav.getLeft() != null)
// move to the left child
trav = trav.getLeft();
return trav;
}
/*****************************************************************
* Delete a node
* Returns true on successful deletion and false otherwise
*****************************************************************/
public boolean delete(T data)
{
boolean found = search_util(root, data);
// if data is not present in the tree
if(found == false)
return found;
//TODO -> Implement here
BSTNode temp = root;
root = delete_util(temp, data);
size--;
return true;
}
// delete the given node
BSTNode<T> delete_util(BSTNode<T> x, T key)
{
// if the tree is empty
if(x == null)
return null;
// if the required node lies in the left subtree
//if (key < x.getData())
if (compare(key, x.getData()) < 0)
// recursively call the function on the left subtree
x.setLeft(delete_util(x.getLeft(), key));
// if the required node lies in the right subtree
//else if (key > x.getData())
else if (compare(key, x.getData()) > 0)
// recursively call the function on the right subtree
x.setRight(delete_util(x.getRight(), key));
// if the node to be deleted is found
else
{
// left child is not present
if (x.getLeft() == null)
return x.getRight();
// right child is not present
else if (x.getRight() == null)
return x.getLeft();
// no child is present
// get the node with the minimum value
BSTNode<T> trav = getMin(x.getRight());
// content of inorder successor is set to this node
x.setData(trav.getData());
// inorder successor is removed
x.setRight(delete_util(x.getRight(), trav.getData()));
}
return x;
}
/****************************************************************
*
* Reset Tree
*
***************************************************************/
public void reset()
{
root = null;
size=0;
}
/*****************************************************************
*
* Height of tree
*
****************************************************************/
public int height()
{
//TODO -> Implement here
return getHeight(root);
}
// get the height of the tree
public int getHeight(BSTNode<T> x)
{
// if tree is empty
if (x == null)
return 0;
else
{
// calculate height of right subtree
int r = getHeight(x.getRight());
// calculate height of left subtree
int l = getHeight(x.getLeft());
// if the height of left subtree is larger
if (l > r)
return(l + 1);
// if the height of right subtree is larger
return(r + 1);
}
}
/*****************************************************************
*
* Traversal
*
******************************************************************/
public void inorder()
{
System.out.print("inorder BST: ");
//TODO -> Implement here (print all nodes)
inorder_util(root);
System.out.println();
}
private void inorder_util(BSTNode<T> r)
{
if (r != null)
{
inorder_util(r.getLeft());
System.out.print(r.getData() +" ");
inorder_util(r.getRight());
}
}
public void preorder()
{
System.out.print("preorder BST: ");
//TODO -> Implement here
preorder_util(root);
System.out.println();
}
private void preorder_util(BSTNode<T> r)
{
if (r != null)
{
System.out.print(r.getData() +" ");
preorder_util(r.getLeft());
preorder_util(r.getRight());
}
}
public void postorder()
{
System.out.print("postorder BST: ");
//TODO -> Implement here
postorder_util(root);
System.out.println();
}
private void postorder_util(BSTNode<T> r)
{
if (r != null)
{
postorder_util(r.getLeft());
postorder_util(r.getRight());
System.out.print(r.getData() +" ");
}
}
public void convertArrayToBinarySearchTree(int[] array)
{
this.root = this.convertArrayToBinarySearchTreeUtil(array, 0, array.length - 1);
}
// p is the left bound index
// r is the right bound index
public BSTNode convertArrayToBinarySearchTreeUtil(int[] array, int p, int r)
{
if( p <= r )
{
// calculate the index of middle element
int mid = ( p + r ) / 2;
// create a new node with the middle element as the value
BSTNode x = new BSTNode( array[mid] );
// recursively build the left subtree
x.setLeft( this.convertArrayToBinarySearchTreeUtil(array, p, mid - 1) );
// recursively build the right subtree
x.setRight( this.convertArrayToBinarySearchTreeUtil(array, mid + 1, r) );
return x;
}
else
return null;
}
}
public class Solution
{
public static void main(String[] args)
{
// create an object of class binary Search Tree to store each element
BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
// sorted array
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
bst.convertArrayToBinarySearchTree(arr);
bst.inorder();
}
}
Sample output
Add Answer to:
Complete in Java :
Question 2: Write a program that can convert a sorted array into...
The goal of this assignment is to reinforce the tree data structure in C++. Specifically, the...
The goal of this assignment is to reinforce the tree data structure in C++. Specifically, the assignment is to do the following: Binary search trees have their best performance when they are balanced, which means that at each node, n, the height of the left subtree of n is within one of the height of the right subtree of n. Write a function (and a test program) which takes a sorted list of entries and produces a balanced binary search...
Write Prolog rules as described in the questions below. You may use any Prolog builtin predicates....
Write Prolog rules as described in the questions below. You may use any Prolog builtin predicates. A binary tree is defined by the structure node(left,right), where left and right can be either another node or any Prolog data item. Write the rule isBalanced(Tree) that determines if the tree is balanced. A binary tree is balanced if, at every node, the difference between the number of leaves appearing in the left and right subtree is at most one. (A tree which...
Would appreciate the answer in the Java coding language please and thank you! 10d 10h left...
Would appreciate the answer in the Java coding language please
and thank you!
10d 10h left Java 7 1. Check the Structure Autocomplete Ready 1 > import java.io.*;... 10 ALL A binary tree uses a multi-node data structure where each node may have 0 to 2 child nodes, and has one stored value, its node number in this case. A tree may either be: 11 class Result { * Complete the 'isValid' function below. • An empty tree, the root...
In Java: Given the following binary tree class, write a recursive method called size() which will...
In Java: Given the following binary tree class, write a recursive method called size() which will find the number of nodes in the subtree rooted at the current node: class myBinaryTree{ int myValue; myBinaryTree left; myBinaryTree right; myBinaryTree(int inValue) {myValue = inValue;} public int size(){ <CODE WRITTEN HERE> } }
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);...
(true/false) All nodes in the right subtree of a node must be smaller in value than...
(true/false) All nodes in the right subtree of a node must be smaller in value than their parent (true/false) Each node in a binary search tree may contain zero, one, or two children nodes. (true/false) It is possible to recursively process a binary search tree to print all the data in a binary search tree in sorted order. (true/false) The value of a parent must be less than all its children. (true/false) All nodes in the right subtree of a...
Tree Plot Please write a Java program to print or plot a binary tree in a 2-dimensional character format. You are not...
Tree Plot Please write a Java program to print or plot a binary tree in a 2-dimensional character format. You are not allowed to use any existing Java classes such as ArrayList or Vector or Tree. Your program must define 3 binary trees as follows. Each tree is defined in an integer 16 x 3 array. Programming Techniques: (1) The array for the binary tree can be integer data type with 16 rows by 3 columns. Please always make index...
Can someone help with these two problems? The following binary tree contains the characters 'A' through...
Can someone help with these two problems?
The following binary tree contains the characters 'A' through 'G' in its nodes. List the nodes in the order that they are visited by: A preorder traversal. An inorder traversal. A postorder traversal. The binary tree in Problem 2 is a Binary Search Tree since for every node, all elements stored in the left subtree of the node are smaller than the element in the node and all elements stored in the right...
Tree Plot Please write a Java program to print or plot a binary tree in a 2-dimensional character format. You are n...
Tree Plot Please write a Java program to print or plot a binary tree in a 2-dimensional character format. You are not allowed to use any existing Java classes such as ArrayList or Vector or Tree. Your program must define 3 binary trees as follows. Each tree is defined in an integer 16 x 3 array. Programming Techniques: (1) The array for the binary tree can be integer data type with 16 rows by 3 columns. Please always make index...
A Binary Search Tree is a binary tree where nodes are ordered in the following way:...
A Binary Search Tree is a binary tree where nodes are ordered in the following way: each node contains one key (also known as data) the keys in the left subtree are less than the key in its parent node the keys in the right subtree are greater than the key in its parent node duplicate keys are not allowed Create a Binary Search Tree inserting the following list of numbers in order from left to right. 10, 6, 4, 8, 18, 15, 21 Please type...
The goal of this assignment is to reinforce the tree data structure in C++. Specifically, the assignment is to do the following: Binary search trees have their best performance when they are balanced, which means that at each node, n, the height of the left subtree of n is within one of the height of the right subtree of n. Write a function (and a test program) which takes a sorted list of entries and produces a balanced binary search...
Would appreciate the answer in the Java coding language please
and thank you!
10d 10h left Java 7 1. Check the Structure Autocomplete Ready 1 > import java.io.*;... 10 ALL A binary tree uses a multi-node data structure where each node may have 0 to 2 child nodes, and has one stored value, its node number in this case. A tree may either be: 11 class Result { * Complete the 'isValid' function below. • An empty tree, the root...
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);...
(true/false) All nodes in the right subtree of a node must be smaller in value than their parent (true/false) Each node in a binary search tree may contain zero, one, or two children nodes. (true/false) It is possible to recursively process a binary search tree to print all the data in a binary search tree in sorted order. (true/false) The value of a parent must be less than all its children. (true/false) All nodes in the right subtree of a...
Can someone help with these two problems?
The following binary tree contains the characters 'A' through 'G' in its nodes. List the nodes in the order that they are visited by: A preorder traversal. An inorder traversal. A postorder traversal. The binary tree in Problem 2 is a Binary Search Tree since for every node, all elements stored in the left subtree of the node are smaller than the element in the node and all elements stored in the right...
Most questions answered within 3 hours.
-
A χ2-curve, looking at the relationship between age and hours
spent working at an office per...
asked 11 minutes ago -
The pH of a sample of water from a river is 5.0. A
sample of effluent from...
asked 56 minutes ago -
At the beginning of the period, the Fabricating Department
budgeted direct labor of $136,500 and equipment...
asked 1 hour ago -
Please answer all
____ 28. Rent control is usually
justified on the grounds that it protects...
asked 1 hour ago -
PARTS A-D HAVE BEEN ANSWERED. WAS TOLD TO REPOST. ONLY ANSWER
PARTS E and F.
A...
asked 1 hour ago -
2) You are given the task of finding a representation for a
circle in a drawing...
asked 2 hours ago -
STUDY QUESTION: Does use of diet drug fen-phen
(fenfluramine-phentermine) cause valvular heart disease?
HINT: Valvular heart...
asked 2 hours ago -
1. An object weighing 40 N rests on a surface. The coefficient
of friction is 0.35....
asked 3 hours ago -
Investor company owns 35% of investee company voting stock and
accounts for the investment under the...
asked 5 hours ago -
The number of major faults on a randomly chosen 1 km stretch of
highway has a...
asked 5 hours ago -
Consider the competitive environment of Starbuck's, Progressive
Insurance, a manufacturing firm with low turnover, or a...
asked 6 hours ago -
3. Gains from trade
Consider two neighbouring island countries called Euphoria and
Contente. They each have...
asked 8 hours ago