|
A binary search tree can be used to construct a knowledge base of information
using a binary search tree. The app below can be used to build a decision tree of knowledge for a given of meal items, such as soda, steak, fries, burger, pizza, coffee, etc. The user will be asked a series of yes or no questions about meal items. The program's internal knowledge based is repressented as a binary decision tree, in which internal nodes represent questions and leaf nodes represent meal items. When the app discovers a new meal item, a new sub-tree containing a distinguishing question the meal item. There are three Java classes required for this lab
|
/**
* THERE ARE TWO TYPES OF NODES FOR THE KNOWLEDGE BASE:
* - question (Parent) nodes: Example - Is it a beverage?
* - meal item (Leaf) nodes: Example - Coffee
* The content of a question node is the question to ask;
* The content of a meal-item node is a non yes or no answer to the question.
* A meal-item node can be turned into a question node when a proposed answer fails
*/
public class Node {
// DATA MEMBERS
public boolean isQuestion; // TRUE IF IT IS A QUESTION, FALSE IF IT IS AN ANSWER
public String contents; // Question or meal-item as the case may be
public Node no; // left branch
public Node yes; // right branch
Node(String question, Node noNode, Node yesNode) {
isQuestion = true;
contents = question;
no = noNode;
yes = yesNode;
}
Node(String mealItemAnswer) {
isQuestion = false;
contents = mealItemAnswer;
no = null;
yes = null;
}
//A MEAL-ITEM NODE WILL BE TURNED INTO A QUESTION NODE WHEN A PROPOSED ANSWER FAILS.
void convertToQuestion(String question, Node noNode, Node yesNode) {
isQuestion = true;
contents = question;
no = noNode;
yes = yesNode;
}
}
import java.util.Scanner;
public class KnowledgeTree {
//DATA MEMBER: THE ROOT POINTER TO THE TOP OF THE KNOWLEDGE TREE
private Node root;
//CONSTRUCTOR
public KnowledgeTree() {
// CREATE THE INITIAL KNOWLEDGE TREE USING A FIRST QUESTION AND TWO MEAL ITEMS
String mainSubjectContent = "Is it a beverage?";
Node yesBeverage = new Node("wine");
Node noBeverage = new Node("steak");
Node mainSubject = new Node(mainSubjectContent, noBeverage, yesBeverage);
root = mainSubject;
}
//MEMBER METHODS
//--------------------------------------------------------------------------
// ASKS THE USER A YES OR NO QUESTION - RETURNS TRUE IF YES AND FALSE IF NO
//--------------------------------------------------------------------------
private static boolean askYesNo(String question) {
Scanner in = new Scanner(System.in);
String answer;
for (;;) {
System.out.print(question + " ");
answer = in.nextLine();
if (answer.equals("yes"))
return true;
else if (answer.equals("no"))
return false;
else
System.out.println("Answers must be yes or no");
}
}
//--------------------------------------------------------------------------
// BUILDS THE DECISION TREE BY ADDING A QUESTION NODE AT THE APPROPRIATE LOCATION
//--------------------------------------------------------------------------
public void buildKnowledgeNode() {
Scanner in = new Scanner(System.in);
// TASK 1: BEGIN BY PROPOSING A MEAL ITEM
System.out.println("Please think of a meal item and answer the following yes or no questions. ");
// TASK 2: NAVIGATE DOWN THE TREE USING ANSWERS TO YES OR NO QUESTIONS
// END THE NAVIGATION WHEN THERE ARE NO MORE QUESTIONS TO ASK
// SEARCH THE DECISION TREE BY STARTING AT THE ROOT
Node currentNode = root;
while (currentNode.isQuestion) {
if (askYesNo(currentNode.contents))
currentNode = currentNode.yes;
else
currentNode = currentNode.no;
}
// TASK 3: IF THE MEAL ITEM DOES NOT EXIST IN THE KNOWLEDGE TREE, ADD IT
if (!askYesNo("Is this meal item " + currentNode.contents + "? ")) {
//a. get the meal item name
System.out.print("Name the meal item you are thinking of: ");
String userAnswer = in.nextLine();
//b. identify a yes or no question that distinguishes this meal item
System.out.println(
"Supply a yes/no question that would distinguish " + userAnswer + " from " + currentNode.contents);
String userQuestion = in.nextLine();
// c. add the question node by repositioning the yes and no answers
//yes
if (askYesNo("Is the answer yes or no for " + userAnswer + "? ")){
Node noTemp = new Node(currentNode.contents);
Node yesTemp = new Node(userAnswer);
currentNode.convertToQuestion(userQuestion,noTemp, yesTemp);
}
//no
else{
Node noTemp = new Node(userAnswer);
Node yesTemp = new Node(currentNode.contents);
currentNode.convertToQuestion(userQuestion, noTemp, yesTemp);
}
System.out.println(userAnswer + " has now been added to the knowledge base.");
}
else
System.out.println("Great!");
}
}
public class KnowledgeApp {
public static void main(String[] args) {
// TASK 1: CONSTRUCT A BINARY TREE TO HOLD THE KNOWLEDGE BASE
KnowledgeTree knowledgeTree = new KnowledgeTree();
// TASK 2: BUILD THE KNOWLEDGE BASE AS A DECISION TREE USING
// YES/NO QUESTIONS AND FINAL ANSWERS
for (;;){
knowledgeTree.buildKnowledgeNode();
System.out.println();
}
}
}