抽象数据类型之二叉搜索树ADT接口包

mingcxx

这份二叉搜索树的接口有几个重要的函数是用递归实现的，譬如AddNode(), InOrder()等等，所以内存开销应该比其他算法要大了些。（算法接下来才学 ）

/*tree.h -- 二叉搜索树的接口头文件*/
/*树中不允许有相同的项目*/
#ifndef _TREE_H_
#define _TREE_H_
#include <stdbool.h>

/*您可以在这里把Item定义为适合的类型*/
typedef struct item
{
        char petname[20];
        char petkind[20];
} Item;

#define MAXITEMS 10

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


typedef struct tree
{
        Node * root;                        /*指向树根的指针*/
        int size;                                /*树中项目的个数*/
} Tree;

/*函数原型*/

/*操作：  把一个树初始化为一个空树*/
/*操作前：ptree指向一个树*/
/*操作后：该树已被初始化为空树*/
void InitializeTree(Tree * ptree);

/*操作：  确定树是否为空*/
/*操作前：ptree指向一个树*/
/*操作后：如果树为空则函数返回tree，
                  否则返回false*/
bool TreeIsEmpty(const Tree * ptree);

/*操作：  确定树是否已满*/
/*操作前：ptree指向一个树*/
/*操作后：如果树已满则函数返回tree，
                  否则返回false*/
bool TreeIsFull(const Tree * ptree);

/*操作：  确定树中项目的个数*/
/*操作前：ptree指向一个树*/
/*操作后：函数返回树中项目的个数*/
int TreeItemCount(const Tree * ptree);

/*操作：  向树中添加一个项目*/
/*操作前：pi是待添加项目的地址
                  ptree指向一个已初始化的树*/
/*操作后：如果可能，函数把项目添加到树中
                  并返回tree，否则返回false*/
bool AddItem(const Item * pi, Tree * ptree);

/*操作：  在树中查找一个项目*/
/*操作前：pi指向一个项目，
                  ptree指向一个已初始化的树*/
/*操作后：如果项目在树中，则函数返回tree，
                  否则返回false*/
bool InTree(const Item * pi, const Tree * ptree);

/*操作：  从树中删除一个项目*/
/*操作前：pi是待删除项目的地址
                  ptree指向一个已初始化的树*/
/*操作后：如果可能，函数从树中删除该项目
                  并返回tree，否则返回false*/
bool DeleteItem(const Item * pi, Tree * ptree);

/*操作：  把一个函数作用于树中每一个项目*/
/*操作前：ptree指向一棵树，
                  pfun指向一个没有返回值的函数，
                  该函数接受一个Item作为参数*/
/*操作后：pfun指向的函数被作用于树中
                  每一个项目一次*/
void Traverse(const Tree * ptree, void(*pfun)(Item item));

/*操作：  从树中删除所有节点*/
/*操作前：ptree指向一个已初始化的树*/
/*操作后：该树为空树*/
void EmptyAll(Tree * ptree);


#endif // !_TREE_H_

//tree.c -- 二叉搜索树类型的实现接口

#include <stdio.h>
#include <stdlib.h>                                                        //malloc(), free()
#include <stdbool.h>
#include <string.h>                                                //strcmp()
#include "tree.h"

//局部数据类型
typedef struct pair
{
        Node * parent;
        Node * child;
} Pair;

//局部函数原型
static Node * MakeNode(const Item * pi);
static bool ToLeft(const Item * pi1, const Item * pi2);
static bool ToRight(const Item * pi1, const Item * pi2);
static void AddNode(Node * pnew_node, Node * root);
static void InOrder(const Node * root, void(*pfun)(Item item));
static Pair SeekItem(const Item * pi, const Tree * ptree);
static void DeleteNode(Node ** ptr);
static void DeleteAllNodes(Node * root);


