In Java.

Programming Steps:

* Modify the program given below to do the following.

1) Modify the code to write the sample output shown below to the output file "p9out.txt".

2) Already have the code to write the generated input to the output file.

3) Now, modify the code first to write the 3 traversals shown in sample output to the output file based on the generated 20 numbers.

4) After doing step 3, you should write the output to output file "p9out.txt" (Same file) the same way it writes to the console using System.out.println().

5) Whenever user pick any option from menu, such as add or delete or any traversals, it should write to the output file. After any option, print all traversals.

6) Might just need to add the print writer statements to write to output file the same way there are for System.out.println().

Sample output file: (Right now, it just writes the generated input to the output file)

The generated input: 93 8 56 44 53 8 62 3 19 63 49 64 16 34 70 34 15 9 26 82

Preorder traversal: 34 15 8 3 8 9 19 16 26 34 62 49 44 53 56 70 63 64 82 93

Inorder traversal: 3 8 9 8 15 16 34 26 19 34 44 56 53 49 64 63 93 82 70 62

Postorder traversal: 3 9 8 8 16 34 26 19 15 44 56 53 49 64 63 93 82 70 62 34

Add 23:

Preorder traversal of constructed BST after adding a new node 34 15 8 3 8 9 19 16 26 23 34 62 49 44 53 56 70 63 64 82 93

Inorder traversal of constructed BST after adding a new node 3 8 9 8 15 16 23 34 26 19 34 44 56 53 49 64 63 93 82 70 62

Postorder traversal of constructed BST after adding a new node 3 9 8 8 16 23 34 26 19 15 44 56 53 49 64 63 93 82 70 62 34

Delete 15:

Preorder traversal of constructed BST after deleting a node 34 16 8 3 8 9 19 26 23 34 62 49 44 53 56 70 63 64 82 93

Inorder traversal of constructed BST after deleting a node 3 8 9 8 16 23 34 26 19 34 44 56 53 49 64 63 93 82 70 62

Postorder traversal of constructed BST after deleting a node 3 9 8 8 23 34 26 19 16 44 56 53 49 64 63 93 82 70 62 34

Delete 99:

** Number 100 is not found **

BinaryTree.java:

import java.io.BufferedWriter; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; import java.util.Arrays; import java.util.Scanner;

