C语言学习，二叉树的实现

Question

我在编写下面的程序：
tree.h

//TREE.H二叉查找树，树中不允许有重复项
#ifndef _TREE_H_
#define _TREE_H_
#define SLEN 20

typedef struct item
{
    char petname[SLEN];
    char petkind[SLEN][SLEN];
} Item;
//定义节点的内容
#define MAXITEMS 100

typedef struct trnode
{
    Item item;
    struct trnode *left;
    struct trnode *right;
} Trnode;
//定义节点

typedef struct tree
{
    Trnode *root;
    int size;
} Tree;
//定义二叉查找树

//函数原型
//初始化树
void InitializeTree(Tree *ptree);

//判断树是否已空
int TreeIsEmpty(const Tree *ptree);

//判断树是否已满
int TreeIsFull(const Tree *ptree);

//树中的项数
int TreeItemCount(const Tree *ptree);

//添加节点
int AddItem(const Item *pi, Tree *ptree);

//在树内查找
int InTree(const Item *pi, const Tree *ptree);

//删除项
int DeleteItem(const Item *pi, Tree *ptree);

//遍历树
void Traverse(const Tree *ptree, void (*pfun)(Item item));

//清空树
void DeleteAll(Tree *ptree);

#endif

tree.c

//TREE.C查找二叉树的操作函数实现
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "tree.h"

typedef struct pair
{
    Trnode *parent;
    Trnode *child;
} Pair;

static Trnode *MakeNode(const Item *pi);
static int ToLeft(const Item *i1, const Item *i2);
static int ToRight(const Item *i1, const Item *i2);
static void AddNode(Trnode *new_node, Trnode *root);
static void InOrder(const Trnode *root, void (*pfun)(Item item));
static Pair SeekItem(const Item *pi, const Tree *ptree);
static void DeleteNode(Trnode **ptr);
static void DeleteAllNodes(Trnode *ptr);

void InitializeTree(Tree *ptree)
{
    ptree->root = NULL;
    ptree->size = 0;
}

int TreeIsEmpty(const Tree *ptree)
{
    if(ptree->root == NULL)
        return 1;
    else
        return 0;
}

int TreeIsFull(const Tree *ptree)
{
    if(ptree->size == MAXITEMS)
        return 1;
    else
        return 0;
}

int TreeItemCount(const Tree *ptree)
{
    return ptree->size;
}

int AddItem(const Item *pi, Tree *ptree)
{
    Trnode *new_node;
    Pair look;
    int i;

    if(TreeIsFull(ptree))
    {
        fprintf(stderr,"Tree is full\n");
        return 0;
    }

    if(SeekItem(pi,ptree).child != NULL)
    {
        look = SeekItem(pi,ptree);
        for(i=0;i<SLEN;i++)
        {
            if(strlen(look.child->item.petkind[i])<1)
            {
                strcpy(look.child->item.petkind[i],pi->petkind[0]);
                break;
            }
        }
        return 1;
    }
    //如果输入数据重复，则在原数据上添加种类

    //如果新数据不存在，则添加节点，标记数量为1
    new_node = MakeNode(pi);
    if(new_node == NULL)
    {
        fprintf(stderr,"Couldn't create node\n");
        return 0;
    }
    ptree->size++;

    if(ptree->root == NULL)
        ptree->root = new_node;
    else
        AddNode(new_node,ptree->root);
    return 1;
}

int InTree(const Item *pi, const Tree *ptree)
{
    return (SeekItem(pi,ptree).child == NULL) ? 0 : 1;
}

int DeleteItem(const Item *pi, Tree *ptree)
{
    Pair look;
    look = SeekItem(pi,ptree);
    if(look.child == NULL)
        return 0;

    if(look.parent == NULL)
        DeleteNode(&ptree->root);
    else if(look.parent->left == look.child)
        DeleteNode(&look.parent->left);
    else
        DeleteNode(&look.parent->right);
    ptree->size--;

    return 1;
}

