You will be making a binary search tree class. Then you will use it to import a

Question

You will be making a binary search tree class. Then you will use it to import a text file and create a word frequency histogram. Your binary search tree class should have the following methods: search-finds and returns the node that matches a search key (if it exists; otherwise return null) insert-inserts a node into the tree delete-deletes a node from the tree print-traverse (inorder) and print each node any methods you need to solve the problem of using a tree to make a word frequency histogram. You should be able to read a file and add a word if it isn't in the tree yet and update a counter associated with it if it is in the tree. This sentence repeats words because a sentence that repeats words makes a good example sentence. a 2 because 1 example 1 good 1 makes 1 repeats 2 sentence 3 that 1 this 1 words 2

Explanation / Answer

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package chegg.march;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
*
* @author Sam
*/
public class BSTree {
    class Node{ // data structure of each node
        final String data; //stores data
        Node left; //resresents left child
        Node right; //represents right child
        int count;

        public Node(String data) { // constructor to create node
            this.data = data;
            left = right = null;
            count = 1;          
        }

        public int compareTo(Node o) { //compare to another node
            return data.compareTo(o.data); //returns -ve if other node is larger
        }
    }
    Node root;

    public BSTree() {
        root = null; //initialize
    }
  
    void insert(String x) {
        if (root == null) { // if root is null
            root = new Node(x); // we need to insert root
            return; // this will occur only once
        }
        Node parent = null; //parent node is used to store the node where inserion will occur
        Node child = root;
        Node newNode = new Node(x); //new node is created
        while (child!=null ) { // condition to check parent is leaf
            if (child.compareTo(newNode) == 0) { // node already present in the tree
                child.count++;
                return;
            }
              
            parent = child; //make child the new parent
            if (newNode.compareTo(parent) < 0) //if new node value is less than parent
                child = parent.left; // we go to feft of the tree
            else
                child = parent.right; // and vise-versa
        }
      
        if (newNode.compareTo(parent) < 0) // if new node is less than its parent
            parent.left = newNode; // we make it the new feft child
        else
            parent.right = newNode; //else opposite
    }
  
    private static void printInfix (Node root){
        if(root == null)
            return; //terminating condition
        printInfix(root.left); //go to left
        System.out.println(root.data + " " + root.count); //print own value
        printInfix(root.right); //then go to right
    }
  
    public static void main(String[] args) throws IOException { //driver method
        BSTree bst = new BSTree();
        System.out.println("Enter a sentence:");
        String[] inputWords = new BufferedReader(new InputStreamReader(System.in)).readLine().split(" "); //sorry for this complex line
        for (String w:inputWords)
            bst.insert(w.trim().toLowerCase());
        printInfix(bst.root);
    }
  
}

This code should meet all your need. I have also commented the code to make your life easy. I hope you like the code.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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