MCX2                                                                                                                 Math Department
Mr. Gary. Jaye                                                                                                    Danny Jaye, A.P.S.

                                        2000 APCS AB Exam Question 4

Consider a binary tree that implements a decision tree to give advice on some subject. Internal (nonleaf) nodes contain 
decisions to be made; leaf nodes represent the final advice or recommendation. For example, the following decision tree 
could be used to provide advice on choosing a movie.

Consider the following representation for the nodes of a tree.

struct AdviceNode  { 
   apstring QorA;           // a question or an answer
   AdviceNode * yes;        // yes branch 
   AdviceNode * no;         // no branch
   AdviceNode(const apstring & s);     // constructor
};

Each node contains either a question or an answer (final recommendation). If QorA is a question, 
the Advice node has two non-empty subtrees, representing Yes and No answers to the question. If QorA 
is an answer, the node has no children. Function IsQuestionNode, whose specification is given below, 
is provided to determine whether a node is a question or an answer node. 

bool IsQuestionNode(AdviceNode * T); 
// precondition:  T is not NULL 
// postcondition: returns true if T points to a question node; otherwise, returns false 

Do not write the body of IsQuestionNode. 

(a) Write function GiveAdvice, as started below. If parameter T points to a question node, GiveAdvice 
      should print the question, read a ' Y' or ' N' response from cin and then continue down the appropriate path 
      in the tree. (Assume that users always respond with either' Y' or ' N' .)  If parameter T points to an answer node, 
  GiveAdvice should print the answer.

     For example, if T is the tree given above and the user always answers' Y', then the output would be as follows 
     (where user input is given in boldface). 

  Do you want to see a romantic movie? Y 
  A classic movie? Y 
  Casablanca 

    In writing GiveAdvice, you may call function IsQuestionNode specified at the beginning of this question. 
   Assume that function IsQuestionNode works as specified. 

   Complete function GiveAdvice below.

void GiveAdvice(AdviceNode * T) {
// precondition:  T is not NULL 

(b) Write function TracePath, as started below. TracePath should search for the parameter movie in decision 
       tree T, recursively tracing the path from the root of the tree to the movie. If the movie is in tree T, TracePath pushes 
       the questions and answers along that path onto the parameter pathStack and returns true. If the movie is not in tree T, 
   TracePath returns false. For question nodes, the question and its answer should be stored together as a single string 
       in the stack. For example, if T is a pointer to the root of the decision tree shown at the beginning of this question and S 
       is an empty stack, then after the call TracePath (T, "Jaws", S), S would contain the following elements. 

top -> "Do you want to see a romantic movie? No" 
       "Science Fiction? No" 
       "Suspense? Yes" 
       "Jaws" 

       In writing TracePath, you may call function IsQuestionNode specified at the beginning of this question. Assume 
       that function IsQuestionNode works as specified. You may also assume that a given movie appears at most once in the 
       decision tree. 

       Complete function TracePath below. 

bool TracePath(AdviceNode * T, const apstring & movie, apstack<string> & pathStack){ 
//precondition: T is not NULL