Part 1: You\'re not really convinced those recursive methods operating on trees
ID: 3843219 • Letter: P
Question
Part 1:
You're not really convinced those recursive methods operating on trees really work, so you plan
to write one for yourself and see. You will implement a recursive method that changes a binary tree (any binary tree; not necessarily balanced, not necessarily a BST) as if it was flipped left to right.
As an example, the transformation below would be performed when the tree is flipped.
AA
B C to C B DE ED
Hint: the code is minimal but some thinking is required. As always, best done on paper first. To test your code you can make up a tree by manually linking nodes. Then flip it and verify the result (you can do a tree traversal and print each node).
Part 2:
You have some free time left and you decide to have a look at an industrial strength balanced
BST implementation. You have heard that for any large size text, quite a large portion of the words are very common words which occur over and over again (e.g. “a”, “the”, ...). You plan to check for yourself by counting occurrences of all the words in a text file that occur more often than a given number of times and compare that number to the total of words in the file. You will print these words and the number of times they each occur so that you get some idea what kind of words these are.
Part 3:
You will analyze the time efficiency of your solution in part 2.
Hints:
- Have a look at the TreeMap class documentation. Don't be intimidated by the large number of
methods; you will only need to use the main ones we have seen.
https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html
- Once you have all the word – number of occurrence pairs in the tree, you will iterate over the tree and print the pairs in order.
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Map;
import java.util.Scanner;
import java.util.SortedMap;
import java.util.TreeMap;
/**
*
* @author YOUR NAME HERE
*
*/
public class Project5 {
/*
* ******************************** Part 1 ******************************
*/
/* DO NOT MODIFY THE NODE CLASS */
static class Node {
Node(int data) {
this.data = data;
}
int data;
Node left;
Node right;
}
static void flip(Node root) {
// ****************** Your code here **********************
}
/*
* ******************************** Part 2 ******************************
*/
/**
* Prints all the words that occur threshold times or more and their count.
* The words are printed in alphabetical order.
* All the words read from the file are converted to lower case so that "That" and "that"
* are considered the same word. Empty words are not counted.
*
* @param filename The text file to process
* @param threshold e.g. 1000 -> only words that occur 1000 times or more are printed
*/
static void mostFrequentWords(String filename, int threshold) {
// You may find useful these methods for strings:
// split(), toLowerCase(), trim(), isEmpty()
// iterate over the pairs and print the ones that meet the threshold
// System.out.println(word + " " + count);
// print statistics
System.out.println("Total words : " + 0);
System.out.println("Total common words: " + 0);
System.out.println("Total common words as a portion of total words: " + 0);
}
/*
* ******************************** Part 3 ******************************
* Your Part 2 time analysis here.
* Briefly and clearly explain where the final time big O comes from:
*
*
*
*/
/**
* @param args
*/
public static void main(String[] args) {
/*
*
* Test your code well.
*
* You can leave that code in the main but I will not use that or grade
* you on it.
*/
Node root = new Node(1);
// populate tree ...
flip(root);
System.out.println("Most frequent words:");
mostFrequentWords("LesMiserables.txt", 1000);
// Would output something like below (all numbers shown are made up)
// a 12345 - this means the word "a" occured 12345 times in the text
// all 2345 - "all" 2345 times, and so on ...
// an 3456
// ...
// ...
// with 4567
// would 1234
// you 2345
// Total words : 234567
// Total common words: 123456
// All common words as a portion of total: 0.53
}
}
Explanation / Answer
Part 1---------------------------
import java.util.*;
import java.lang.*;
import java.io.*;
/**
*
* @author YOUR NAME HERE
*
*/
class Project5 {
/* DO NOT MODIFY THE NODE CLASS */
static class Node {
Node(int data) {
this.data = data;
}
int data;
Node left;
Node right;
}
public void flipTree(Node root){
display(root);
System.out.println();
Node head = flip(root);
display(head);
}
static Node flip(Node root){
if(root!=null){
Node n = root.left;
root.left = root.right;
root.right = n;
flip(root.right);
flip(root.left);
}
return root;
}
public void display(Node root){
if(root!=null){
display(root.left);
System.out.print(" " + (char)(root.data));
display(root.right);
}
}
public static void main (String[] args) throws java.lang.Exception
{
Node root = new Node('A');
root.left = new Node('B');
root.right = new Node('D');
root.left.left = new Node('X');
root.left.right = new Node('I');
root.right.left = new Node('J');
root.right.right = new Node('L');
//accordingly edit left or right nodes for given tree
Project5 obj = new Project5();
obj.flipTree(root);
}
}
Part 2---------------------------------------------------
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
String wholeText;
public static void readNewFile() {
BufferedReader bufRead = new BufferedReader(new FileReader("input.txt"));
StringBuilder strbuild = new StringBuilder();
String nxtLine = strbuild.readLine();
while (nxtLine != null) {
strbuild.append(nxtLine);
strbuild.append(System.lineSeparator());
nxtLine = bufRead.readLine();
}
wholeText = strbuild.toString();
bufRead.close();
}
}
public static void printMap(Map<String,Integer> map) {
Set st = map.entrySet();
int mostCommonWordCount = 0, totalCount = 0;
Iterator itr = st.iterator();
while ( itr.hasNext() ) {
Map.Entry entry = (Map.Entry) itr.next();
String key = (String) entry.getKey();
Integer value = (Integer) entry.getValue();
if(value>mostCommonWordCount)
mostCommonWordCount = value;
totalCount = totalCount+value;
System.out.println(key + " " + value);
}
System.out.println("Total words : " + totalCount);
System.out.println("Total common words: " + mostCommonWordCount);
System.out.println("Total common words as a portion of total words: " + mostCommonWordCount/totalCount);
}
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
//Take input of string
String str = sc.nextLine();
//Convert all characters to lower case
str = str.toLowerCase();
//Split the string at the whitespace, i.e., each word is stored
String[] words = str.split(" ");
//Create a HashMap to store the string and its count
Map<String, Integer> mp = new HashMap<String, Integer>();
for (int i=0; i<words.length ; i++) {
if (mp.containsKey(words[i])) {
int num = mp.get(words[i]);
mp.put(words[i], num + 1);
} else {
mp.put(words[i], 1);
}
}
Map<String, Integer> treeMap = new TreeMap<String, Integer>(mp);
printMap(treeMap);
}
}
Part 3----------------------------------------
For part 1, it is O(n) as the program traverses all the n number of nodes once.
For part 2, complexity is O(number of words in the file)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.