//函数定义
void InitializeTree(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)
{
        Node  * pnew_node;

        //检查树是否已满
        if (TreeIsFull(ptree))
        {
                fprintf(stderr, "Tree is full.\n");
                return false;
        }
        //检查欲添加项是否已存在
        if (SeekItem(pi, ptree).child != NULL)
        {
                fprintf(stderr, "Attempted to add duplicate item.\n");
                return false;
        }

        //尝试创建新节点
        pnew_node = MakeNode(pi);
        if (pnew_node == NULL)
        {
                fprintf(stderr, "Couldn't create node.\n");
                return false;
        }
        //创建成功，更新树结构
        ptree->size++;
        if (ptree->root == NULL)
        {
                ptree->root = pnew_node;
        }
        else
        {
                AddNode(pnew_node, ptree->root);
        }        
        return true;
}

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

bool DeleteItem(const Item * pi, Tree * ptree)
{
        Pair look;

        look = SeekItem(pi, ptree);
        if (look.child == NULL)
        {
                return false;                //失败返回
        }

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

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

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


//局部函数定义

Node * MakeNode(const Item * pi)
{
        Node * pnew_node;

        pnew_node = (Node *)malloc(sizeof(Node));                //分配节点内存
        if (pnew_node != NULL)                                        //分配到时进行节点的初始化
        {
                pnew_node->item = *pi;
                pnew_node->left = NULL;
                pnew_node->right = NULL;
        }
        return pnew_node;
}

bool ToLeft(const Item * pi1, const Item * pi2)
{
        int comp1;

        if ((comp1 = strcmp(pi1->petname, pi2->petname)) < 0)
        {
                return true;
        }
        else if (comp1 == 0 && strcmp(pi1->petkind, pi2->petkind) < 0)
        {
                return true;
        }
        else
        {
                return false;
        }
}

bool ToRight(const Item * pi1, const Item * pi2)
{
        int comp1;

        if ((comp1 = strcmp(pi1->petname, pi2->petname)) > 0)
        {
                return true;
        }
        else if (comp1 = 0 && strcmp(pi1->petkind, pi2->petkind) > 0)
        {
                return true;
        }
        else
        {
                return false;
        }
}

void AddNode(Node * pnew_node, Node * root)                        //递归
{
        if (ToLeft(&pnew_node->item, &root->item))
        {
                if (root->left == NULL)
                {
                        root->left = pnew_node;
                }
                else
                {
                        AddNode(pnew_node, root->left);
                }
        }
        else if (ToRight(&pnew_node->item,&root->item))
        {
                if (root->right == NULL)
                {
                        root->right = pnew_node;
                }
                else
                {
                        AddNode(pnew_node, root->right);
                }
        }
        else
        {
                fprintf(stderr, "location error in AddNode().\n");
                exit(EXIT_FAILURE);
        }
}

void InOrder(const Node * root, void(*pfun)(Item item))                //递归
{
        //递归调用访问非空的子树，遍历顺序：中序遍历
        if (root != NULL)
        {
                InOrder(root->left, pfun);
                (*pfun)(root->item);
                InOrder(root->right, pfun);
        }
}

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;                //如果前两种情况都不满足，必定为相等的情况，中断循环，look.child等于目标节点的地址
                }
        }
        return look;
}

void DeleteNode(Node ** ptr)
{
        Node * temp;

        puts((*ptr)->item.petname);
        if ((*ptr)->left == NULL)
        {
                *ptr = (*ptr)->right;        //只有右支时，让待删节点的父节点中指向该节点的指针，修改为指向待删节点的右子树
        }
        else if ((*ptr)->right == NULL)
        {
                *ptr = (*ptr)->left;        //同上
        }
        else                                //待删节点有2个子节点
        {        
                                                                //在左子树的右支查找空的右子树
                for (temp = (*ptr)->left; temp->right == NULL; temp = temp->right)
                {
                        continue;
                }
                temp->right = (*ptr)->right;
                temp = *ptr;
                *ptr = temp->left;
                free(temp);
        }
}

void DeleteAllNodes(Node * root)                                //递归
{
        Node *pright;

        if (root != NULL)
        {
                //中序遍历删除非空的子树
                pright = root->right;
                DeleteAllNodes(root->left);
                free(root);
                DeleteAllNodes(pright);
        }
}