Write an efficient xxxxxH5.java program that:

a) Reads n idno and name from input file and inserts them in a BST. // (100 Pts)

b) Print inorder, preorder and postorder of the BST in a user friendly form by modifying inorder, preorder and postorder methods. // (60 Pts)

c) Reads m idno from input file and query the BST. // (40 Pts)

To compile: javac xxxxxH5.java

To execute: java xxxxxH5 20 5 input.txt

A sample input is as follow:

206 Yashir 356 Ryan 311 Ruth 117 Morgan 341 Mard 251 Losak

266 Kelly 371 Ramir 258 Qu 176 Park 100 Wesley 288 Victor

161 Sergio 146 Saman 303 Sahil 228 Saber 333 Saad 221 Kagen

318 John 122 Jian

243 258 100 117 363

Please Save the following java program into xxxxxH4.java and just please complete the required methods and do not modify main method, except writing your name in line 176.

1 // CSUN COMP 282 Sp 22, Homework-5

2 // Implementing Binary Search Tree (BST)

3 // Author: G. Dastghaiby Fard

4

5 import java.io.*;

6 import java.util.*;

7

8 public class xxxxxH5{

9 //root is a pointer to root of the BST

10 node root = null;

11

12 //use a short word for prt to save typing

13 PrintStream prt = System.out;

14

15 // class node

16 private class node {

17 int id;

18 String name;

19 node ll, rl; //left and right link

20 // node constructor

21 node(int myid, String myname) {

22 id = myid;

23 name = myname;

24 rl = ll = null;

25 } //end node constructor

26 }// end class node

27

28 //inorder traversal of BST

29 private void preorder(){

30 if (root == null){

31 prt.printf (" tBST is empty, So no preorder traversal.");

32 return;

33 }

34 prt.printf (" tPreorder of BST is as follow: ");

35 preorder(root);

36 }// end preorder()

37

38 //preorder traversal from node t

39 private void preorder(node t){

40 //complete this method

41 } //end preorder traversal from node t

42

43 //inorder traversal of BST

44 private void inorder(){

45 if (root == null){

46 prt.printf (" tBST is empty, So no inorder traversal.");

47 return;

48 }

49 prt.printf (" tInorder of BST is as follow: ");

50 inorder(root);

51 }// end inorder()

52

53 //inorder traversal from node t

54 private void inorder(node t){

55 //complete this method

56 } //end inorder traversal from node t

57

58 //postorder traversal of BST

59 private void postorder(){

60 if (root == null){

61 prt.printf (" tBST is empty, So no postorder traversal.");

62 return;

63 }

64 prt.printf (" tpostorder of BST is as follow: ");

65 postorder(root);

66 }// end postorder()

67

68 //postorder traversal from node t

69 private void postorder(node t){

70 //complete this method

71 } //end postorder traversal from node t

72

73 //insert myid and myname in the BST

74 private void insert(int myid, String myname){

75 if (root == null){

76 //Allocate space and store myid, myname

77 root = new node(myid, myname);

78 return;

79 }// end if

80 insert(myid, myname, root);

81 } // end insert(myid, myname)

82

83 //insert myid and myname in the BST from node t

84 private void insert(int myid, String myname, node t){

85 //Complete this method

86 } // end insert(myid, myname)

87

88 // search for myid in the BST

89 private String search(int myid){

90 prt.printf(" tSearch for %d in the BST: ", myid);

91 if (root == null){//BST is empty

92 prt.printf ("tSorry, BST is empty.");

93 return null;

94 }

95 return search(myid, root);

96 } // end search (int myid)

97

98 // search for myid in the BST from node t if found return its name

99 private String search(int myid, node t){

100 //complete this method

101 return null;

102 } // end search (int myid, node t)

103

104

105 // process method for BST insert and search

106 private void process(int n, int m, String fn){

107 int i, myid, k;

108 String myname;

109 prt.print("tJava program to: tInsert n id and name into an empty BST," +

110 " printing 3 traversals tcontents of the BST and" +

111 " searching m id in the BST.");

112 try{

113 Scanner inf = new Scanner(new File(fn));

114 prt.printf(" tInsert %d id and name into BST. t", n);

115 // insert n id and name into BST

116 for (i = 1; i <= n; i++) {

117 //read next id and name

118 myid = inf.nextInt();

119 myname = inf.next();

120 // insert id and name in the bst

121 prt.printf("%2d:%3d, %-10s", i, myid, myname);

122 if (i % 5 == 0) prt.printf(" t");

123 insert(myid, myname);

124 } // end for

125

126 // print 3 travesals of the BST

127 preorder();

128 inorder();

129 postorder();

130

131 prt.printf(" tSearch %2d id in the BST.", m);

132 // search for nsrch id in the BST

133 for (i = 1; i <= m; i++) {

134 // read next word

135 myid = inf.nextInt();

136 // search for myid in the bst

137 myname = search(myid);

138 if (myname != null)

139 prt.printf(" Found: %s", myname);

140 else

141 prt.printf(" NOT Found.");

142 } // end for

143 //close input file

144 inf.close();

145 } catch (Exception e) {prt.print(" Read Error... " + e);}

146 } //end process method

147

148

149 // main method

150 public static void main(String args[]) throws Exception{

151 int m, n, cnt = args.length; // get no. of atguments

152 String fn;

153 if (cnt < 3)

154 System.out.printf(" tOOOPS Invalid No. of aguments!"+

155 " tTO Execute: java xxxxxH5 20 10 input.txt");

156 else {

157 // get no. of elements to insert

158 n = Integer.parseInt(args[0]);

159

160 // get no. of elements to search

161 m = Integer.parseInt(args[1]);

162

163 // get input file name

164 fn = args[2];

165

166 System.out.printf(" t n = %d, m = %d, fn=%s",

167 n, m, fn);

168

169 // create an instance of H1282 class

170 xxxxxH5 bst = new xxxxxH5();

171

172 // call process method

173 bst.process(n, m, fn);

174

175 //MAKE SURE TO WRITE YOUR NAME IN NEXT LINE

176 System.out.printf(" tAuthor: Gh. Dastghaibyfard Date: " +

177 java.time.LocalDate.now());

178 }

179 } // end main

180 } // end class xxxxxH5