void Traverse(const Tree *ptree, void (*pfun)(Item item))
{
    if(ptree != NULL)
        InOrder(ptree->root,pfun);
}

void DeleteAll(Tree *ptree)
{
    if(ptree != NULL)
        DeleteAllNodes(ptree->root);
    ptree->root = NULL;
    ptree->size = 0;
}

//局部函数
static void InOrder(const Trnode *root, void (*pfun)(Item item))
{
    if(root != NULL)
    {
        InOrder(root->left,pfun);
        (*pfun)(root->item);
        InOrder(root->right,pfun);
    }
}

static void DeleteAllNodes(Trnode *root)
{
    Trnode *pright;

    if(root != NULL)
    {
        pright = root->right;
        DeleteAllNodes(root->left);
        free(root);
        DeleteAllNodes(pright);
    }
}

static void AddNode(Trnode *new_node, Trnode *root)
{
    if(ToLeft(&new_node->item, &root->item))
    {
        if(root->left == NULL)
            root->left = new_node;
        else
            AddNode(new_node, root->left);
    }
    else if(ToRight(&new_node->item, &root->item))
    {
        if(root->right == NULL)
            root->right = new_node;
        else
            AddNode(new_node, root->right);
    }
    else
    {
        fprintf(stderr,"Location Error! in Add Node()\n");
        exit(1);
    }
}

static int ToLeft(const Item *i1, const Item *i2)
{
    int comp1;

    if((comp1 = strcmp(i1->petname, i2->petname))<0)
        return 1;
    else
        return 0;
}

static int ToRight(const Item *i1, const Item *i2)
{
    int comp1;

    if((comp1 = strcmp(i1->petname, i2->petname))>0)
        return 1;
    else
        return 0;
}

static Trnode *MakeNode(const Item *pi)
{
    Trnode *new_node;

    new_node = (Trnode *)malloc(sizeof(Trnode));
    if(new_node != NULL)
    {
        new_node->item = *pi;
        new_node->left = NULL;
        new_node->right = NULL;
    }
    return new_node;
}

static Pair SeekItem(const Item *pi, const Tree *ptree)
{
    Pair look;
    look.parent = NULL;
    look.child = ptree->root;

    if(look.child == NULL)
        return look;
    while(look.child != NULL)
    {
        if(ToLeft(pi,&(look.child->item)))
        {
            look.parent = look.child;
            look.child = look.child->left;
        }
        else if(ToRight(pi,&(look.child->item)))
        {
            look.parent = look.child;
            look.child = look.child->right;
        }
        else
            break;
    }
    return look;
}

static void DeleteNode(Trnode **ptr)
{
    Trnode *temp;
    if((*ptr)->left == NULL)
    {
        temp = *ptr;
        *ptr = (*ptr)->right;
        free(temp);
    }
    else if((*ptr)->right == NULL)
    {
        temp = *ptr;
        *ptr = (*ptr)->left;
        free(temp);
    }
    else
    {
        for(temp = (*ptr)->left;temp->right != NULL;temp = temp->right)
            continue;
        temp->right = (*ptr)->right;
        temp = (*ptr);
        (*ptr) = (*ptr)->left;
        free(temp);
    }
}

petclub.c

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "tree.h"

char menu(void);
void addpet(Tree *pt);
void droppet(Tree *pt);
void showpets(const Tree *pt);
void findpet(const Tree *pt);
void printitem(Item item);
void uppercase(char *str);
char *s_gets(char *st, int n);

int main(void)
{
    Tree pets;  //定义树变量
    char choice;
  
    InitializeTree(&pets);    

    while((choice = menu()) != 'q')
    {
        switch (choice)
        {
        case 'a': addpet(&pets);
            break;
        case 'l': showpets(&pets);
            break;
        case 'f': findpet(&pets);
            break;
        case 'n':
            printf("%d pets in club\n", TreeItemCount(&pets));
            break;
        case 'd': droppet(&pets);
            break;
        default: puts("Switching error");
        }
    }
    DeleteAll(&pets);
    puts("Bye.");

    return 0;
}

