Question

**IN JAVA!!**

You may be working with a programming language that has arrays, but not nodes. In this case you will need to save your BST in a two dimensional array. In this lab you will write a program to create a BST modelled as a two-dimensional array. The output from your program will be a two-dimensional array.

THEN: practice creating another array-based BST using integers of your choice.

Once you have figured out your algorithm you will be able to code it.

Use this input file which contains the number of integers (you will need this so you know how many rows you need) followed by the integers that are to put into the BST.

**lab8.txt**

10 50 40 45 25 80 90 60 13 52 70

In this input file the first number is 10. This is the number of nodes. So you will need a 10 x 3 array. However, I will test the program with different input so don't hard code in the 10. Pick up the first integer (say you call it n), you will then need to create an n x 3 array.

**MY CODE**

**Lab8.java**

import java.io.File;

import java.util.*;

import static labnumber8.Node.placement;

import static labnumber8.Node.print;

import static labnumber8.Node.twoDimensional;

//honestly have no idea why these needed to be imported, I made a
seperate class

//for them but would only get error messages.

//the messages would disappear if I just imported them however.

public class LabNumber8 {

public static void main(String[] args) {

File file = new File("lab8.txt");

Scanner scnr = new Scanner(System.in);

int n = 0;

//to get the first input of the file

while(scnr.hasNext()) {

n = scnr.nextInt();

break;

}

//need to create an n x 3 array, in this case n is 10

int[][] arr = new int[n][3];

while(scnr.hasNext()) {

arr.add(scnr.nextInt());

}

//for whatever reason I cannot input any of the ints from the text
file

//to the array, will continue to try but i have looked
everywhere

//on stack overflow and nothing is making sense.

Node root = new Node(scnr.nextInt());

for(int i = 1; i < n; i++) {

root = placement(root, scnr.nextInt());

}

twoDimensional(root);

print(n);

}

}

Node.java

public class Node {

static int[][] arr;

int value;

Node right;

Node left;

Node(int value){

this.value = value;

right= null;

left = null;

}

//this method inserts each part of the BST in its correct
spot

static Node placement(Node node, int val) {

if(node == null) {

return new Node(val);

}

if(val > node.value) {

node.right = placement(node.right, val);

}

else if(val < node.value) {

node.left = placement(node.left, val);

}

return node;

}

Answer #1

Last Updated: 21-04-2020

Given a sorted array. Write a function that creates a Balanced Binary Search Tree using array elements.

Input: Array {1, 2, 3} Output: A Balanced BST 2 / \ 1 3 Input: Array {1, 2, 3, 4} Output: A Balanced BST 3 / \ 2 4 / 1

**Algorithm**

BST from sorted Linked List. Constructing from sorted array in O(n)
time is simpler as we can get the middle element in O(1) time.
Following is a simple algorithm where we first find the middle node
of list and make it root of the tree to be constructed.

1) Get the Middle of the array and make it root. 2) Recursively do same for left half and right half. a) Get the middle of left half and make it left child of the root created in step 1. b) Get the middle of right half and make it right child of the root created in step 1.

// Java program to print BST in given range

// A binary tree node

class Node {

int data;

Node left, right;

Node(int d) {

data = d;

left = right = null;

}

}

class BinaryTree {

static Node root;

/* A function that constructs Balanced Binary
Search Tree

from a sorted array */

Node sortedArrayToBST(int arr[], int start, int end)
{

/* Base Case */

if (start > end) {

return
null;

}

/* Get the middle element and
make it root */

int mid = (start + end) / 2;

Node node = new Node(arr[mid]);

/* Recursively construct the
left subtree and make it

left child of root */

node.left = sortedArrayToBST(arr,
start, mid - 1);

/* Recursively construct the
right subtree and make it

right child of root */

node.right = sortedArrayToBST(arr,
mid + 1, end);

return node;

}

/* A utility function to print preorder traversal
of BST */

void preOrder(Node node) {

if (node == null) {

return;

}

System.out.print(node.data + "
");

preOrder(node.left);

preOrder(node.right);

}

public static void main(String[] args) {

BinaryTree tree = new
BinaryTree();

int arr[] = new int[]{1, 2, 3, 4,
5, 6, 7};

int n = arr.length;

root = tree.sortedArrayToBST(arr,
0, n - 1);

System.out.println("Preorder
traversal of constructed BST");

tree.preOrder(root);

}

}

4 2 1 3 6 5 7

Tree representation of above output: 4 2 6 1 3 5 7

**Time Complexity:** O(n)

Following is the recurrance relation for sortedArrayToBST().

T(n) = 2T(n/2) + C T(n) --> Time taken for an array of size n C --> Constant (Finding middle of array and linking root to left and right subtrees take constant time)

def mergeSort(alist):

print("Splitting ",alist)

if len(alist)>1:

mid = len(alist)//2

lefthalf = alist[:mid]

righthalf = alist[mid:]

mergeSort(lefthalf)

mergeSort(righthalf)

fi=0

j=0

k=0

while i < len(lefthalf) and j < len(righthalf):

if lefthalf[i] <= righthalf[j]:

alist[k]=lefthalf[i]

i=i+1

else:

alist[k]=righthalf[j]

j=j+1

k=k+1

while i < len(lefthalf):

alist[k]=lefthalf[i]

i=i+1

k=k+1

while j < len(righthalf):

alist[k]=righthalf[j]

j=j+1

k=k+1

print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]

mergeSort(alist)

print(alist)

Merg

the length of the list is less than or equal to one, then we already have a sorted list and no more processing is necessary. It is important to note that the list may not have an even number of items. That does not matter, as the lengths will differ by at most one.

def mergeSort(alist):

print("Splitting ",alist)

if len(alist)>1:

mid = len(alist)//

lefthalf = alist[:mid]

righthalf = alist[mid:]

mergeSort(lefthalf)

mergeSort(righthalf)

i=0

j=0

k=0

while i < len(lefthalf) and j < len(righthalf):

if lefthalf[i] <= righthalf[j]:

alist[k]=lefthalf[i]

i=i+1

else:

alist[k]=righthalf[j]

j=j+1

k=k+1

while i < len(lefthalf):

alist[k]=lefthalf[i]

i=i+1

k=k+1

while j < len(righthalf):

alist[k]=righthalf[j]

j=j+1

k=k+1

print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]

