CIS 313, Intermediate Data StructuresFall 2018CIS 313 Lab 2Due: November 1, 2018This lab involves implementing a Binary Search TreeOverviewFill out all of the methods in the provided skeleton code. You may add additional methods, butshould NOT add additional public elds to the BST class. You also should not change the name ofany of the classes or les. You will implement a working Binary Search Tree in the BST.java class.You will relay input commands in lab2.java using a scanner. In particular, you will implement thefollowing functionality:InsertionTo simplify things, we will not test your binary search tree with duplicate elements.Insertion should change one of the leaves of the tree from null to a node holding the inserted value.This should also preserve the ordering requirement that all nodes in the right side of a subtree aregreater than the value in the root of that subtree, and all elements in the left side are lesser thanthe value in the root of the subtree.DeletionWhen deleting a value, delete the node which contains that value from the tree.If said node has no children, simply remove it by setting its parent to point to null instead of it.If said node has one child, delete it by making its parent point to its child.If said node has two children, then replace it with its successor, and remove the successor from itsprevious location in the tree.The successor of a node is the left-most node in the node’s right subtree.If the value speci ed by delete does not exist in the tree, then the structure is left unchanged.FindFind takes an int and returns the node in the tree which holds that value.If no such node exists in the tree, return null.Traversals: preorder, post order, in orderPrint out the elements in a binary search tree, space separated.You should do this for the preorder, post order, and in ordered representation of the elements.Recommended StrategyCreate a print function to visualize the shape of trees.Create trees which should have the same shape, and trees which should have di erent shapes.This will also help you debug your other functions.1Input DescriptionThe input will be a text le, for example inSample.txt below will be provided. The rst line willcontain an integer N, which is the number of lines to follow. Each of the N lines contain a singleword specifying delete, insert, inorder, preorder, or postorder (and for insert and delete, also anumber).You should create an empty binary search tree (with root null), and then perform. a sequenceof actions on that tree.10insert 30insert 40insert 20insert 10inorderpreorderpostorderinsert 3调试CIS 313, Intermediate Data StructuresJava作业、Java Java Bina5delete 30inorderNote: When using an editor, you may also manually type in input to the command window.However, you will be tested with a le similar to inSample.txt.Output DescriptionThe only output will be from the traverse commands. Print each the data in each element in theBST separated by spaces in the correct order (depending on which traverse command was called).For example, using the sample input above, your program should output:10 20 30 4030 20 10 4010 20 40 3010 20 35 40Testing ProtocolWe will test your program in the same fashion as previous labs. We strongly suggest you test yourprogram in the following ways:While creating itWith inSample.txtWith the provided test.sh le found in /home/users/smergend/public/cs313/lab2/test.shon ix-dev.2GradingThis assignment will be graded as follows:Correctness 50%Your program compiles without errors (including the submitted les NOT containing package namesat the top. Delete the package name from the top of the les before you submit them): 10%Your program runs without errors: 10%Your program produces the correct output: 30%(5% for insertion, deletion, nd, and each traversal)Implementation 50%Your Binary Search Tree class implements all of the proper methods in O(n): 50%To earn points for implementation, your code must be clear enough for us to under-standFurther, you may not use any data structures from the Java standard library, theC foreign function interface, or arraysExtra Credit 20%To receive points for the extra credit you will create two Binary Search Trees based on given input,and then you must determine if they have the same shape:Create a new public class le called TreeCompareTreeCompare will be similar to lab2.java{ It will read in a list of commands from an input text le{ The input text le will create two di erent BSTs{ The input text le will start with a number N1{ Then N1 lines of insert commands will follow to create the rst BST{ Then there will be a line with a number N2{ Then N2 lines of insert commands will follow to create the second BSTAfter you have created the two BSTs, TreeCompare will compare the two treesIf the trees have the same shape, output &"The trees have the same shape.&"Otherwise, output &"The trees do not have the same shape.&"Here is an example of what the input text le may look like:insert 10insert 20insert 30insert 40insert 50insert 50insert 40insert 30insert 20insert 10The corresponding output would then be:The trees do not have the same shape.转自：http://ass.3daixie.com/2018110120083412.html