char menu(void)
{
    int ch;

    puts("Nerfville pet Club Membership Program");
    puts("Enter the letter corresponding to your choice: ");
    puts("a)add a pet        l)show list of pets");
    puts("n)number of pets   f)find pets");
    puts("d)delete a pet     q)quit");
    while ((ch = getchar()) != EOF)
    {
        while (getchar() != '\n')  //丢弃输入行的剩余部分
            continue;
        ch = tolower(ch);
        if(strchr("alrfndq", ch) == NULL)
            puts("Please enter an a, l, f, n, d, or q: ");
        else
            break;
    }
    if(ch == EOF)  //在遇到EOF时程序退出
        ch = 'q';

    return ch;
}

void addpet(Tree *pt)
{
    Item temp;

    if(TreeIsFull(pt))
        puts("No room in the club!");
    else
    {
        puts("Please enter name of pet: ");
        s_gets(temp.petname,SLEN);
        puts("Please enter pet kind: ");
        s_gets(temp.petkind[0],SLEN);
        uppercase(temp.petname);
        uppercase(temp.petkind[0]);
        AddItem(&temp, pt);
    }
}

void showpets(const Tree *pt)
{
    if (TreeIsEmpty(pt))
        puts("No enteries!");
    else
        Traverse(pt, printitem);
}

void printitem(Item item)
{
    int i=0;
    while(strlen(item.petkind[i])>0)
    {
        printf("pet: %-19s kind: %-19s\n",item.petname,item.petkind[i]);
        i++;
    }
}

void findpet(const Tree *pt)
{
    Item temp;

    if(TreeIsEmpty(pt))
    {
        puts("No enteries!");
        return;
    }

    puts("Please enter name of pet you wish to find: ");
    s_gets(temp.petname,SLEN);
    puts("Please enter pet kind: ");
    s_gets(temp.petkind[0],SLEN);
    uppercase(temp.petname);
    uppercase(temp.petkind[0]);
    printf("%s the %s ",temp.petkind[0],temp.petname);
    if(InTree(&temp, pt))
        printf("is a member.\n");
    else
        printf("is not a member.\n");
}

void droppet(Tree *pt)
{
    Item temp;

    if(TreeIsEmpty(pt))
    {
        puts("No enteries!");
        return;
    }
    puts("Please enter name of pet you wish to delete: ");
    s_gets(temp.petname,SLEN);
    puts("Please enter pet dind: ");
    s_gets(temp.petkind[0],SLEN);
    uppercase(temp.petname);
    uppercase(temp.petkind[0]);
    printf("%s the %s ", temp.petname, temp.petkind[0]);

    if(DeleteItem(&temp,pt))
        printf("is dropped from the club.\n");
    else
        printf("is not a member.\n");
}

void uppercase(char *str)
{
    while(*str)
    {
        *str = toupper(*str);
        str++;
    }
}

char *s_gets(char *st, int n)
{
    char *ret_val;
    char *find;
    ret_val = fgets(st, n, stdin);
    if(ret_val)
    {
        find = strchr(st,'\n');  //查找换行符
        if(find)  //如果地址不是NULL
            *find = '\0';  //在此处放置一个空字符
        else while (getchar() != '\n')
            continue;  //处理输入行剩余的字符
    }
    return ret_val;
}

运行结果如下：

请问是哪里出问题了？要怎么修改？

Answer 1

item结构体中的char数组没有初始化，导致在计算strlen的时候出错。只需要给item结构体增加一个构造函数即可，如下：

typedef struct item
{
    char petname[SLEN];
    char petkind[SLEN][SLEN];
    item()
    {
        for (int i = 0; i < SLEN; i++)
        {
            petname[0] = 0;
            petkind[i][0] = 0;
        }
            
    }
} Item;

修改后的运行结果：