class BinaryTree { static Node root;

/* A function that constructs Balanced Binary Search Tree from a sorted array */ Node ArrayToBST(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 = ArrayToBST(arr, start, mid - 1);

/* Recursively construct the right subtree and make it right child of root */ node.right = ArrayToBST(arr, mid + 1, end);

return node; }

void addToTree(int key) { root = insertRec(root, key); }

/* A recursive function to insert a new key in BST */ Node insertRec(Node root, int 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 < root.data) root.left = insertRec(root.left, key); else if (key > root.data) root.right = insertRec(root.right, key);

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

public static boolean search(int val) { return search(root, val); }

/* Function to search for an element recursively */ private static boolean search(Node r, int val) { boolean found = false; while ((r != null) && !found) { int rval = r.data; if (val < rval) r = r.left; else if (val > rval) r = r.right; else { found = true; break; } found = search(r, val); } return found; }

public boolean isEmpty() { return root == null; }

void deleteKey(int key) { if (isEmpty()) System.out.println("Tree is Empty");

else { root = deleteRec(root, key); System.out.println(key + " deleted from the tree"); } } /* A recursive function to insert a new key in BST */ Node deleteRec(Node root, int key) { /* Base Case: If the tree is empty */ if (root == null) return root;

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

// if key is same as root's key, then This is the node // to be deleted else { // node with only one child or no child if (root.left == null) return root.right; else if (root.right == null) return root.left;

// node with two children: Get the inorder successor (smallest // in the right subtree) root.data = minValue(root.right);

// Delete the inorder successor root.right = deleteRec(root.right, root.data); }

return root; }

int minValue(Node root) { int minv = root.data; while (root.left != null) { minv = root.left.data; root = root.left; } return minv; }

void inOrder(Node node) { if (node == null) { return; }

inOrder(node.left); System.out.print(node.data + " "); postOrder(node.right);

}

void postOrder(Node node) { if (node == null) { return; }

postOrder(node.left); postOrder(node.right); System.out.print(node.data + " "); }

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) { int[] numbers = new int[20]; BinaryTree tree = new BinaryTree(); //Generates 20 Random Numbers in the range 1 - 100 for(int i = 0; i < numbers.length; i++) { numbers[i] = (int)(Math.random()*100 + 1); }//end for loop try { BufferedWriter writer = new BufferedWriter(new FileWriter("C:/Users/patel/Desktop/JavaFiles/p9in.txt", false)); for(int i = 0; i < numbers.length; i++) { String x = "" + numbers[i]; // Note you have to cast it as strings if not already writer.write(x); writer.newLine(); } writer.flush(); writer.close(); } catch (IOException e) { e.printStackTrace(); }

try { FileReader file = new FileReader("C:/Users/patel/Desktop/JavaFiles/p9in.txt"); int i=0; Scanner input = new Scanner(file); while(input.hasNext()) { numbers[i] = input.nextInt(); i++; } input.close(); } catch(IOException e) { System.out.println("Could not read File ..."); e.printStackTrace(); }

try { BufferedWriter writer = new BufferedWriter(new FileWriter("C:/Users/patel/Desktop/JavaFiles/p9out.txt", false)); writer.write("Project 9 result output by Aashiv Patel "); writer.newLine(); writer.newLine(); writer.write("The generated input: "); for(int i = 0; i < numbers.length; i++) { String x = "" + numbers[i]; // Note you have to cast it as strings if not already writer.write(x); writer.write (" "); } writer.write("Preorder traversal: "); tree.preOrder(root); System.out.println(" "); writer.newLine(); writer.write("Inorder traversal: "); tree.inOrder(root); System.out.println(" "); writer.newLine(); writer.write("Postorder traversal: "); tree.postOrder(root); System.out.println(" "); writer.newLine(); writer.flush(); writer.close(); } catch (IOException e) { System.out.println("Could not write File ..."); e.printStackTrace(); } Arrays.sort(numbers);

int n = numbers.length; root = tree.ArrayToBST(numbers, 0, n - 1); Scanner kbEntry = new Scanner(System.in); char menuOptions; BufferedWriter writer1; // Menu(); do {

System.out.println("Choose the following: "); System.out.println("1 - Add a number into the tree "); System.out.println("2 - Delete a number from the tree "); System.out.println("3 - Preorder Traversal "); System.out.println("4 - Inorder Traversal "); System.out.println("5 - Postorder Traversal "); System.out.println("6 - Exit "); System.out.println("Enter any key from the menu below: "); String input = kbEntry.next(); menuOptions = input.charAt(0); switch (menuOptions) { case '1': System.out.println("Enter the number you want to add to the BST"); String dataToAdd = kbEntry.next(); tree.addToTree(Integer.parseInt(dataToAdd)); System.out.println("Preorder traversal of constructed BST after adding a new node "); tree.preOrder(root); System.out.println(" "); System.out.println("Inorder traversal of constructed BST after adding a new node "); tree.inOrder(root); System.out.println(" "); System.out.println("Postorder traversal of constructed BST after adding a new node "); tree.postOrder(root); break; case '2': System.out.println("Inorder traversal of constructed BST before deleting the node "); tree.inOrder(root); System.out.println(" "); System.out.println("Enter the number you want to delete from the BST"); String dataToDelete = kbEntry.next(); if (search(Integer.parseInt(dataToDelete)) == false) { System.out.println("Number " + Integer.parseInt(dataToDelete) +" is not found"); } else { tree.deleteKey(Integer.parseInt(dataToDelete)); System.out.println("Preorder traversal of constructed BST after deleting a node "); tree.preOrder(root); System.out.println(" "); System.out.println("Inorder traversal of constructed BST after deleting a node "); tree.inOrder(root); System.out.println(" "); System.out.println("Postorder traversal of constructed BST after deleting a node"); tree.postOrder(root); System.out.println(" "); } break;

case '3': System.out.println("Preorder traversal of constructed BST"); tree.preOrder(root); System.out.println(" "); break;

case '4': System.out.println("Inorder traversal of constructed BST"); tree.inOrder(root); System.out.println(" "); break;

case '5': System.out.println("Postorder traversal of constructed BST"); tree.postOrder(root); System.out.println(" "); break;

case '6': break;

default: System.out.println("Error!! Entered wrong key!! "); System.out.println("Please enter key from the menu again. "); } } while (menuOptions != '6'); } }

Node.java:

import java.util.*; import java.io.*;

public class Node {

int data; Node left, right;

public Node(int d) { data = d; left = right = null; } }