练习ADT中Tree的用法，代写一个决策树分类器的应用程序。

Background

In this homework you will be implementing a decision tree classifier. A decision tree classifier is used in rule-based machine learning to classify data based on a predefined set of attributes. In our case, we will be classifying text based on the terms it contains (or does not contain). Decision trees can be used for real-life applications ranging from answering FAQs to classifying a piece of data.
In order to be able to make decisions using the decision tree classifier, we must first build the decision tree. Your program will be able to import existing decision trees from text files, and edit them in the program. Additionally, it will have to read input text and classify it based on the decision tree, printing the decisions that were made in order to reach the final verdict.
NOTE: All exceptions explicitly thrown in Required Classes except for IllegalArgumentException are custom exceptions that need to be made by you.

Required Classes

TreeNode

• private String[] keywords
  • This field holds the message only if it is a leaf, otherwise this is a list of words to trigger going down this path.
  • These keywords are joined as if ORed together:
    • Example: {Fat; Orange}: if text contains Fat or text contains Orange, then go down yes path, otherwise no path.
• private TreeNode left
• private TreeNode right
  • These two fields hold the left and right subtrees respectively.
  • You should have getters/setters for the three fields above.
• public Boolean isLeaf():
  • function that returns true if the node is a leaf and its left and right subtrees are null, otherwise false.
  • Preconditions: This node is initialized
  • Postconditions: The tree remains unchanged

TreeNavigator

• private TreeNode root
  • A reference to the root TreeNode of this tree.
• private TreeNode cursor
  • A reference to the currently selected TreeNode in the tree.
  • The cursor should select the root node by default.
• public static TreeNavigator buildTree(String treeFile)
  • Reads in a text file describing a TreeNavigator. See sample input for an example.
  • Preconditions: treeFile is a non-null, non-empty String that points to a file that exists that is readable and valid.
  • Returns a new TreeNavigator generated by the passed in text file.
• public String classify(String text)
  • Classifies the text with the given tree and returns the classification as a String.
• public String getPath()
  • Gets the current path of the cursor. For example, if cursor referred to a TreeNode at position Garfield in the example below, this method should return NOT red, NOT coyote,wolf, IS cat, IS orange, DECISION: Garfield
  • Note the comma above: This is how you can show multiple keywords.
• public void resetCursor()
  • Resets the cursor to the root node.
  • Postconditions: Cursor references root node. Cursor contents are printed.
• public void cursorLeft()
  • Moves cursor to its left child.
  • Postconditions: Cursor contents are printed.
• public void cursorRight()
  • Moves cursor to its right child.
  • Postconditions: Cursor contents are printed.
• public TreeNode getCursor()
  • This gets the Cursor so you can modify the keywords or the Left or the Right child links.
  • Precondition: Cursor is not null (return null if it is null)
  • Postcondition: Cursor is returned to the caller.
• public void editCursor(String text)
  • Sets the keywords for the current cursor.

DecisionTreeClassifier (Driver)

• public static void main (String args[])
  • This will drive the program and present a menu like shown below.
  • You can and should write helper functions for each menu option if not already present in the TreeNavigator.

General Recommendations

You might want to implement a toString() method for classes to make debugging and printing easier. You do not have to do this, but it will help you.
You can feel free to add any extra methods and variables as you see fit (public and private).

Text file format

The input file will be formatted like the following example:

0;;Red;nonleaf0-0;Coyote,Wolf;nonleaf0-0-0;Cat;nonleaf0-0-0-0;snoopy;leaf0-0-0-1;fat,orange;nonleaf0-0-0-1-0;tom;leaf0-0-0-1-1;garfield;leaf0-0-1;big,bad,evil,mean;nonleaf0-0-1-0;Wolf Blitzer;leaf0-0-1-1;ACME;nonleaf0-0-1-1-0;Big Bad Wolf;leaf0-0-1-1-1;Wile E. Coyote;leaf0-1;Dog;nonleaf0-1-0;plumber;nonleaf0-1-0-0;Little Red Riding Hood;leaf0-1-0-1;Mario;leaf0-1-1;Clifford;leaf

UI Required Functions

Menu:

