You are not allowed to use Java API Tree, ArrayList, Vector, LinkedList or any o
ID: 3866818 • Letter: Y
Question
You are not allowed to use Java API Tree, ArrayList, Vector, LinkedList or any other Java API Data Structure classes to implement this assignment.
Design a program that will be used as a versatile decision-making system based on user input. There are several places where this application can be used. An example is online Technical Support for a product or group of products. A series of questions might be asked and based on the answers, a different branch of questions will be asked as follow-up-questions to determine exactly how to help the user. Another example is a telephone Technical Support, like a 1-800 number. When calling a 1-800 number, you might communicate with a machine. A series of questions are asked and as answers you typically press the numbers on the keypad, 1-9. After determining exactly what the problem is, a simple answer is usually possible.
In this assignment, you will use Ternary (3-ary) trees to represent the flow of data. In each node in the Ternary tree there will be a question to ask. The "answers" will be branches towards more questions in the tree. For the normal assignment, it will be a Ternary (3-ary) tree, meaning that any node can have at most three children.
1. Write a fully-documented class named TreeNode that stores the data in each node. It should have:
Three references to other TreeNodes. Left, Middle, Right.
OR
An array with three references to other TreeNodes. If you're doing the extra credit, the array should store potentially 9 TreeNodes.
private String label
The "name" of this TreeNode. It will be used when constructing the tree. More info on labels will follow.
private String message
The message will be displayed to the screen. It will either be a question or just a normal message. If this TreeNode has children TreeNodes, it should then traverse one level downwards to each child node to get the prompts as answers. If this TreeNode is a leaf node, then it should just display the message which will act as a solution.
private String prompt
The prompt will be displayed to the screen as a possible answer to a question. For example, when starting at the root of the tree, there will be a question (message) to ask, and as possible answers the root will traverse one level downwards each child TreeNode to display the prompt as a possible answer.
This class should have a constructor, mutator and accessor methods for each instance variable. You may also want to have a method to determine if this TreeNode is a leaf (no children).
2. Write a fully-documented class named Tree that will have a reference to the root of the tree and other useful methods described below:
Constructor.
public boolean addNode(String label, String prompt, String message, String parentLabel)
A method to add a TreeNode to the tree. The location will be a child of parentLabel. The child node should be left justified meaning that it should first be placed in the left most TreeNode reference, then the middle, then the right. A return value of true indicates that the node was successfully added to the tree. Otherwise, the return value is false. More info on the label is in the input file format.
Note: You can use a different method signature if you need to, or define a separate method for adding each child (i.e. addNodeLeft, addNodeMiddle, addNodeRight).
public TreeNode getNodeReference(String label)
Returns a reference to the TreeNode that has the given label. The return value is null if the label is not found. This may be helpful to implement the above method. Efficiency is not important and you can use any traversal order you wish. Also, if you are more comfortable with placing this method in the TreeNode class, that is perfectly acceptable.
public void preOrder()
Traverses the tree in preorder, and prints the contents of the tree to the screen.
Note: This method can also be in the TreeNode class.
public void beginSession()
This method will be used to start the question and answer session.
Note: You may include additional instance variables or methods as needed.
3. Write a fully-documented class named TreeDriver which contains the main() method and it should display a menu:
L (Load input file and build a tree)
Prompt the user for a file name and build a new tree. The entire tree will be recreated each time this menu option is chosen.
H (Start help session)
This option will begin asking questions starting from the root of the tree; if there is no tree set up, display an error message. When displaying a question with answers, display each answer on a separate line with a number associated with it, similar to a menu. Include another option, 0 (zero) to exit the help session and return to the main menu. For example:
If the node is a leaf, then display the message and go back to the main menu. For example:
T (Traverse the tree in pre-order)
Traverse the tree in pre-order and display the label, prompt, and message in each node on a separate line (see sample input/output).
The order is root, left subtree, middle subtree, right subtree.
Q (Quit)
Quit the program.
INPUT FORMAT
All strings in the input file will be no longer than 60 characters so that they will not take up more than one line.
Blank lines in the input file are to be ignored.
The length of the filename will not be longer than 20 characters.
OUTPUT FORMAT
Be sure your prompts and error messages for the user are clear and understandable.
Be sure to have a menu after each operation.
INPUT FILE FORMAT
Since this program is designed to be a versatile decision-making system based on user input, we will be using input files so that anyone with a tree of questions/answers can use this program, including but not limited to Tech Support. It is strongly recommended that you post any sample text files you create in the Blackboard discussion board so that others can test their code. The input file will always start with "root" on the first line. Look at the input file comments and ask any questions you may have on the discussion board.The format of the input file is as follows:
Label is a one-word string with no spaces that is used during the creation of a tree. It determines the location of a node in the tree. A picture of a tree with only their labels is shown below. Note that labels do not have to be in any specific format, and they will not necessarily be made of numbers and dashes.
Prompt is a string that will be printed to the screen as a choice or answer.
(NOTE: The prompt for the root node should not be printed to the screen. Look at the example text file input.)
Message is a string that will be displayed to the screen as either question or if the node is a leaf node, as a final message.
All strings (label, prompt, message) in the input file will be no longer than 60 characters so that they will not take up more than one line.
Another possible line in the input file is the name of a previously defined label followed by a number, separated by at least one space. This number will indicate the number of children this node has. The child nodes will then be directly after this line.
Any blank lines in the input file are to be ignored. They will help the creator of the input file for readability purposes.
If at any point during the reading in of the text file, you encounter an error in the format, you may stop reading in the text file then report a message to the user.
For the normal assignment, a node can have 0, 1, 2, or 3 children.
A sample input text file: Sample text file with comments , Sample text file without comments (this is the file that must be used to test your program).
The visualization of the text file is the second tree below.
For simplicity, we will not include comments in our test cases.
SAMPLE INPUT/OUTPUT
As usual, comments in green, user input in black, and computer output in blue.
Explanation / Answer
//TreeDriver.java
import java.io.*;
import java.util.*;
public class TreeDriver {
static String label;
static String promt;
static String msg;
static String childNumber;
static String parentLabel;
static Scanner stdin = new Scanner (System.in);
static Tree helpTree = new Tree();
public static void main(String[] args) throws IOException {
String input = null;
mainMenu();
input = stdin.next();
while(!input.equalsIgnoreCase("Q")){
if (input.equalsIgnoreCase("L"))
loadFile();
if (input.equalsIgnoreCase("H"))
startHelp();
if (input.equalsIgnoreCase("T"))
helpTree.preOrder();
mainMenu();
input = stdin.next();
}
System.out.println("Closing the program");
}
private static void startHelp() {
helpTree.beginSession();
}
private static void loadFile() throws IOException {
String fileName;
System.out.println("Enter the file name: ");
fileName = stdin.next();
fileName = fileName+".txt";
String line ="";
int wait=1;
try{
Scanner getFile = new Scanner(new File(fileName));
while(getFile.hasNextLine())
{
label = NonEmptyLine(getFile);
promt = NonEmptyLine(getFile);
msg = NonEmptyLine(getFile);
helpTree.addNode(label, promt, msg, parentLabel);
wait--;
if ((wait==0)&&(getFile.hasNextLine())){
line = NonEmptyLine(getFile);
StringTokenizer tkChild = new StringTokenizer(line," ",false);
parentLabel = tkChild.nextToken();
wait = Integer.parseInt(tkChild.nextToken()); // find the number of the children
}
}
System.out.println("File loaded sucessfully");
getFile.close();
}catch (IOException e){
System.out.println("File not Found");
}
}
public static String NonEmptyLine(Scanner fileName){
String nonEmptyLine = "";
String line;
while(fileName.hasNextLine())
{
line = fileName.nextLine();
if (!line.isEmpty()) //If line in not empty
{
nonEmptyLine = line;
break;
}
}
return nonEmptyLine;
}
/**
* Display the main Menu of the program
*/
public static void mainMenu(){
System.out.println("L >> Load Input File");
System.out.println("H >> Start Help Session");
System.out.println("T >> Traverse Tree in Pre-Order");
System.out.println("Q >> Quit");
}
}
====================================================================================
//TreeNode.java
public class TreeNode {
private TreeNode left;
private TreeNode middle;
private TreeNode right;
private String label;
private String message;
private String promt;
/**
* Constructor of TreeNode
*/
public TreeNode(){
}
public TreeNode(String label, String message, String promt){
this.label =label;
this.message = message;
this.promt = promt;
}
public boolean isLeaf(){
if((left == null)&&(right==null)&&(middle ==null))
return true;
else
return false;
}
/**
* Check if a node is empty
* @return true if the node is empty
*/
public boolean isEmpty(){
if ((label==null)&&(message == null)&&(promt == null)){
return true;
}
return false;
}
/**
* Accessor method of left node
* @return left node of the node
*/
public TreeNode getLeft() {
return left;
}
/**
* Mutator method of the left
* @param left - assign the left node of the node
*/
public void setLeft(TreeNode left) {
this.left = left;
}
/**
* Accessor method of the middle node
* @return middle node of the current node
*/
public TreeNode getMiddle() {
return middle;
}
/**
* Mutator method of the middle
* @param middle - assign the middle node of the node
*/
public void setMiddle(TreeNode middle) {
this.middle = middle;
}
/**
* Accessor method of the Right node
* @return right node of the current node
*/
public TreeNode getRight() {
return right;
}
/**
* Mutator method of the right
* @param right - assign the right node of the node
*/
public void setRight(TreeNode right) {
this.right = right;
}
public String getLabel() {
return label;
}
public void setLabel(String label) {
this.label = label;
}
public String getMessage() {
return message;
}
public void setMessage(String message) {
this.message = message;
}
/**
* Accessor method of the prompt
* @return middle node of the prompt
*/
public String getPromt() {
return promt;
}
/**
* Mutator method of the prompt
* @param promt - assign the prompt of the node
*/
public void setPromt(String promt) {
this.promt = promt;
}
/**
* Traverse the tree in pre-order
*/
public void preOrder(){
System.out.println("Label: " + label);
System.out.println("Promt: " +promt);
System.out.println("Message: " +message);
if(left!=null)
left.preOrder();
if(middle!=null)
middle.preOrder();
if(right!=null)
right.preOrder();
}
}
================================================================================
//Tree.java
import java.util.*;
public class Tree {
private TreeNode root;
private TreeNode current;
private TreeNode runner;
/**
* Constructor for Tree
*/
public Tree(){
}
public boolean addNode(String label, String prompt, String message, String parentLabel)
{
TreeNode newNode = new TreeNode(label,message,prompt);
TreeNode getParent = new TreeNode();
if (isEmpty()){
root = newNode;
return true;
}
else { // find the parent node and place the child
getParent = getNodeReference(parentLabel);
if (getParent.getLeft()==null) // if there is no left child add into the left
{
getParent.setLeft(newNode);
return true;
}
if (getParent.getMiddle()==null) // if there is no left child add into the left
{
getParent.setMiddle(newNode);
return true;
}
if (getParent.getRight()==null) // if there is no left child add into the left
{
getParent.setRight(newNode);
return true;
}
}
return false;
}
/**
* Print the tree in Pre-Order;
*/
public void preOrder(){
root.preOrder();
}
/**
* Find the node of a given label
* @param label -- Label of a node which node needs to be found
* @return -- return the node of that label
*/
public TreeNode getNodeReference (String label){
StringTokenizer parent = new StringTokenizer(label, "-",false);
if (label.equalsIgnoreCase("Root"))
{
return root;
}
current = root;
while (parent.hasMoreTokens())
{
int number = Integer.parseInt(parent.nextToken());
if(number==1)
current = current.getLeft();
if(number==2)
current = current.getMiddle();
if(number==3)
current = current.getRight();
}
return current;
}
/**
* Start the Session to help
*/
public void beginSession(){
System.out.println("Welcome to Help Session");
String traceCode ="";
runner = root;
int select=-1;
Scanner input = new Scanner (System.in);
while((runner!=null)&&(select!=0)&&(!runner.isLeaf()))
{
String get="";
System.out.println(runner.getMessage());
if (runner.getLeft()!=null){
System.out.println("1>> "+runner.getLeft().getPromt());
}
if (runner.getMiddle()!=null){
System.out.println("2>> "+runner.getMiddle().getPromt());
}
if (runner.getRight()!=null){
System.out.println("3>> "+runner.getRight().getPromt());
}
if(!runner.isLeaf()&&(!traceCode.isEmpty()))
System.out.println("B>> Go Back");
if (runner.isLeaf()==false){
System.out.println("0>> Exit");
System.out.print("Enter Selection: ");
try{
select =input.nextInt();
}catch (InputMismatchException e){
get =input.next();
select =-1;
}
if(select ==1){
runner = runner.getLeft();
traceCode = traceCode+"l";
}
if(select ==2){
runner = runner.getMiddle();
traceCode = traceCode+"m";
}
if(select ==3){
runner = runner.getRight();
traceCode = traceCode+"r";
}
if(get.equalsIgnoreCase("B")){
System.out.println("Typed B");
System.out.println(traceCode);
runner = prevoius(traceCode);
if(traceCode.length()>1)
traceCode =String.copyValueOf(traceCode.toCharArray(), 0, traceCode.length()-1);
else
traceCode = "";
}
if (runner.isLeaf()){
System.out.println(runner.getMessage());
}
}
}
System.out.println("Thanks for Using your help Session");
}
/**
* This method used to find the parent node of the current node via the trace
* @param trace - String that recored the path of the nodes
* @return - parent node of the current node
*/
public TreeNode prevoius(String trace){
TreeNode sendNode=root;
for(int i=0;i<trace.length()-1;i++){
char info = trace.charAt(i);
if(info=='m'){
sendNode = sendNode.getMiddle();
}
if(info=='l'){
sendNode = sendNode.getLeft();
}
if(info=='r'){
sendNode = sendNode.getRight();
}
}return sendNode;
}
/**
* This method check if a root is empty
* @return true if the node is empty
*/
public boolean isEmpty(){
if (root ==null)
return true;
else
return false;
}
}
=============================================================================
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.