[C++知识库]C语言—二叉查找树经典实例

一、所用IDE：codeblocks 17.12

二、二叉树查找树介绍：

（一）二叉树查找树ADT

类型名： 二叉查找树
类型属性： 二叉树要么是空节点的集合（空树），要么是有一个根节点的节点集合
每个节点都有两个子树，叫做左子树和右子树
每个子树本身也是一个二叉树，也有可能是空树
二叉查找树是一个有序的二叉树，每个节点包含一个项，
左子树的所有项都在根节点的前面，右子树的所有项都在根节点项的后面
类型操作： 初始化树为空
确定树是否为空
确定树是否已满
确定树中的项数
在树中添加一个项
在树中删除一个项
在树中查找一个项
在树中访问一个项
清空树

（二）二叉查找树接口：

原则上，可以用多种方法实现二叉查找树，甚至可以通过操控数组下标来实现，但是，实现二叉查找树最直接的方法是通过指针动态分配链式节点。常用的定义形式如下：
typedef SOMETHING Item;

typedef struct trnode
{
Item item;
struct trnode * left;
struct trnode * right;
} Trnode;

typedef struct tree
{
Trnode * root;
int size;
} Tree;

每个节点包含一个项，一个指向左子节点的指针和一个指向右子节点的指针。可以把Tree定义为指向Trnode的指针类型，因为只需要知道根节点的位置就可以访问整个树，然而使用有成员大小的结构能方便的记录树的大小。

三、真枪实战

（一）题目要求（需求）

我们要开发一个维护Nerfville宠物俱乐部的花名册，每一项都包含宠物名和宠物的种类。把数的大小限制为10，较小的树便于在树中已满时测试程序的行为是否正确，当然你也可以把MAXITEMS设置为更大的值。

（二）代码如下（实现）：

一、tree.h

/*tree.h -- 二叉查找树 */
/* 该定义假设不允许有重复的项*/
#ifndef TREE_H_INCLUDED
#define TREE_H_INCLUDED
#include<stdbool.h>

/*根据具体情况定义 Item*/
#define SLEN 20
typedef struct item
{
    char petname[SLEN];
    char petkind[SLEN];
} Item;

#define MAXITEMS 10

typedef struct trnode
{
    Item item;
    struct trnode * left; //指向左分支的指针
    struct trnode * right; //指向右分支的指针
} Trnode;

typedef struct tree{
    Trnode * root;
    int size;
} Tree;

/* 函数原型 */

/*操作：   把树初始化为空*/
/*前提条件  ptree指向一个树*/
/*后置条件  树被初始化为空*/
void InitiallizeTree(Tree * ptree);


/*操作    确定树是否为空*/
/*前提条件  ptree指向一个已初始化的树 */
/*后置条件  如果树为空，该函数返回true，否则返回false*/
bool TreeIsEmpty(const Tree * ptree);


/*操作    确定树是否已满*/
/*前提条件  ptree指向一个已初始化的树 */
/*后置条件  如果树已满，该函数返回true，否则返回false*/
bool TreeIsFull(const Tree * ptree);


/*操作    确定树的项数*/
/*前提条件  ptree指向一个已初始化的树 */
/*后置条件  返回树的项数*/
int TreeItemCount(const Tree * ptree);


/*操作    在树中添加一个项*/
/*前提条件  pi是待添加的地址
            ptree指向一个已初始化的树 */
/*后置条件  如果可以添加，将在书中添加一个项，并返回true；否则返回false*/
bool AddItem(const Item * pi,Tree * ptree);


/*操作    在树中查找一个项*/
/*前提条件  pi指向一个项
            ptree指向一个已初始化的树 */
/*后置条件  如果在树中找到指定项，该函数返回true，否则返回false*/
bool InTree(const Item * pi, const Tree * ptree);


/*操作    从树中删除一项*/
/*前提条件  pi是删除项的地址
            ptree指向一个已初始化的树 */
/*后置条件  从树中成功删除一个项，该函数返回true，否则返回false*/
bool DeleteItem(const Item * pi, Tree * ptree);


/*操作    把函数应用于树中的每一项*/
/*前提条件  ptree指向一个已初始化的树
            pfunc 指向一个函数，该函数接受一个Item类型的参数，并且没有返回值*/
/*后置条件  pfunc指向的这个函数为树中的每一项执行一次*/
void Traverse(const Tree * ptree, void (*pfunc) (Item item));


/*操作    删除树中的所有内容*/
/*前提条件  ptree指向一个已初始化的树 */
/*后置条件  树为空*/
void DeleteAll(Tree * ptree);


#endif // TREE_H_INCLUDED

.
.
二、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 bool ToLeft(const Item * i1, const Item * i2);
static bool ToRight(const Item * i1, const Item * i2);
static void AddNode(Trnode * new_node, Trnode * root);
static void InOrder(const Trnode * root, void (*pfunc)(Item item));
static Pair SeekItem(const Item * pi, const Tree * ptree);
static void DeleteNode(Trnode **ptr);
static void DeleteAllNodes(Trnode * root);

/*函数定义*/
void InitiallizeTree(Tree * ptree)
{
    ptree->root = NULL;
    ptree->size = 0;
}

