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(); } } }