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 4We could print it
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); } }
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.)
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