抽象数据类型之二叉搜索树ADT接口包
本帖最后由 mingcxx 于 2016-9-6 01:05 编辑这份二叉搜索树的接口有几个重要的函数是用递归实现的，譬如AddNode(), InOrder()等等，所以内存开销应该比其他算法要大了些。（算法接下来才学{:10_279:} ）
/*tree.h -- 二叉搜索树的接口头文件*/
/*树中不允许有相同的项目*/
#ifndef _TREE_H_
#define _TREE_H_
#include <stdbool.h>
/*您可以在这里把Item定义为适合的类型*/
typedef struct item
{
char petname;
char petkind;
} 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);
}
}
页:
[1]