mergeSort(alist)

print(alist)

Merg

def mergeSort(alist):

print("Splitting ",alist)

if len(alist)>1:

mid = len(alist)//2

lefthalf = alist[:mid]

righthalf = alist[mid:]

mergeSort(lefthalf)

mergeSort(righthalf)

i=0

j=0

k=0

while i < len(lefthalf) and j < len(righthalf):

if lefthalf[i] <= righthalf[j]:

alist[k]=lefthalf[i]

i=i+1

else:

alist[k]=righthalf[j]

j=j+1

k=k+1

while i < len(lefthalf):

alist[k]=lefthalf[i]

i=i+1

k=k+1

while j < len(righthalf):

alist[k]=righthalf[j]

j=j+1

k=k+1

print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]

mergeSort(alist)

print(alist)

Hello, I am trying to create a Java program that reads a .txt
file and outputs how many times the word "and" is used. I attempted
modifying a code I had previously used for counting the total
number of tokens, but now it is saying there is an input mismatch.
Please help! My code is below:
import java.util.*;
import java.io.*;
public class Hamlet2
{
public static void main(String[] args) throws
FileNotFoundException
{
File file = new File("hamlet.txt");
Scanner fileRead =...

Complete the program below. The program takes in two positive
integers, n and m, and should print out all the powers of n that
are less than or equal to m, on seperate lines. Assume both n and m
are positive with n less than or equal to m.
For example, if the input values are n = 2 and m = 40 the output
should be:
2
4
8
16
32
Starter code:
import java.util.Scanner;
public class Powers {...

JAVA please
Arrays are a very powerful data structure with which you must
become very familiar. Arrays hold more than one object. The objects
must be of the same type. If the array is an integer array then all
the objects in the array must be integers. The object in the array
is associated with an integer index which can be used to locate the
object. The first object of the array has index 0. There are many
problems where...

4.2.2 Basic while loop with user input. JAVA
Write an expression that executes the loop while the user enters
a number greater than or equal to 0.
Note: These activities may test code with different test values.
This activity will perform three tests, with user input of 9, 5, 2,
-1, then with user input of 0, -17, then with user input of 0 1 0
-1. See "How to Use zyBooks".
Also note: If the submitted code has an...

I wrote the following java code with the eclipse ide, which is
supposed to report the number of guesses it took to guess the right
number between one and five. Can some repost the corrected code
where the variable "guess" is incremented such that the correct
number of guesses is displayed? please test run the code, not just
look at it in case there are other bugs that exist.
import java.util.*;
public class GuessingGame {
public static final int...

Write a for loop that prints: 1 2 ... userNum
Ex: userNum = 4 prints:
1 2 3 4
import java.util.Scanner;
public class ForLoops {
public static void main (String [] args) {
int userNum;
int i;
Scanner input = new Scanner(System.in);
userNum = input.nextInt();
for (/* Your code goes here */) {
System.out.print(i + " ");
}
}
}
Need to fill out the "for" solved in JAVA

Write a method that returns the sum of all the elements in a
specified column in a 3 x 4 matrix using the following header:
public static double sumColumn(double[][] m, int
columnIndex)
The program should be broken down into methods, menu-driven, and
check for proper input, etc.
The problem I'm having is I'm trying to get my menu to execute
the runProgram method. I'm not sure what should be in the
parentheses to direct choice "1" to the method. I'm...

Write code in java
Implement a method to build an AVL tree out of a sorted
(ascending order) array of unique integers, with the
fastest possible big O running time. You may implement private
helper methods as necessary. If your code builds a tree that is
other than an AVL tree, you will not get any credit. If your code
builds an AVL tree, but is not the fastest big O implementation,
you will get at most 12 points. You...

Take the Java program Pretty.java and convert it to the
equivalent C program. You can use the file in.txt as sample input
for your program.
v import java.io.*;
import java.util.*;
public class Pretty
{
public static final int LINE_SIZE = 50;
public static void main(String[] parms)
{
String inputLine;
int position = 1;
Scanner fileIn = new Scanner(System.in);
while (fileIn.hasNextLine())
{
inputLine = fileIn.nextLine();
if (inputLine.equals(""))
{
if (position > 1)
{
System.out.println();
}
System.out.println();
position = 1;
}
else...

THIS IS FOR JAVA
I have to write a method for a game of Hangman. The word the
user is trying to guess is made up of hashtags like so " ######
"
If the user guesses a letter correctly then that letter is revealed
on the hashtags like so "##e##e##"
If the user guesses incorrectly then it increments an int
variable named count " ++count; "
String guessWord(String guess,String word,
String pound) In this method, you compare the character(letter)...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 7 minutes ago

asked 15 minutes ago

asked 26 minutes ago

asked 26 minutes ago

asked 40 minutes ago

asked 48 minutes ago

asked 52 minutes ago

asked 54 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago