CS111 Lab 15 Decision Trees and Knowledge Bases

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
  1. Node.java - representing an individual node in the tree.
  2. KnowledgeTree.java - representing the decision tree (also called KnowledgeTree)
  3. KnowledgeApp.java - the class with a driver program.

Node.java


      /**
      * 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;
        }

      }
    


KnowledgeTree.java

      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!");
        }
      }
    




KnowledgeApp.java


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