Write a Java program that takes as input text from a file. Build a binary tree o

Question

Write a Java program that takes as input text from a file. Build a binary tree of all words in the file. Words are separated by the usual punctuation marks and spaces. From each binary tree node, link the line numbers on which the word is found. The first line in the file is line 1. If a word occurs more than once on a line, do not include the same line number twice. Your program should not be case-sensitive. That is, upper-case and lower-case words are the same. Your program should not be dependent upon the size or content of the file. A test file of 50,000 words should work as well as the test data provided. The output is a sorted cross-reference of all words in the file, along with a list of the lines on which it is found. Your program should ask the user for the file name and handle exceptions appropriately.

Please write your own binary tree class rather than using one of the Java classes, although you may use code from the book that you adapt. Part of our purpose here is to learn the mechanics of data structures.

For example, for the output might look like this:

a 1 3
all 1 5
are 1 5
as 1
... TEST DATA FILE:

 http://utdallas.edu/~john.cole/CS2336Asg2Data.txt

... TEST DATA FILE:

 http://utdallas.edu/~john.cole/CS2336Asg2Data.txt

Explanation / Answer

import java.util.*; import java.io.*; public class WordTree { public static void main(String[] args) throws IOException { int lineNum = 0; WordTree wordtree = new WordTree(); Scanner file = new Scanner(new File("data.txt")); while(file.hasNextLine()) { Scanner chopper = new Scanner(file.nextLine()); lineNum++; while(chopper.hasNext()) { wordtree.add(chopper.next().toLowerCase(), lineNum); } } wordtree.traverse(); } class TreeNode { private TreeNode left, right; private String word; private TreeSet lines; public TreeNode(String word) { this.word = word; lines = new TreeSet(); } public String toString() { String output = ""; output += word+" "; for(int i : lines) { output += i + " "; } return output; } } private TreeNode root; public WordTree() { } public void add(String word, int line) { if(root == null) { root = new TreeNode(word); root.lines.add(line); } else { TreeNode curr = root; while(curr != null) { if(word.equals(curr.word)) { curr.lines.add(line); break; } else if(word.compareTo(curr.word) < 0) { if(curr.left != null) { curr = curr.left; } else { curr.left = new TreeNode(word); curr.left.lines.add(line); break; } } else { if(curr.right != null) { curr = curr.right; } else { curr.right = new TreeNode(word); curr.right.lines.add(line); break; } } } } } public void traverse() { traverse(root); } public void traverse(TreeNode root) { if(root == null) { return; } traverse(root.left); System.out.println(root); traverse(root.right); } }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.