bool TreeIsEmpty(const Tree * ptree)
{
    if(ptree->root == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool TreeIsFull(const Tree * ptree)
{
    if(ptree->size == MAXITEMS)
    {
        return true;
    }
    else
    {
        return false;
    }
}

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

bool AddItem(const Item * pi,Tree * ptree)
{
    Trnode * new_node;
    if(TreeIsFull(ptree))
    {
        fprintf(stderr,"Tree is full\n");
        return false;
    }
    if(SeekItem(pi,ptree).child != NULL)
    {
        fprintf(stderr,"树中已经存在相关内容！\n");
        return false;
    }
    new_node = MakeNode(pi);
    if(new_node == NULL)
    {
        fprintf(stderr,"can't create node\n");
    }
    ptree->size++;

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

static bool ToLeft(const Item * i1, const Item * i2) //列出仅有的返回true的两种情况，其余都是返回false，编程思想，局部思考
{
    int comp1;
    if( (comp1 = strcmp(i1->petname,i2->petname) ) < 0)
    {
        return true;
    }
    else if(comp1==0 && strcmp(i1->petkind,i2->petkind) < 0)
    {
        return true;
    }
    else
        return false;
}

static bool ToRight(const Item * i1, const Item * i2)
{
    int comp1;
    if( (comp1 = strcmp(i1->petname,i2->petname) ) > 0)
    {
        return true;
    }
    else if(comp1==0 && strcmp(i1->petkind,i2->petkind) > 0)
    {
        return true;
    }
    else
        return false;

}

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

    if(TreeIsEmpty(ptree))
    {
        fprintf(stderr,"Tree is empty");
        return pair;
    }
    while(pair.child != NULL)
    {
        if(ToLeft(pi,&(pair.child->item) ))
        {
            pair.parent = pair.child;
            pair.child = pair.child->left;
        }
        else if(ToRight(pi,&(pair.child->item) ))
        {
            pair.parent = pair.child;
            pair.child = pair.child->right;
        }
        else
            break;
    }
    return pair;
}

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 void AddNode(Trnode * new_node, Trnode * root)
{
    Trnode * temp;
    if(ToLeft( &(new_node->item),&(root->item) ) )
    {
        temp  = root->left;
        if(temp != NULL)
        {
            AddNode(new_node,temp);
        }
        else{bool InTree(const Item * pi, const Tree * ptree);
            root->left = new_node;
        }
    }
    else if(ToRight( &(new_node->item),&(root->item) ) )
    {
        temp = root->right;
        if(temp != NULL)
        {
            AddNode(new_node,temp);
        }
        else{
            root->right = new_node;
        }
    }
    else{
        fprintf(stderr,"怎么重复了呢小老弟\n");
        exit(EXIT_FAILURE);
    }

}

bool InTree(const Item * pi, const Tree * ptree){
    return (SeekItem(pi,ptree).child != NULL) ? true:false;
}

bool DeleteItem(const Item * pi, Tree * ptree){
    Pair pair;
    pair = SeekItem(pi,ptree);
    if(pair.child == NULL){
        return false;
    }

    if(pair.parent == NULL){
        DeleteNode(&(ptree->root) );
    }
    else if(pair.parent->left == pair.child){
        DeleteNode(&(pair.parent->left) );
    }
    else{
        DeleteNode(&(pair.parent->right));
    }
    ptree->size--;
    return true;
}

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);
    }
}

//以下四个函数用到了分而治之的递归
void Traverse(const Tree * ptree, void (*pfunc) (Item item))
{
    if(ptree != NULL)
        InOrder(ptree->root,pfunc);
}

static void InOrder(const Trnode * root, void (*pfunc)(Item item))
{
    if(root != NULL)
    {
        InOrder(root->left,pfunc);
        (*pfunc)(root->item);
        InOrder(root->right,pfunc);
    }
}

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


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

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

.
.
三、main.c

#include <stdio.h>
#include <stdlib.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;

    InitiallizeTree(&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");
    //printf("%d",SLEN);
    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)
        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);
        printf("%s\n",temp.petname);
        puts("Please enter pet kind");
        s_gets(temp.petkind,SLEN);
        uppercase(temp.petname);
        uppercase(temp.petkind);
        AddItem(&temp,pt);
    }
}

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

void printitem(Item item)
{
    printf("Pet: %-19s Kind: %-19s\n",item.petname,item.petkind);
}

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

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

    puts("Please enter name of pet you wish to find:");
    s_gets(temp.petname,SLEN);
    puts("Please entet pet kind:");
    s_gets(temp.petkind,SLEN);
    uppercase(temp.petname);
    uppercase(temp.petkind);
    printf("%s the %s ",temp.petname,temp.petkind);
    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 entries");
        return;
    }

    puts("Please enter name of pet you wish to delete:");
    s_gets(temp.petname,SLEN);
    puts("Please enter pet kind");
    s_gets(temp.petkind,SLEN);
    uppercase(temp.petname);
    uppercase(temp.petkind);
    printf("%s is %s ",temp.petname,temp.petkind);
    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)
        {
            *find = '\0';
        }
        else
            while(getchar() != '\n')
                continue;
    }
    return ret_val;
}