Hints about how to code the game in C

Data structures for the game

Here is a suitable data structure for a binary tree:
struct node {
  datatype data; // whatever data is inside the node
  struct node *left_ptr; // may be NULL
  struct node *right_ptr; // may be NULL
}
For the Pangolins game, we have two different kinds of nodes: object(name)s and questions. There are several ways we could implement this in C. Here's one possibility, using a single struct type for the two kinds of node:
struct node {
  // a string declaration to hold an object-name (which may be NULL)
  // a string declaration to hold a question (which may be NULL)
  struct node *yes_ptr; // only NULL for objects
  struct node *no_ptr; // only NULL for objects
}
It's up to you to decide on the details of the data structure, and how you store strings.

For example, if you are feeling adventurous, you might want to use an enum to say for each node whether it is an object or a question, and a union to hold the information about either the object or the question.

Printing a tree

The most important thing is to decide which order you want to print the nodes in. e.g. for this tree:
     7
   /   \
  5     6
 / \   / \
1   2 3   4
We could print it
top-down left-to-right: 7 5 1 2 6 3 4
top-down right-to-left: 7 6 4 3 5 2 1
bottom-up left-to-right: 1 2 5 3 4 6 7
bottom-up right-to-left: 4 3 6 2 1 5 7
or in many other different orders (e.g. 1 5 2 7 3 6 4)

Which order do you think is easiest to understand?

The commonest choice (but not by much!) is top-down left-to-right, so we will use that:

void treePrint(struct node *ptr) {
  if (ptr == NULL)
    do nothing
  else {
    print the data from ptr
    // now print its children, left-to-right:
    treePrint(ptr->left_ptr);
    treePrint(ptr->right_ptr);
  }
}

Performing input

Don't use scanf, because it's rather fiddly to handle newline characters. Instead, we recommend you use fgets to read a whole line from the terminal or a file, and then (if you need to) use sscanf to extract the data you want from the line you've just read.

char *fgets(char *str, int size, FILE *f);

This reads the next complete line from file f. The line (including the end-of-line character, and terminated by \0) is written into the string pointed to by str. str must be a char array created by the programmer, of size size. fgets puts as much of the input line as it can into str, stopping when size is reached. If the read failed for some reason, the result of the function is NULL; if it was OK, the result of the function is the same as str.

sscanf(char *str, format, vars...);

This does exactly the same as fscanf, but reads input from the string str, instead of from a file.

The algorithm for the game

initialise the tree // first version: just one object, a pangolin

// first version: play just one round
current node= root of tree
while (not finished) {
  if (current node is a leaf) { // object node
    make the guess
    if (user says guess is correct) {
      say computer has won
    } else {
      say user has won
      ask for new object-name and question
      insert the new object-name and question into the tree
    }
    finished
  } else { // question node
    ask the question
    set current node according to Yes/No response
  }
}
Inserting a new question into the tree, which has to be linked to the new object-name and to the computer's wrong guess, has some similarities to step 2C of exercise 4 - inserting a person into the correct place in a sorted list. (As in step 2F of the same exercise, you might want to try using a pointer to a pointer, but you don't need to.)

Saving and loading the tree

For this exercise, you just need to print the tree in human-readable form, and then input it again. We know that we can print a tree in many different orders, but does the order affect how easy it is to read it in again?

The simple answer is no, as long as the algorithm we use to read the tree does things in exactly the same order as we used to write it out e.g. compare this to treePrint given above:

struct node* treeRead() {
  read the next input line
  if (nothing there)
    return NULL;
  else {
    ptr = malloc (size of a struct node)
    fill ptr from the input line read in above
    // now read its children, left-to-right:
    ptr->left_ptr = treeRead()
    ptr->right_ptr= treeRead()
  }
}
But there is a problem: for treeRead to work correctly, it has to be able to decide whether it is reading an object, which has no children, or reading a question, which has children. (You may be able to think of different but equivalent ways of describing the problem and then solving it.) The simplest way to fix this is to change treePrint to say what kind of node it is printing e.g.:
void treePrint(struct node *ptr) {
  if (ptr == NULL)
    do nothing
  else {
    if (ptr is a question) {
      print "question:" and the question
      //now print the yes and no subtrees:
      treePrint(ptr->yes_ptr);
      treePrint(ptr->no_ptr);
    } else { // ptr is an object
      print "object:" and the object-name
    }
  }
}

struct node* treeRead() {
  read the next line of input
  if (nothing there) // i.e. no input
    return NULL;
  else {
    ptr = malloc (size of a struct node)
    if (the line started with "question:") {
      fill ptr with the question from the input line
      //now read the yes and no subtrees:
      ptr->yes_ptr = treeRead()
      ptr->no_ptr= treeRead()
    } else { // the line started with "object:"
      fill ptr with the object-name from the input line
      ptr->yes_ptr= ptr->no_ptr= NULL
    }
  }
}
e.g. for the tree from round 5 of the example game, treePrint would output:
question: Does it have a tail?
question: Does it like to chase mice?
object: a cat
object: a pangolin
question: Is it flat, round and edible?
question: Can you dip it in your tea?
object: a biscuit
object: a pizza
object: Pete