C语言 二叉树，一个猜动物的小游戏

1. 此项目用到的知识点: 二叉树， struct， 文件读写。

2. 其中最复杂的地方是：复制一个指针的内容，参考：https://stackoverflow.com/questions/39938648/copy-one-pointer-content-to-another

1. 头文件 "node_utils.h"

#define BOOL int
#define TRUE 1
#define FALSE 0


//This is the NODE type definition.
//The field question_or_animal contains
//either an animal name if the node is a leaf
//or a question used to descend into the tree.
//The left child represents the node to descend
//to if the answer to the question is "yes", the
//right child represents the node to descend to
//if the answer is "no".

typedef struct node {
  char question_or_animal[200];
  struct node *left;
  struct node *right;
} NODE;


//This reads a line from the standard input.
//It returns true if a line was actually read.
//It returns false if end-of-file was encountered
//before any data could be read.

BOOL read_line(char *p);


//Recursively performs a pre-order traversal of the
//tree starting at node p, printing the question_or_animal field to
//the file specified by the file pointer.

void write_tree(NODE *p, FILE *f);


//Reads the file specified by the file pointer and 
//creates a tree based on the contents of the file.
//Returns a pointer to the root node of the tree.

NODE *read_tree(FILE *f);

2. 二叉树节点相关的函数  node_utils.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "node_utils.h"

#define BOOL int
#define TRUE 1
#define FALSE 0

BOOL read_line(char *p)
{
  char c = getchar();
  if (c == EOF)
    return FALSE;
  while ((c == '\n') || (c == ' ') || (c == '\t')) //ignore leading whitespace
    c = getchar();
  while (c != '\n') {
    *p++ = c;
    c = getchar();
  }
  *p = 0;
  return TRUE;
}


void write_tree(NODE *p, FILE *f)
{
  if (p == NULL)
    fprintf(f,"NULL\n");
  else {
    fprintf(f,"%s\n", p->question_or_animal);
    write_tree(p->left,f);
    write_tree(p->right,f);
  }
}

NODE *read_tree(FILE *f)
{
  char s[200];
  int i;
  NODE *n;
  char c;

  //attempt to read the first character of the line
  c = getc(f);

  //if end-of-file has been reached, then it means
  //that the input wasn't structured correctly.
  if (c == EOF) {
    printf("Error: Wrong number of entries in file\n");
    exit(1);
  }

  i = 0;
  for(i=0; (c != EOF) && (c != '\n'); i++) {
    s[i] = c;
    c = getc(f);
  }
  s[i] = 0;

  if(!strcmp(s,"NULL"))
     return NULL;

  n = (NODE *) malloc(sizeof(NODE));
  strcpy(n->question_or_animal, s);
  n->left = read_tree(f);
  n->right = read_tree(f);
  return n;
}

3. 主函数  animals.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "node_utils.h"

#define BOOL int
#define TRUE 1
#define FALSE 0

NODE *root = NULL;

BOOL yes_response() {
    char response[10];
    while (TRUE) {
        fgets(response, 11, stdin);
        response[strcspn(response, "\n")] = 0;  // remove leading newline

        if (strcasecmp(response, "yes") == 0) {
            return TRUE;
        } else if (strcasecmp(response, "y") == 0) {
            return TRUE;

        } else if (strcasecmp(response, "no") == 0) {
            return FALSE;
        } else if (strcasecmp(response, "n") == 0) {
            return FALSE;

        } else {
            printf("You answered neither yes nor no!\n");
        }
    }
}


NODE *new_node(char *s) {
    NODE *newNode = (NODE *) malloc(sizeof(NODE));
    char *s2;
    s2 = malloc(sizeof(char) * (strlen(s) + 1));
    strcpy(s2, s);

    strcpy(newNode->question_or_animal, s2);
    newNode->left = NULL;
    newNode->right = NULL;

    free(s2);
    return newNode;
}


void guess_animal() {
    if (!root) {
        printf("What animal were you thinking of? > ");
        char *animal_name;

        fgets(animal_name, 200, stdin);
        animal_name[strcspn(animal_name, "\n")] = 0;  // remove leading newline
        root = new_node(animal_name);

    } else {
        NODE *current_node = new_node(root->question_or_animal);
        *current_node = *root;

        while (current_node->left && current_node->right) {
            printf("%s (yes/no) > ", current_node->question_or_animal);
            if (yes_response()) {
                current_node = current_node->left;
            } else {
                current_node = current_node->right;
            }
        }

        printf("I'm guessing: %s\n", current_node->question_or_animal);
        printf("Am I right? >");

        if (yes_response()) {
            printf("I win ! \n");
            return;
        }

        // ask 3 questions
        printf("\noops.   What animal were you thinking of? > ");
        char new_animal_name[200];
        fgets(new_animal_name, 200, stdin);
        new_animal_name[strcspn(new_animal_name, "\n")] = 0;  // remove leading newline

        printf("Enter a yes/no question to distinguish a %s and a %s > ", new_animal_name,
               current_node->question_or_animal);
        char new_question[200];
        fgets(new_question, 200, stdin);
        new_question[strcspn(new_question, "\n")] = 0;  // remove leading newline

        printf("What is the answer of a %s (yes or no) > ", new_animal_name);
        BOOL yes_no_to_new_question = yes_response();

        // create 2 nodes
        char *new_animal_name_ptr = new_animal_name;
        NODE *newAnimalNode = new_node(new_animal_name_ptr);     // yes
        NODE *oldAnimalNode = new_node(current_node->question_or_animal);

        // set relations
        char *question;
        question = malloc(sizeof(char) * (strlen(new_question) + 1));
        strcpy(question, new_question);
        strcpy(current_node->question_or_animal, question);

        if (yes_no_to_new_question) {
            current_node->left = newAnimalNode;
            current_node->right = oldAnimalNode;

        } else {
            current_node->left = oldAnimalNode;
            current_node->right = newAnimalNode;
        }

        if (root->left && root->right) {
            if (yes_no_to_new_question) {
                root->left = current_node;
            } else {
                root->right = current_node;
            }
        } else {
            *root = *current_node;
        }
        free(question);
    }
}



//This code is complete. Just add comments where indicated.

int main() {
    int i;
    BOOL done = FALSE;

    //insert comment here: read a data file "data.dat", assign to a pointer
    FILE *datafile = fopen("data.dat", "r");

    if (datafile == NULL) {
        printf("data.dat not found\n");
        exit(1);
    }

    //insert comment here: read the backup file.
    FILE *backupfile = fopen("data.dat.bak", "w");

    //insert comment here: find the root of a binary tree
    root = read_tree(datafile);

    //call write_tree() to write the initial tree to the
    //backup file (i.e. to back up the tree data)
    write_tree(root, backupfile);

    //close both files (for now)
    fclose(backupfile);
    fclose(datafile);

    printf("Welcome to the animal guessing game (like 20 questions).\n");
    do {
        printf("\nThink of an animal...\n");
        guess_animal();  // insert comment here: run the main game
        printf("\nDo you want to play again? (yes/no) >");
    } while (yes_response());  // keep ask user input if the response always is yes

    //now open the "data.dat" file for writing
    datafile = fopen("data.dat", "w");

    //insert comment:
    // call write_tree() to write the full binary tree to a data file (data.dat).
    // this will overwrite the original content.
    write_tree(root, datafile);

    //close the data.dat file
    fclose(datafile);
}

编译命令:

# 编译此项目

gcc -o A1 animals.c node_utils.c