• Classify (Sentence)
• Path (Sentence)
• Import (file)
• Cursor To Root (print cursor)
• Cursor Left (print cursor)
• Cursor right (print cursor)
• Edit Cursor (print cursor)
• Add Left Child (doesnt move cursor)
• Add Right Child (doesnt move cursor)

Sample IO

Example 1 - Working with the following tree:

Welcome to the DecisionTree ClassifierMenu:I)Import a tree from a fileE)Edit current treeC)Classify a DescriptionP)Show decision path for a DescriptionQ) Quit.Please select an option: ECursor is at root.Current node keywords: tree is empty Root node is initialized with this value.Please select an option:E)Edit KeywordsC)Add Children Children are automatically leaves, can be edited later.D)Delete Children, and Make Leaf Ask user for new value for keyword(only one, no commas).N)Cursor to No ChildY)Cursor to Yes ChildR)Cursor to RootP)Cursor to Parent Extra credit. May not use parent reference for extra credit.M)Main MenuPlease select an Edit option:EPlease enter keywords for this node, separated by a comma:smelly,dimKeywords updated to: smelly, dim.//Edit menu not shown again in sample IOPlease select an Edit option: CPlease enter terminal text for the no leaf: tempNoPlease enter terminal text for the yes leaf: tempYesChildren are: yes - 'tempYes' and no - 'tempNo'Please select an Edit option: YCursor moved. Cursor is at leaf, message is 'tempYes'.Please select an Edit option: APlease enter terminal text for the no leaf: JavitsPlease enter terminal text for the yes leaf: Old CSChildren are: yes - 'Old CS' and no - 'Javits'Please select an Edit option:EPlease enter keywords for this node, separated by a comma:asbestos,brokenKeywords updated to: smelly, dim.Please select an Edit option:RCursor moved. Cursor is at root.Current node keywords: smelly, dimPlease select an Edit option:NCursor moved. Cursor is at leaf, message is 'tempNo'.Please select an Edit option:EPlease enter keywords for this node, separated by a comma:sick,food,bad,activitiesKeywords updated to: sick,food,bad,activities.Please select an Edit option: APlease enter terminal text for the no leaf: New CSPlease enter terminal text for the yes leaf: SACChildren are: yes - 'New CS' and no - 'Javits'.Please select an Edit option: M//Main menu not shown in samplePlease select an option: CPlease enter some text: Where can I go if I want to sit in a broken chair in a dim room?Your request is classified as: Old CSPlease select an option: PPlease enter some text: I would like to get sick before my test tomorrow. Where should I eat to increase my chances?Decision path:NOT smelly, dim, IS sick, DECISION: SACPlease select an option: ECursor is at root.Current node keywords: smelly, dimPlease select an Edit option: DPlease enter a terminal text for this node: Chuck NorrisCurrent node is leaf. Text is: 'Chuck Norris'.Please select an Edit option: MPlease select an option: CPlease enter some text: Who can kill two stones with one bird?Your request is classified as: Chuck NorrisPlease enter a menu option: QGoodbye!

Example 2 - Working with the following tree:

Welcome to the DecisionTree ClassifierMenu:I)Import a tree from a fileE)Edit current treeC)Classify a DescriptionP)Show decision path for a DescriptionQ)Quit.Please select an option: IPlease enter a filename: sampletree.txtTree Loaded.Please select an option:PPlease enter some text:This Character is an orange cat who likes lasagna.Decision path: NOT red, NOT coyote,wolf, IS cat, IS orange, DECISION: GarfieldPlease select an option:CPlease enter some text:I'm looking for a plumber, but I insist that he wears a red hat, so I know how to tell  him apart from his brother.Your request is classified as: MarioPlease select an option:CPlease enter some text: Who is the unlucky coyote who always tries to use ACME products to catch a bird?Your request is classified as: Wile E. CoyotePlease enter a menu option: QGoodbye!

Extra Credit: GUI OR Android NOT BOTH Requirements

You must make a nice visualization of all the components. For example this can include a graphical representation of the tree and what each node contains, along with connecting lines to each node.
All the menu options should be buttons, and all inputs should be graphical (ie: in a TextField in JavaFX) for any extra credit.

Extra Credit: Child to Parent (can be done with or without a GUI for credit)

Implement a Cursor to Parent function as in the sample WITHOUT putting a parent reference in the TreeNode class.