Java Program Instructions This is a challenging assignment For this assignment y

Question

Java Program

Instructions

This is a challenging assignment

For this assignment you are to develop a program that creates a binary search tree. You are to then read the text file into the binary tree. Finally you are supposed to output the in-order traversal of the binary tree. This should show a sorted list of the 50 state abbreviations in order.

You program will be incorrect if you do not program the binary tree and instead use tree collection.

Use the package name treeStates.

Hints:

You may want to create a Node class to define a tree node

You may want to create a utility class to define how to print tree nodes

You may want to create a BinaryTree class that has a node member

The file they want us to use is named states.txt

The contents of this file is as follows

Explanation / Answer

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;

//Java program to demonstrate insert operation in binary search tree
class BinarySearchTree {

   /* Class containing left and right child of current node and key value */
   class Node {
       String key;
       Node left, right;

       public Node(String item) {
           key = item;
           left = right = null;
       }
   }

   // Root of BST
   Node root;

   // Constructor
   BinarySearchTree() {
       root = null;
   }

   // This method mainly calls insertRec()
   void insert(String key) {
       root = insertRec(root, key);
   }

   /* A recursive function to insert a new key in BST */
   Node insertRec(Node root, String key) {

       /* If the tree is empty, return a new node */
       if (root == null) {
           root = new Node(key);
           return root;
       }

       /* Otherwise, recur down the tree */
       if (key.compareTo(root.key) < 0)
           root.left = insertRec(root.left, key);
       else if (key.compareTo(root.key) > 0)
           root.right = insertRec(root.right, key);

       /* return the (unchanged) node pointer */
       return root;
   }

   // This method mainly calls InorderRec()
   void inorder() {
       inorderRec(root);
   }

   // A utility function to do inorder traversal of BST
   void inorderRec(Node root) {
       if (root != null) {
           inorderRec(root.left);
           System.out.println(root.key);
           inorderRec(root.right);
       }
   }

   // Driver Program to test above functions
   public static void main(String[] args) throws IOException {
       BinarySearchTree tree = new BinarySearchTree();
      
       Scanner sc = new Scanner(System.in);
       System.out.print("Enter input file name: ");
       String fileName = sc.next();
      
       // opening and reading from file
       FileReader fr = new FileReader(fileName);
       BufferedReader br= new BufferedReader(fr);
      
       String line;
       while((line = br.readLine()) != null){
           // inserting into tree
           tree.insert(line.trim());
       }
      
       br.close();
       fr.close();

       // print inorder traversal of the BST
       tree.inorder();
   }
}

/*

Output:

Enter input file name: country.txt

AL
AR
AZ
CA
CO
CT
DE
FL
GA
HI
IA
ID
IL
IN
KS
KY
LA
MA
MD
ME
MI
MN
MO
MS
MT
NC
ND
NE
NH
NJ
NM
NV
NY
OH
OK
OR
PA
RI
SC
SD
TN
TX
UT
VA
VT
WA
WI
WV
WY

*/

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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